Method and apparatus for run-ahead victim selection to reduce undesirable replacement behavior in inclusive caches
View Patent ↗A method and apparatus for selecting and updating a replacement candidate in a cache is disclosed. In one embodiment, a cache miss may initiate the eviction of a present replacement candidate in a last-level cache. The cache miss may also initiate the selection of a future replacement candidate. Upon the selection of the future replacement candidate, the corresponding cache line may be invalidated in lower-level caches but remain resident in the last-level cache. The future replacement candidate may be updated by subsequent hits to the replacement candidate in the last-level cache prior to a subsequent cache miss.
1. An apparatus, comprising:
a multi-level cache memory including a lower-level cache and at least one higher-level cache, said lower-level cache located closer to a processor and having lower access latency than said higher-level cache;
a set control logic to identify a first replacement candidate within said higher-level cache responsive to a first cache miss to said higher-level cache, to invalidate a cache line corresponding to the first replacement candidate in the lower-level cache, and to evict said first replacement candidate only if there is a second cache miss to said first replacement candidate within said higher-level cache prior to an intervening cache hit to said first replacement candidate within said higher-level cache; and
a cache control logic to forward requests to system memory on a cache miss.
2. The apparatus of claim 1 , wherein said set control logic to identify a second replacement candidate within said higher-level cache when a cache hit to said first replacement candidate occurs prior to said second cache miss to said multi-level cache.
3. The apparatus of claim 2 , wherein said set control logic to send said cache line of said first replacement candidate to said lower-level cache.
4. The apparatus of claim 1 , wherein said set control logic to identify said first replacement candidate by a replacement method.
5. The apparatus of claim 4 , wherein said replacement method is a random method.
6. The apparatus of claim 4 , wherein said replacement method is a first-in-first-out method.
7. The apparatus of claim 4 , wherein said replacement method is a least-recently-used method.
8. The apparatus of claim 7 , wherein said set control logic to identify a second replacement candidate within said higher-level cache and to establish said first replacement candidate as most-recently-used when a cache hit to said first replacement candidate in said lower-level cache occurs prior to said second cache miss to said higher-level cache.
9. The apparatus of claim 8 , wherein said control logic to identify said second replacement candidate within said higher-level cache after said cache hit to said first replacement candidate in said higher-level cache occurs.
10. A method, comprising:
identifying a first replacement candidate within a higher-level cache of a multi-level cache memory after a first cache miss to said higher-level cache, said multi-level cache memory including said higher-level cache and at least one lower-level cache, said lower-level cache located closer to a processor and having lower access latency than said higher-level cache;
invalidating a cache line corresponding to said first replacement candidate in said lower-level cache; and
evicting said first replacement candidate from said higher-level cache only if there is a second cache miss to said first replacement candidate in said higher-level cache prior to an intervening cache hit to said first replacement candidate in said higher-level cache.
11. The method of claim 10 , further comprising identifying a second replacement candidate within said higher-level cache when a cache hit to said first replacement candidate within said higher-level cache occurs prior to said second cache miss to said multi-level cache.
12. The method of claim 11 , further comprising sending said cache line in response to said cache hit.
13. The method of claim 10 , wherein said identifying a first replacement candidate includes implementing a replacement method.
14. The method of claim 13 , wherein said replacement method determines said first replacement candidate by random selection.
15. The method of claim 13 , wherein said replacement method determines said first replacement candidate by implementing first-in-first-out.
16. The method of claim 13 , wherein said replacement method determines said first replacement candidate by determining a least-recently-used cache line.
17. The method of claim 13 , further comprising identifying a second replacement candidate within said higher-level cache and establishing said first replacement candidate as most-recently-used when a cache hit to said first replacement candidate in said higher-level cache occurs prior to said second cache miss.
18. The method of claim 17 , wherein said identifying a second replacement within said higher-level cache candidate occurs before said second cache miss.
19. system, comprising:
a multi-level cache memory having a lower-level cache and at least one higher-level cache, said lower-level cache located closer to a processor and having lower access latency than said higher-level cache;
a set control logic to identify a first replacement candidate within said higher-level cache responsive to a first cache miss to said higher-level cache, to invalidate a cache line corresponding to the first replacement candidate in the lower-level cache, and to evict said first replacement candidate only if there is a second cache miss to said first replacement candidate within said higher-level cache prior to an intervening cache hit to said first replacement candidate within said higher-level cache; and
a cache control logic to forward requests to system memory on a cache miss and
an audio input/output coupled to said multi-level cache memory.
20. The system of claim 19 , wherein said set control logic to identify a second replacement candidate within said higher-level cache when a cache hit to said first replacement candidate in said higher-level cache occurs prior to said second cache miss to said multi-level cache.
21. The system of claim 20 , wherein said set control logic to send said cache line of said first replacement candidate to said lower-level cache.
22. The system of claim 19 , wherein said set control logic to identify said first replacement candidate by a replacement method.
23. The system of claim 22 , wherein said replacement method is a random method.
24. The system of claim 22 , wherein said replacement method is a first-in-first-out method.
25. The system of claim 22 , wherein said replacement method is a least-recently-used method.
26. The system of claim 25 , wherein said set control logic to identify a second replacement candidate within said higher-level cache and to establish said first replacement candidate as most-recently-used when a cache hit to said first replacement candidate in said lower-level cache occurs prior to said second cache miss to said higher-level cache.
27. The system of claim 26 , wherein said control logic to identify said second replacement candidate after said cache hit to said first replacement candidate in said higher-level cache occurs.
28. An apparatus, comprising:
a multi-level cache memory including a lower-level cache and at least one higher-level cache, said lower-level cache located closer to a processor and having a lower access latency than said higher-level caches;
means for identifying a first replacement candidate within said higher-level cache after a first cache miss to a said higher-level cache;
means for invalidating a cache line corresponding to said first replacement candidate in said lower-level cache subsequent to said first cache miss; and
means for evicting said first replacement candidate from said higher-level cache only if there is a second cache miss to said first replacement candidate in said higher-level cache prior to an intervening cache hit to said first replacement candidate in said higher-level cache.
29. The apparatus of claim 28 , further comprising means for identifying a second replacement candidate within said higher-level cache when a cache hit to said first replacement candidate in said higher-level cache occurs prior to said second cache miss to said higher-level cache.
30. The apparatus of claim 29 , further comprising means for sending said cache line to said lower-level cache in response to said cache hit.
31. The apparatus of claim 28 , wherein said means for identifying a first replacement candidate includes means for implementing a replacement method.
32. The apparatus of claim 31 , wherein said replacement method includes means for determining said first replacement candidate by random selection.
33. The apparatus of claim 31 , wherein said replacement method includes means for determining said first replacement candidate by implementing first-in-first-out.
34. The apparatus of claim 31 , wherein said replacement method includes means for determining said first replacement candidate by determining a least-recently-used cache line.
35. The apparatus of claim 34 , further comprising means for identifying a second replacement candidate within said higher-level cache and means for establishing said first replacement candidate as most-recently-used when a cache hit to said first replacement candidate in said higher-level cache occurs prior to said second cache miss.
36. The method of claim 35 , wherein said means for identifying a second replacement candidate performs its identification after said cache hit to said first replacement candidate in said higher-level cache.