SAFARI Technical Report, TR-SAFARI-2011-009, Carnegie Mellon University, September 2011.
Vivek Seshadri, Onur Mutlu, Todd Mowry, Michael A. Kozuch*
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
*Intel Labs
With increasing pressure on memory bandwidth, there have been a number of proposals that improve the cache replacement policy. These mechanisms monitor the cache blocks while they are in the cache and evict blocks that are deemed to have low temporal locality. However, a majority of these mechanisms are agnostic to the temporal locality of a missed block and follow a single insertion policy for all incoming blocks. There is comparatively very little work on mechanisms to distinguish between missed blocks based on their temporal reuse behavior. Prior work has shown that distinguishing missed blocks based on their temporal locality and choosing the insertion policy on a per-block basis can significantly improve performance. To this end, we propose a new, simple hardware mechanism that predicts the temporal locality of a missed block before inserting it into the cache. The key insight behind the prediction scheme is that if a block with good temporal locality gets prematurely evicted from the cache, it will be accessed soon after eviction.
To implement this prediction scheme, our mechanism augments the conventional cache with a structure, victim tag store, that keeps track of addresses of blocks evicted from the cache. We provide a practical, low-complexity hardware implementation of our mechanism using Bloom filters. We qualitatively and quantitatively compare our mechanism to five different cache management mechanisms and show that it provides significant performance improvements.
FULL PAPER: pdf