Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-02-17
2001-07-17
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S141000, C711S146000, C711S134000
Reexamination Certificate
active
06263407
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 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.
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 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 which are each associated with a respective one of a plurality of caches. According to the method of the present invention, a first data item is stored in a first cache in association with an address tag indicating an address of the data item. A coherency indicator in the first cache is set to a first state that indicates that the first data item is valid. In response to another cache indicating an intent to store to the address indicated by the address tag while the coherency indicator is set to the first state, the coherency indicator in the first cache is updated to a second state that indicates that the address tag is valid and that the first data item is invalid. Thereafter, in response to detection of a remotely-sourced data transfer that is associated with the address indicated by the address tag and includes a second data item, a determination is made, in response to a mode of operation of the first cache, whether or not to update the first cache. In response to a determination to make an update to the first cache, the first data item is replaced by storing the second data item in association with the address tag, and the coherency indicator is updated to a third state that indicates that the second data item is valid. In one embodiment, the operating modes of the first cache include a precise mode in which cache updates are always performed and an imprecise mode in which cache updates are selectively performed. The mode in which the first cache operates may be set by hardware or software.
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: 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 et al.
patent: 5900016 (1999-05-01), Ghosh
patent: 6014728 (2000-01-01), Baror
patent: 6038644 (2000-03-01), Irie et al.
patent: 6049849 (2000-04-01), Arimilli et al.
patent: 0378399A2 (1990-07-01), None
patent: 0438211A2 (1991-07-01), None
patent: 0489556A2 (1992-06-01), None
patent: 0681241A1 (1995-11-01), None
patent: 2178205A (1987-02-01), None
patent: 253963A (1991-11-01), None
patent: 06110785A (1994-04-01), None
patent: 110785A (1994-04-01), None
patent: 06110844A (1994-04-01), None
Jim Handy, The Cache Memory Book, 1993
Arimilli Ravi Kumar
Dodson John Steven
Lewis Jerry Don
Bracewell & Patterson L.L.P.
Emile Volel
International Business Machines - Corporation
Kim Matthew
Peugh B.
LandOfFree
Cache coherency protocol including a hovering (H) state... 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 including a hovering (H) state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache coherency protocol including a hovering (H) state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484944