Computer cache system with deferred invalidation

Details Computer cache system with deferred invalidation Computer cache system with deferred invalidation

2000-07-31

2003-06-03

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S141000, C711S146000

Reexamination Certificate

active

06574710

ABSTRACT:

FIELD OF INVENTION
This invention relates generally to computer systems and more specifically to coherency protocols and inclusion in cache memory systems.
BACKGROUND OF THE INVENTION
Most computer systems employ a multilevel hierarchy of memory systems, with relatively fast, expensive, limited-capacity memory at the highest level of the hierarchy (closest to the processor) and proceeding to relatively slower, lower cost, higher-capacity memory at the lowest level of the hierarchy (typically relatively far from the processor). Typically, the hierarchy includes a small fast memory called a cache, either physically integrated within a processor integrated circuit or mounted physically close to the processor for speed. There may be separate instruction caches and data caches. There may be multiple levels of caches.
The minimum amount of memory that can be transferred between a cache and a next lower level of the memory hierarchy is called a line, or block, or page. The present patent document uses the term “line,” but the invention is equally applicable to systems employing blocks or pages.
In most multilevel caches, each cache level has a copy of every line of memory residing in every cache level higher in the hierarchy (closer to the processor), a property called inclusion. For example, in an inclusive two-level cache system, every entry in the primary cache is also in the secondary cache. Typically, when a line is evicted from an upper level cache, the line is permitted to remain in lower level caches. Conversely, in order to maintain inclusion, if a line is evicted from a lower level cache, the lower level cache must issue a bus transaction, called a back-invalidate transaction, to flush any copies of the evicted line out of upper levels of the cache hierarchy. Each back-invalidate instruction causes any cache at a higher level in the hierarchy to invalidate its copy of the item corresponding to the address, and to provide a modified copy of the item to the lower level cache if the item has been modified. Back-invalidate transactions occur frequently and have a significant impact on overall performance, because of increased bus utilization between the caches and increased bus monitoring (snoop) traffic.
Many computer systems employ multiple processors, each of which may have multiple levels of caches. All processors and caches may share a common main memory. A particular line may simultaneously exist in shared memory and in the cache hierarchies for multiple processors. All copies of a line in the caches must be identical, a property called coherency. The copy of a line in shared memory may be “stale” (not updated). If any processor changes the contents of a line, only the one changed copy is then valid, and all other copies must be then be updated or invalidated. The protocols for maintaining coherence for multiple processors are called cache-coherence protocols. In some protocols, the status of a line of physical memory is kept in one location, called the directory. In other protocols, every cache that has a copy of a line of physical memory also has a copy of the sharing status of the line. When no centralized state is kept, all caches monitor or “snoop” a shared bus to determine whether or not they have a copy of a line that is requested on the bus. The present patent document is relevant to any multi-level cache system, but is particularly relevant to multi-processor systems, with each processor having a hierarchy of caches, all sharing a main memory, in a snooping based system.
In a snooping based system, the cache system monitors transactions on a bus. Some of the transactions indicate that an item has been evicted from an upper level of the cache system. However, some transactions may only “hint” that an item has been evicted from a high level of the cache system, but a low level of the cache does not know with complete certainty that the item is not still retained by a higher level. For example, some systems do not implement inclusion at the upper levels of the cache hierarchy. If the system does not implement inclusion at higher cache levels, then a third level cache may see that an item has been evicted from a second level cache, but the third level cache does not know whether a copy of the item is in the first level cache. One possible solution is for the low level cache to immediately issue a back-invalidate transaction (which may be unnecessary). Since the back-invalidate transaction may interrupt other bus activity, the transaction may degrade performance. Another possible solution is for the lower level cache to ignore the hint. If the line is later requested by another cache, then the lower level cache may issue an immediate back-invalidate transaction at the time of the later request, adding latency to the later request. There is a need for a computer cache system which can detect a need for invalidation, without requiring an immediate invalidate transaction.
SUMMARY OF THE INVENTION
A lower level cache stores addresses that may need to be invalidated, and waits until a bus is idle before issuing a back-invalidate transaction. If a lower level cache knows with certainty that an item is invalidated in the higher cache levels, then there is an opportunity for performance enhancement. The lower cache can place the item in a state (called Modified-uncached, or Mu). For items in the Mu state, no back-invalidate transaction is required when the item is evicted from the lower level cache. This improves performance by eliminating the need for some back-invalidate transactions. Accordingly, knowledge that an item has been evicted from a higher level is useful for improving performance, but is not required. In accordance with the invention, a lower level cache includes a list or stack containing addresses of items that have been recently evicted from one higher level of the cache hierarchy, but for which the lower level of the cache does not know with complete certainty that the items are not still retained by some other higher level cache. During idle bus cycles, the lower-level cache issues back-invalidate transactions for addresses in the list, enabling the corresponding items to be placed into the Mu state without interrupting other bus activity. Upon completion of the back-invalidate command, the address is removed from the list. It is permissible for the list or stack to overflow or fill. That is, if the list fills, additional entries may be refused, or new entries may displace old entries, and the only consequence is that some items in the lower level cache are not placed in the Mu state, and a later back-invalidate command may have to be issued at an inopportune time. The resulting cache system can take advantage of the Mu state without requiring complete certainty as to whether evicted items at some levels are still being retained at higher levels in the cache hierarchy.


REFERENCES:
patent: 5261066 (1993-11-01), Jouppi et al.
patent: 5577227 (1996-11-01), Finnell et al.
patent: 5860095 (1999-01-01), Iacobovici et al.
patent: 5996048 (1999-11-01), Cherabuddi et al.
patent: 6049847 (2000-04-01), Vogt et al.
patent: 6078992 (2000-06-01), Hum
patent: 6134634 (2000-10-01), Marshall, Jr. et al.
patent: 6360301 (2002-03-01), Gaither et al.
patent: 6477635 (2002-11-01), Kahle et al.

Affiliated with

Also associated with

Rating

Computer cache system with deferred invalidation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Computer cache system with deferred invalidation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer cache system with deferred invalidation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3141556