Virtual memory cache for use in multi-processing systems

• US 4,843,542 A
• Filed: 11/12/1986
• Issued: 06/27/1989
• Est. Priority Date: 11/12/1986
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Prasad, Bindiganavele A., Steffen, James A., Dashiell, Stephen R., Rider, Ronald E.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/930,172
• Time in Patent Office: 958 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/119
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)

Abstract

A system for maintaining data consistency among distributed processors, each having its associated cache memory. A processor addresses data in its cache by specifying the virtual address. The cache will search its cells for the data associatively. Each cell has a virtual address, a real address, flags and a plurality of associated data words. If there is no hit on the virtual address supplied by the processor, a map processor supplies the equivalent real address which the cache uses to access the data from another cache if one has it, or else from real memory. When a processor writes into a data word in the cache, the cache will update all other caches that share the data before allowing the write to the local cache.

Claims

1. A parallel data processor system for maintaining the consistency of data blocks, each block containing a plurality of bits of data and a master flag bit, said means for maintaining comprising:

a main memory for storing blocks of data,

a plurality of caches, each storing a plurality of addressable data blocks, each cache comprising a first and second data port and each data block comprising data and a master flag bit.

one data bus connecting the main memory and the first port of all caches,

a processor associated with each cache and connected to the second port of its associated cache,

means in each cache for allowing the processor to write into an addressed data block comprising,

(a) if the block is contained in the associated cache, means for setting the master flag in that cache, means for writing into any other cache that is sharing the block, means for resetting the master flag in all other caches, and means for allowing the processor to write into the block of the associated cache, or

(b) if the block is not contained in the associated cache, means for reading the block from another cache if any other cache has the block with the master flag set for that block, or from main memory otherwise, means for setting the master flag in the associated cache and resetting the master flag in all other caches, and

(c) means for allowing the processor to write into the block of the associated cache, and

means each cache for allowing the processor to read from an addressed block comprising,

(a) if the block is in the associated cache, means for allowing the associated processor to read from the block, or

(b) if the block is not in the associated cache, means for reading it into the associated cache from the cache having the block in which the master flag is set, or for reading it from memory otherwise, and

(c) means for allowing the associated processor to read from the block.

2. The system of claim 1 wherein

said block of data comprises said bits of data grouped into a plurality of words, and wherein, when one cache writes into another cache having shared data, only the one word being modified is written.

3. The system of claim 1 wherein each block has a shared flag which signifies to the cache that the data is shared, further comprising a shared line connecting all caches, and,

means within each cache for asserting the line by driving the line to its true value when a shared block of data is requested by another cache, means for setting the shared flag if the cache either asserts the line or requests the data and senses that another cache has asserted the line, and means for resetting the shared flag is the cache attempts to write data onto the bus to update the other caches that may be sharing the data and the shared line is not asserted by any other cache.

4. The system of claim 1 further comprising:

means in each cache for performing a read-modify-write sequence between a processor and its associated cache and for preventing another processor from writing into the shared block in its associated cache for the duration of said sequence.

5. The method of maintaining consistency between data blocks, each having a master flag bit, in a parallel data processing system comprising a main memory and a plurality of cache memories connected by one data bus, when a processor associated with one cache initiates a read from or a write into its associated cache comprising the steps of:

(A) in the case of a write by the processor into the cache data block, first

if the block is in the cache and the data is shared with at least one other cache, writing into all caches having the shared data, and setting the master flag of the associated cache,

if the block is not in the associated cache obtaining the block from one of the other caches if it has its master flag set, otherwise,

getting the block from main memory,

and in all cases, setting the block master flag of the associated cache, or

(B) in the case of a read from a data block in the associated cache, first

if the block is not in the associated cache, reading the block from any other cache which has the block in which the master flag is set, otherwise reading the block from main memory.

6. The method of claim 5 wherein the step of writing into all caches which share the data will result in the writing of only one word within said block.

7. The method of claim 5 further comprising:

if the block is shared, during a read-modify-write sequence between a processor and its associated cache, preventing another processor from writing into the shared block in its associated cache for the duration of said sequence.

8. The method of claim 5 further comprising:

using a shared flag in every cache as an indication that the data may be shared,

when a first cache tries to write data into a second cache by transmitting the data onto the bus, having the second cache assert a shared line by driving the line to its true value if the data is shared,

when the shared line is asserted true, having the first and second caches set the shared flag, and

when said first cache tries to write data into the second cache and no other cache asserts the line true, resetting the shared flag.

9. In a system comprising a plurality of caches connected by one data bus, each said cache associated with a processor, a method of supplying a data block from a real memory or from a cache to its associated processor which requests data by addressing a virtual location comprising the steps of:

storing a plurality of data blocks in the cache, each block associated with a virtual page and block address and a real page and block address,

supplying the data block in the cache to the processor if the block is stored in the cache in association with the virtual address,

if the block is not stored therein,

converting the virtual address into a real address in a means for mapping and transmitting it to all caches and memory,

using this real address to read a data block from real memory if no other cache has the data with its master flag set, or to read the block from another cache if said cache has the data and its master flag set,

storing this data block and its associated virtual and real addresses in cache, and

supplying this block to the processor.

10. The method of claim 9 wherein the means for mapping receives the virtual page address from the cache, transmits to the cache the corresponding real page address, and wherein the cache adds the virtual block address to the real page address to form the real address.

11. The method of claim 9 wherein, if the virtual address which the cache receives from the processor has the same page address as a second virtual address already stored in the cache, combining the real page address associated with the second virtual address with the block address of the virtual address received from the processor to form a complete real address which can be used to read data from said main memory.

12. The method of claim 9, including the steps of

invalidating the virtual page address corresponding to a real page address,

establishing a new virtual page address corresponding to a real page address,

receiving a real page address from said means for mapping corresponding to the virtual page address requested by said processor, and

using the real address to access data in the cache, if a data block associated with that real address is present in the cache.