Limited segmented LRU cache replacement algorithm with set aging for memory sensitive benchmarks
Cache memory replacement algorithms are an essential part of the memory hierarchy used to bridge the gap in speed between the CPU and main memory. The Segmented Least Recently Used (SLRU) algorithm is a variation of the popular Least Recently Used (LRU) algorithm. SLRU considers both when a line was accessed last and if it has been re-referenced while in the cache to make its eviction decision. This is achieved by dividing a cache set into two halves: the protected segment and the probationary segment. While SLRU has been shown to perform better than LRU, it has some shortcomings such as requiring a static ratio between the number of protected and probationary segments. In this work, we will first perform an in-depth analysis of SLRU to explore the effect of the protected and probationary segment sizes on performance and better understand its behavior. From there, we will propose two enhancements to SLRU: Limited SLRU (LSLRU) and Set Aging. These two enhancement allow the SLRU algorithm to adapt the segment ratio to the behavior of the current working set of benchmarks. Our work will focus on a subset of the SPEC2K6 benchmark suite that are considered memory sensitive. The hardware costs of both SLRU and the proposed algorithm will also be examined.