``Making LRU friendly to weak locality workloads: a novel replacement algorithm to improve buffer cache performance" Song Jiang and Xiaodong Zhang IEEE Transactions on Computers, Vol. 54, No. 8, 2005, pp. 939-952. Abstract Although the LRU replacement has been widely used in buffer cache management, it is well-known for its inability to cope with access patterns with weak locality. Previously proposed algorithm to improve LRU greatly increase complexity and/or cannot provide consistently improved performance. Some of the algorithm only address LRU problems on certain specific and predefined cases. Motivated by the limitations of existing algorithms, we propose a general and efficient replacement algorithm, called Low Inter-reference Recency Set (LIRS). LIRS effectively addresses the limitations of LRU by using recency to evaluate Inter-Reference Recency (IRR) of accessed blocks for making a replacement decision. This is contrast to what LRU does: directly using recency to predict the next reference time. Meanwhile, LIRS mostly retains the simple assumption adopted by LRU for predicting future block access behaviors. Conducting simulations with a variety of traces of difference access patterns and with a wide range of cache sizes, we show that LIRS significantly outperforms LRU and outperforms other existing replacement algorithms in most cases. Furthermore, we show that the additional cost for implementing LIRS is trivial in comparison with that of LRU. We also show that the LIRS algorithm can be extended into a familty of replacement algorithms, in which LRU is a special member.Back to the Publication Page.
Back to the HPCS Main Page at the Ohio State University.