LIRS2: An Improved LIRS Replacement Algorithm
View/ Open
Date
2021-07-02Author
Zhong, Chen
Zhao, Xingsheng
Jiang, Song
Metadata
Show full item recordAbstract
A block replacement algorithm keeps receiving attention on
improvement of its hit ratio. Many replacement algorithms
have been proposed, among which LIRS stands out with its
consistently higher hit ratio across various workloads with
low time and space overheads. However, there are still access
patterns where LIRS produces sub-optimal hit ratio and has
room for further improvement.
In this paper, we replace the locality measure used by LIRS,
the reuse distance, with a more stable and thus more reliable
measure, to predict future access time. The new measure is
the sum of a block’s two recent consecutive reuse distances.
It addresses the issue with the reuse distance, which is more
likely to fluctuate and mislead replacement decisions. We
proposed LIRS2 by incorporating this new measure into the
LIRS algorithm to reduce its miss ratio. We further propose
a replacement design that allows a responsive adaptation
between LIRS2 and LRU so that LRU-friendly access patterns
can be well accommodated. We have implemented LIRS2 and
its adaptive variant. With extensive experiments on traces
from different sources, we show that the algorithms can
consistently improve cache miss ratio with low overheads