Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-08-04
2002-01-29
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S121000, C711S122000, C711S143000
Reexamination Certificate
active
06343344
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to directory accesses necessary for data access operations in data processing systems and in particular to directory lookups and tag comparisons for related data access and cast out operations. Still more particularly, the present invention relates to concurrent directory lookups and tag comparisons for related data access and cast out operations to improve storage device performance and response latency.
2. Description of the Related Art
High performance data processing systems typically include a number of levels of caching between the processor(s) and system memory to improve performance, reducing latency in data access operations. When utilized, multiple cache levels are typically employed in progressively larger sizes with a trade off to progressively longer access latencies. Smaller, faster caches are employed at levels within the storage hierarchy closer to the processor or processors, while larger, slower caches are employed at levels closer to system memory. Smaller amounts of data are maintained in upper cache levels, but may be accessed faster.
Within such systems, when data access operations frequently give rise to a need to make space for the subject data. For example, when retrieving data from lower storage levels such as system memory or lower level caches, a cache may need to overwrite other data already within the cache because no further unused space is available for the retrieved data. A replacement policy—typically a least-recently-used (LRU) replacement policy—is employed to decide which cache location(s) should be utilized to store the new data.
Often the cache location (commonly referred to as a “victim”) to be overwritten contains only data which is invalid or otherwise unusable from the perspective of a memory coherency model being employed, or for which valid copies are concurrently stored in other devices within the system storage hierarchy. In such cases, the new data may be simply written to the cache location without regard to preserving the existing data at that location.
At other times, however, the cache location selected to received the new data contains modified data, or data which is otherwise unique or special within the storage hierarchy. In such instances, the replacement of data within a selected cache location (a process often referred to as “updating” the cache) requires that any modified data associated with the cache location selected by the replacement policy be written back to lower levels of the storage hierarchy for preservation. The process of writing modified data from a victim to system memory or a lower cache level is generally called a cast out or eviction.
When a cache initiates a data access operation—for instance, in response to a cache miss for a READ operation originating with a processor—typically the cache will initiate a data access operation (READ or WRITE) on a bus coupling the cache to lower storage levels. If the replacement policy requires that a modified cache line be over-written, compelling a cast out for coherency purposes, the cache will also initiate the cast out, but on a subsequent bus cycle. The data access operation thus requires multiple operations, and bus cycles, to complete.
In other storage devices within the system, the data access operation and related cast out also require multiple directory accesses. Whether the storage devices is a vertically in-line device to which the data access and cast out operations are directed, or a horizontal storage device snooping the data access and cast out operations, separate directory lookups and the associated tag comparisons must be performed for these discrete operations.
It would be desirable, therefore, to reduce the number of directory accesses associated with data access operations requiring a victim cast out. It would further be advantageous to improve latency associated with responses to data access operations requiring a cast out.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide improved directory accesses necessary for data access operations in data processing systems.
It is another object of the present invention to provide improved directory lookups and tag comparisons for related data access and cast out operations.
It is yet another object of the present invention to provide concurrent directory lookups and tag comparisons for related data access and cast out operations to improve storage device performance and response latency.
The foregoing objects are achieved as is now described. In response to receiving a combined address for related data access and cast out operations, including an index identifying a congruence class containing both the target of the data access and the victim of the cast out, a single directory access is performed utilizing the index to locate the congruence class. Address tags within the congruence class are then compared to the address tag for the data access operation and the address tag for the cast out operation concurrently, generating separate hit signals as appropriate. Only a single directory access is required, however, rather than two separate directory accesses as required in the known art, taking advantage of the fact that both the data access target and the cast out victim belong to a single congruence class. Response latency is also improved, as is address bus bandwidth utilization.
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: 4797814 (1989-01-01), Brenza
patent: 5369753 (1994-11-01), Tipley
patent: 5493668 (1996-02-01), Elko et al.
patent: 5564035 (1996-10-01), Lai
patent: 5636355 (1997-06-01), Ramakrishnan et al.
patent: 5829038 (1998-10-01), Merrell et al.
patent: 5829040 (1998-10-01), Son
patent: 5895495 (1999-04-01), Arimilli et al.
patent: 5946709 (1999-08-01), Arimilli et al.
patent: 5966729 (1999-10-01), Phelps
patent: 6018791 (2000-01-01), Arimilli et al.
patent: 6021468 (2000-02-01), Arimilli et al.
patent: 6023747 (2000-02-01), Dodson
patent: 6029204 (2000-02-01), Arimilli et al.
patent: 6058456 (2000-05-01), Arimilli et al.
patent: 6195729 (2001-02-01), Arimilli et al.
Lebeck et al., Request combining in multiprocessors with arbitrary interconnection networks, IEEE digital library, vol. 5, No. 11, pp. 1140-1155, Nov. 1994.*
Texas Instruments Incorporated, TM532010 User's Guide, 1983, 3 pages.
Handy, Jim;The Cache Memory Book; Academic Press, Inc.; 1993; pp. 77-82.
Arimilli Ravi Kumar
Dodson John Steven
Guthrie Guy Lynn
Joyner Jody B.
Lewis Jerry Don
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Nguyen Hiep T.
Salys Casimer K.
LandOfFree
System bus directory snooping mechanism for read/castout... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System bus directory snooping mechanism for read/castout..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System bus directory snooping mechanism for read/castout... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857717