Deallocation with cache update protocol (L2 evictions)

Details Deallocation with cache update protocol (L2 evictions) Deallocation with cache update protocol (L2 evictions)

1998-02-17

2001-02-27

Cabeca, John W. (Department: 2752)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S122000, C711S165000

Reexamination Certificate

active

06195729

ABSTRACT:

RELATED APPLICATIONS
The present invention is related to the subject matter of commonly assigned, copending U.S. patent application Ser. No. 09/024,316 entitled “Merged Vertical Cache Controller Mechanism” and filed Feb. 17, 1998, the content of which is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to eviction of data from caches in a data processing system and in particular to eviction of data from a cache in a data processing system having a multilevel cache hierarchy. Still more particularly, the present invention relates to eviction of data from one cache to a logically in line cache within a data processing system having a multilevel cache hierarchy.
2. Description of the Related Art
Most contemporary data processing system architectures include multiple levels of cache memory within the storage hierarchy. Caches are employed in data processing systems to provide faster access to frequently used data over access times associated with system memory, thereby improving overall performance. Caches at any level in the storage hierarchy may be private (reserved for a local processor) or shared (accessible to multiple processors), although typically caches at levels closer to the processors are private. Level one (L1) caches, those logically closest to the processor, are typically implemented as an integral part of the processor and may be bifurcated into separate data and instruction caches. Lower level caches are generally implemented as separate devices, although a level two (L2) may be formed within the same silicon die as a processor.
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. Logically in line caches within a multilevel cache hierarchy are generally utilized to stage data to and from caches in higher levels of the storage hierarchy. As data is staged or transferred from system memory or caches in lower levels of the storage hierarchy to a cache in a higher level of the storage hierarchy, a replacement policy—typically a least-recently-used replacement policy—is employed to determine which cache locations should be utilized to store the new data. This process, often referred to as “updating” the cache, causes any modified data associated with the cache location selected by the replacement policy (also called a “victim”) to be written back to lower levels of the storage hierarchy. The process of writing modified data from a victim to system memory or a lower cache level is called a cast out or eviction.
Accessing system memory generally has a significantly longer latency than that associated with accessing any cache in the storage hierarchy. For example, accessing system memory may require up to four times as many processor cycles as are required to access a level three (L3) cache, and up to 10-15 times as many processor cycles as are required to access an L2 cache. Therefore, data evicted from a cache in any cache hierarchy level other than the lowest is conventionally written to the next lower level of the cache hierarchy rather than to system memory. For example, data cast out of an L2 cache is typically written to an L3 cache via a private bus between the L2 and L3 caches rather than writing the data all the way to system memory. Although latency for a particular operation is minimized in this fashion, such evictions have the effect of keeping the modified data within a localized portion of the storage hierarchy not generally accessible to other devices in a multiprocessor system.
In systems where data is evicted from an L2 cache to an L3 cache via a private bus connecting the two caches, error correction code (ECC) checking is required on the L3 directory and cache to insure that data integrity is preserved. This increases the number of bits required for the bus connecting the two caches. For example, if a 64 bit data bus is employed for transferring data between an L2 and L3 cache, an additional 8 bits may be required for ECC checking, resulting in a 72 bit bus. This larger bus consumes additional area within the silicon and may need to be operated at a lower frequency than the 64 bit bus.
It would be desirable, therefore, to be capable of evicting data from one cache level to a lower level cache without the requirement of a private bus between the two caches, or for ECC checking of data transfers between the two caches. It would further be advantageous to provide a mechanism for such data evictions which allowed the evictions to be visible to the snoop logic of other devices in a multiprocessor system.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to an improved method and apparatus for eviction of data from caches in a data processing system.
It is another object of the present invention to an improved method and apparatus for eviction of data from a cache in data processing system having a multilevel cache hierarchy.
It is yet another object of the present invention to an improved method and apparatus for eviction of data from one cache to a logically in line cache within a data processing system having a multilevel cache hierarchy.
The foregoing objects are achieved as is now described. In evicting data from a first cache in a level other than the lowest in a multilevel cache hierarchy, data is written to the system bus and snooped back into a second cache on a lower level in the cache hierarchy. The need for a private data path between the two caches is thus eliminated, and the second cache memory need not be dual-ported. The reload path employed for updating the second cache is reused to snoop cast-outs off the system bus. As a result of the first cache evicting data via the system bus, the second cache never contains data which is modified (M) with respect to system memory and other devices in a multiprocessor system get updated earlier. The need for error correction code (ECC) checking is eliminated, together with the associated additional bits, and may be replaced by simple parity checking. The bus into the second cache thus requires fewer bits, consumes less area, and may be operated at a higher frequency. When employed in conjunction with an H-MESI cache coherency protocol, horizontal devices go from the hovering (H) state to the shared (S) state faster.
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: 5537575 (1996-07-01), Foley et al.
patent: 5586298 (1996-12-01), Shah
patent: 5588131 (1996-12-01), Borrill
patent: 5822767 (1998-10-01), MacWilliams et al.
patent: 5832250 (1998-11-01), Whittaker
patent: 5860117 (1999-01-01), Cherabuddi
patent: 5875201 (1999-02-01), Bauman et al.
patent: 5900011 (1999-05-01), Saulsbury et al.
patent: 5918069 (1999-06-01), Matoba

Affiliated with

Also associated with

Rating

Deallocation with cache update protocol (L2 evictions) does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deallocation with cache update protocol (L2 evictions), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deallocation with cache update protocol (L2 evictions) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2604610