A low-cost usage-based replacement algorithm for cache memories
Yannick Deville · ACM SIGARCH Computer Architecture News · 1990
Mainly three replacement policies have been used in cache memories : LRU, FIFO and random. LRU achieves higher performance by being usage-based, i.e., by storing the order of the accesses to the cache blocks in order to remove the blocks that have remained unused for the longest period, However, storing this status results in a complex implementation. On the opposite, FIFO and random are non-usage-based ; their implementation is simpler, but their performance is lower. This paper presents the SIDE policy, which achieves a trade-off between the above features : by being usage-based, it yields almost the same performance as LRU. However, it is implemented almost in the same way as FIFO which yields simplicity and makes it easy to design a cache chip performing SIDE or FIFO replacement, depending on the mode chosen.