Counter-based cache replacement algorithms

Citations Over TimeTop 10% of 2006 papers

Abstract

Recent studies have shown that in highly associative caches, the performance gap between the least recently used (LRU) and the theoretical optimal replacement algorithms is large, suggesting that alternative replacement algorithms can improve the performance of the cache. One main reason for this performance gap is that in the LRU replacement algorithm, a line is only evicted after it becomes the LRU line, long after its last access/touch, while unnecessarily occupying the cache space for a long time. This paper proposes a new approach to deal with the problem: counter-based L2 cache replacement. In this approach, each line in the L2 cache is augmented with an event counter that is incremented when an event of interest, such as a cache access to the same set, occurs. When the counter exceeds a threshold, the line "expires", and becomes evictable. When expired lines are evicted early from the cache, they make extra space for lines that may be more useful, reducing the number of capacity and conflict misses. Each line's threshold is unique and is dynamically learned and stored in a small 40-Kbyte counter prediction table. We propose two new replacement algorithms: access interval predictor (AIP) and live-time predictor (LvP). AIP and LvP speed up 10 (out of 21) SPEC2000 benchmarks by up to 40% and 11% on average.

Related Papers

• → Exact and fast L1 cache simulation for embedded systems(2009)26 cited
• → BIG Cache Abstraction for Cache Networks(2017)13 cited
• → A novel cache mapping scheme for dynamic set-based cache partitioning(2009)4 cited
• → A GA-based low-power Cache Partitioning algorithm for multi-programmed systems(2013)1 cited
• → Reducing cache conflicts by multi-level cache partitioning and array elements mapping(2002)1 cited