Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-02-17
2001-09-18
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S144000, C711S145000
Reexamination Certificate
active
06292872
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to a method and system for data processing and in particular to a method and system for maintaining cache coherency in a multiprocessor data processing system. Still more particularly, the present invention relates to a cache coherency protocol for a multiprocessor data processing system, which includes a recent (R) state that supports shared intervention and a hovering (H) state that permits a first cache to be updated with valid data in response to a second cache independently transmitting the valid data on an interconnect coupling the first and second caches.
2. Description of the Related Art
In a conventional symmetric multiprocessor (SMP) data processing system, all of the processors are generally identical, that is, the processors all utilize common instruction sets and communication protocols, have similar hardware architectures, and are generally provided with similar memory hierarchies. For example, a conventional SMP data processing system may comprise a system memory, a plurality of processing elements that each include a processor and one or more levels of cache memory, and a system bus coupling the processing elements to each other and to the system memory. To obtain valid execution results in an SMP data processing system, it is important to maintain a coherent memory hierarchy, that is, to provide a single view of the contents of memory to all of the processors.
A coherent memory hierarchy is maintained through the use of a selected memory coherency protocol, such as the MESI protocol. In the MESI protocol, an indication of a coherency state is stored in association with each coherency granule (e.g., cache line or sector) of at least all upper level (cache) memories. Each coherency granule can have one of four states, modified (M), exclusive (E), shared (S), or invalid (I), which is indicated by two bits in the cache directory. The modified state indicates that a coherency granule is valid only in the cache storing the modified coherency granule and that the value of the modified coherency granule has not been written to system memory. When a coherency granule is indicated as exclusive, the coherency granule is resident in, of all caches at that level of the memory hierarchy, only the cache having the coherency granule in the exclusive state. The data in the exclusive state is consistent with system memory, however. If a coherency granule is marked as shared in a cache directory, the coherency granule is resident in the associated cache and in at least one other cache at the same level of the memory hierarchy, all of the copies of the coherency granule being consistent with system memory. Finally, the invalid state indicates that the data and address tag associated with a coherency granule are both invalid.
The state to which each coherency granule (e.g., cache line) is set is dependent upon both a previous state of the cache line and the type of memory access sought by a requesting processor. Accordingly, maintaining memory coherency in the multiprocessor data processing system requires that the processors communicate messages across the system bus indicating their intention to read or write memory locations. For example, when a processor desires to write data to a memory location, the processor must first inform all other processing elements of its intention to write data to the memory location and receive permission from all other processing elements to carry out the write operation. The permission messages received by the requesting processor indicate that all other cached copies of the contents of the memory location have been invalidated, thereby guaranteeing that the other processors will not access stale local data. This exchange of messages is known as cross-invalidation (XI).
The present invention includes a recognition that while cross-invalidation of cache entries serves to maintain memory coherency in a SMP data processing system, the invalidation of cache entries by remote processors adversely affects data processing system performance by decreasing hit ratios in local caches. Thus, even if equipped with large local caches, a processing element can incur long access latencies when retrieving data that were once resident in a local cache from either a remote cache in another processing element or from system memory. As should thus be apparent, it would be desirable to provide a method and system for maintaining memory coherency in a SMP data processing system that reduces the performance penalty incurred as a result of the cross-invalidation of cache entries.
The present invention also includes a recognition that the conventional MESI protocol does not support efficient retrieval of data stored in remote caches. Although some known multiprocessor data processing systems support so-called modified intervention, which permits a remote cache storing data in the modified state to supply the modified data in response to a read request, the MESI protocol does not allocate responsibility for sourcing data to another processing element when the requested data is in the shared state. Thus, although requested data may be stored in multiple remote caches at a relatively low access latency, in conventional multiprocessor data processing systems shared data must always be retrieved from system memory. It would therefore be desirable to provide an improved cache coherency protocol that supports shared intervention.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method and system for data processing.
It is another object of the present invention to provide an improved method and system for maintaining cache coherency in a multiprocessor data processing system.
It is yet another object of the present invention to provide a cache coherency protocol for a multiprocessor data processing system, which includes a recent (R) state that supports shared intervention and a hovering (H) state that permits a first cache to be updated with valid data in response to a second cache independently transmitting the valid data on an interconnect coupling the first and second caches.
The foregoing objects are achieved as is now described. A data processing system is provided that includes a plurality of processors and a plurality of caches coupled to an interconnect. According to the method of the present invention, a first data item is stored in a first of the caches in association with an address tag indicating an address of the first data item. A coherency indicator in the first cache is set to a first state that indicates that the tag is valid and that the first data item is invalid. Thereafter, the interconnect is snooped to detect a data transfer initiated by another of the plurality of caches, where the data transfer is associated with the address indicated by the address tag and contains a valid second data item. In response to detection of such a data transfer while the coherency indicator is set to the first state, the first data item is replaced by storing the second data item in the first cache in association with the address tag. In addition, the coherency indicator is updated to a second state indicating that the second data item is valid and that the first cache can supply said second data item in response to a request.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5119485 (1992-06-01), Ledbetter, Jr. et al.
patent: 5265235 (1993-11-01), Sindhu et al.
patent: 5274787 (1993-12-01), Hirano et al.
patent: 5282272 (1994-01-01), Guy et al.
patent: 5287484 (1994-02-01), Nishii et al.
patent: 5319766 (1994-06-01), Thaller et al.
patent: 5522057 (1996-05-01), Lichy
patent: 5551001 (1996-08-01), Cohen et al.
patent: 5588131 (1996-12-01), Borrill
patent: 5598550 (1997-01-01), Shen et al.
patent: 5666509 (1997-09-01), McCarthy et al.
patent: 5671391 (1997-09-01), Knotts
patent: 5737757 (1998-04-01), Hassoun
Arimilli Ravi Kumar
Dodson John Steven
Lewis Jerry Don
International Business Machines - Corporation
Kim Matthew
Peugh Brian R.
Volel Emile Bracewell & Patterson, L.L.P.
LandOfFree
Cache coherency protocol having hovering (H) and recent (R)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache coherency protocol having hovering (H) and recent (R)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache coherency protocol having hovering (H) and recent (R)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2436334