Multiprocessor cache coherence system

• US 4,747,043 A
• Filed: 03/27/1987
• Issued: 05/24/1988
• Est. Priority Date: 02/10/1984
• Status: Expired due to Fees

• Current Assignee: CVSI, Inc. (NCR Voyix Corporation)
• Original Assignee: Prime Computer, Inc. (DR Holdings, Inc. of Delaware)
• Inventors: Rodman, Paul K.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/032,990
• Time in Patent Office: 424 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/124
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means

Abstract

A cache coherence system for a multiprocessor system including a plurality of data processors coupled to a common main memory. Each of the data processors includes an associated cache memory having storage locations therein corresponding to storage locations in the main memory. The cache coherence system for a data processor includes a cache invalidate table (CIT) memory having internal storage locations corresponding to locations in the cache memory of the data processor. The cache coherence system detects when the contents of storage locations in the cache memories of the one or more of the data processors have been modified in conjuction with the activity those data processors and is responsive to such detections to generate and store in its CIT memory a multiple element linked list defining the locations in the cache memories of the data processors having modified contents. Each element of the list defines one of those cache storage locations and also identifies the location in the CIT memory of the next element in the list.

Claims

1. A multiprocessor system comprising:

A. a main memory means for storing main memory data at locations therein, and an associated memory bus coupled thereto,

B. n data processors, where n is an integer greater than one, each data processor being coupled to said memory bus, and each data processor including;

i. a central processing unit (CPU),

ii. a local cache memory connected with said central processing unit and including means for storing cache data therein at internal locations, said cache data corresponding to main memory data stored in corresponding locations in said main memory,

iii. means connected with said central processing unit and with said local cache memory for transferring cache data from selected locations in said local cache memory to said central processing unit,

iv. cache data means connected with said central processing unit and with said local cache memory and being responsive to said central processing unit for generating cache data and for storing said generated cache data in selected locations in said local cache memory,

v. detection means for each data processor and connected with said cache data means for determining when said cache data means stores said generated cache data in its local cache memory means and for determining the location of said generated cache data stored in the local cache memory,

vi. cache change means for each data processor and connected with said detection means and responsive to a determination that said cache data means stores generated cache data in its local cache memory means, for generating a cache change signal, said cache change signal being representative of the location of said generated cache data stored in the local cache memory,

vii. means connected with said memory bus for transmitting said cache change signal to said other data processors, said cache change signal being transmitted substantially concurrently with the generation and storage of cache data by said cache data means,

C. n cache coherence processors (CCP'"'"'s), each CCP being connected with a corresponding one of said data processors, and including;

i. cache invalidate tag (CIT) memory including means for storing a CIT data word associated with each of the locations in the local cache memory associated with said CCP,

ii. means connected with said memory bus for receiving said cache change signals from said other data processors,

iii. means for loading said CIT memory including;

a. means responsive to the CPU of the corresponding data processor for loading said locations of said CIT memory with CIT data words corresponding to the cache data at the respective locations in said local cache memory associated with said CPU,

b. means responsive to a cache change signal received from another said data processor for modifying the contents of a location of a CIT memory corresponding to the location of said generated cache data of said other data processor, whereby said location of said CIT memory stores a linked list of cache invalidate words, each cache invalidate word including a flag portion representative of the occurrence of said generation and storage and including a pointer portion representative of the location in said CIT memory storing the next previously stored cache invalidate word.

2. A multiprocessor system according to claim 1 wherein each of said data processors further includes:

A. CIT means connected with the associate CCP for identifying in the associated CIT memory linked list locations having a flag portion stored therein, and

B. cache means connected with the local cache memory of the data processor for identifying the locations corresponding to the linked list locations in said associated CIT memory that store a flag portion therein.

3. A multiprocessor system according to claim 2 wherein said cache means includes means for successively determining the identity of each of said linked list locations from the pointer portion of the next previously stored cache invalidate word.

4. A multiprocessor according to claim 1 wherein said cache change means includes means for transferring said cache change signals to each CCP at least in part by way of said memory bus.

5. A cache coherence system according to claim 1 further comprising means coupled with one of said data processors and responsive thereto for sequentially processing said stored linked list element by element, and for communicating to said coupled data processor the locations in said cache memories having changed contents defined by said linked list.

6. A cache coherence system according to claim 5 further comprising:

means for detecting when the contents of a cache memory location in a coupled data processor have been changed in conjunction with the operation of said coupled data processor, and means for generating cache change signals representative of said detections,

means for communicating said cache change signals to said other data processors.