Cache coherence system

Claim 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 including means for storing cache data therein at internal locations, said cache data being associated with main memory data stored in corresponding locations in said main memory, iii. selectively operable means for transferring cache data from selected locations in said local cache memory to said central processing unit, iv. cache data means selectively operable in conjunction with said central processing unit for generating cache data and for storing said generated cache data in selected locations in said local cache memory, C. detection means associated with each data processor 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 associated with its CCP, D. cache change means assoicated with each data processor and responsive to said determination, 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 associated with its CCP, E. n cache coherence processors (CCP's), each CCP being associated with 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 for receiving said cache change signals, iii. means for loading said CIT memory including: a. selectively operable means responsive to the CPU of its associated data V 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. selectively operable means responsive to said received cache change signals for modifying the contents of the location of said CIT memory corresponding to said determined location of said generated cache data, whereby said location of said CIT memory store 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 in said CIT memory. 2. A multiprocessor system according to claim 1 wherein each of said data processors further includes: a selectively operable interrogator including CIT means for identifying linked list locations in the CIT memory of its associated CCP having a flag portion stored therein and cache means for identifying the locations in the local cache memory of said data processor corresponding to the linked list locations in said associated CIT memory storing 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 adapted for coupling to a data processor of a multiprocessor system including said data processor and one or more other data processors coupled to a common main memory, each of said data processors including an associated cache memory having storage locations therein corresponding to storage locations in said main memory, comprising: A. cache invalidate tag (CIT) memory including storage locations therein corresponding to locations in said memory of said coupled data processor, B. means for detecting, when the contents of a location of one of said cache memories have been changed in conjuction with the operation of one of said data processors, C. means responsive to said detections for generating and storing in said CIT memory a multiple element linked list defining the cache memory locations having changed contents, each element of said list defining one of said cache memory locations having changed contents and identifying the storage location in said CIT memory of the next element in said list. 6. A cache coherence system according to claim 5 further comprising means selectively operable by a coupled data processor 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. 7. A cache coherence system according to claims 5 or 6 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. 8. A processing system having a main memory and at least two data processors operable to access the main memory, characterised in that-each processor includes: a respective associated cache memory arranged to store cache data associated with data in the main memory, the cache data being stored in cache memory locations corresponding to main memory locations for storing the assocated main memory data, a cache coherence system including a cache invalidate table memory having internal storage loactions for storing data associated with the data stored in the respective cache memory, and means for detecting when the contents of storage locations in the cache memories of one or more of the data processors have been modified in conjunction with the activity of that of those data processor or processors, and means responsive to the detecting means for generating and storing in the cache invalidate table memory a multiple element linked list defining locations in the cache memory or memories having modified contents. 9. A processing system according to claim 8, wherein each element in the list defines a respective cache memory storage location and identifies the location in the cache invalidate table memory of the next element in the list.