A new hybrid approach to exploit localities: LRFU with adaptive prefetching

ABSTRACT

This paper reviewed a number of existing methods to exploit the spatial and temporal locality commonly existing in programs, and provided detailed analysis and testing of adaptive prefetching (a method designed to utilize spatial locality) and the least recently and frequently used (LRFU) method (a method designed to utilize temporal locality). The two methods were combined in this work in terms of their exploitation of locality. The comparative studies of the methods were done using real traces, and hit rate was used as an evaluation measure.Results showed that by using adaptive prefetching, the hit rate improved significantly by an average of 11.7% over the hit rate of LRU in the traces and cache configurations used. It also showed that LRFU consistently gives higher hit rates than LRU, but not by much in the trace files and cache configurations tested. And the X value (a controllable parameter which determines the Weights given to recency and frequency) has to be in a certain range, which is usually narrow, in order to get the best performance for hit rate. Compared to adaptive prefetching and LRU, the hybrid approach of combining adaptive prefetching and LRFU gave a consistently higher hit rate also. But, affected by the performance of LRFU, the improvement in the hit rate by the combination was low.

REFERENCES

• 1: J. P. Casmira and D. R Kaeli, "Modeling Cache Pollution", International Journal of Modeling and Simulation, Vol. 19, No. 2, pp. 132--138, May 1998.
• 2: E. Cohen, H. Kaplan and U. Zwick. "Competitive Analysis of the LRFU Paging Algorithm", Algorithmica Vol. 33, No. 4, pp. 511--516, August 2002.
• 3: Antonio González , Carlos Aliagas , Mateo Valero, A data cache with multiple caching strategies tuned to different types of locality, Proceedings of the 9th international conference on Supercomputing, p.338-347, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224622]
• 4: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 5: Teresa L. Johnson , Matthew C. Merten , Wen-Mei W. Hwu, Run-time spatial locality detection and optimization, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.57-64, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 6: Ramakrishna Karedla , J. Spencer Love , Bradley G. Wherry, Caching strategies to improve disk system performance, Computer, v.27 n.3, p.38-46, March 1994 [doi>10.1109/2.268884]
• 7: Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.134-143, May 01-04, 1999, Atlanta, Georgia, United States
• 8: V. Milutinovic, M. Tomasevic, B. Markovi, and M. Tremblay, "A New Cache Architecture Concept: The Split Temporal/Spatial Cache", Proceedings of 8th Mediterranean Electrotechnical Conference, Vol. 2, pp. 1108--1111, Bari, Italy, May 1996.
• 9: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 10: R. Pendse and U. Walterscheidt, "A Fuzzy Block Replacement Algorithm for Disk Caches", Proceedings of 1996 Midwest Symposium on Circuits and Systems, Vol. 3, pp. 995--998, Ames, Iowa, August 1996.
• 11: Ravi Pendse , Ravi Bhagavathula, Performance of LRU Block Replacement Algorithm with Pre-Fetching, Proceedings of the 1998 Midwest Symposium on Systems and Circuits, p.86, August 09-12, 1998
• 12: R. Pendse and R. Bhagavathula, "Prefetch with the Segmented LRU Algorithm", Proceeding of the 42nd Midwest Symposium on Circuits and Systems, Vol. 2, pp. 862--865, Las Cruces, NM, August 1999.
• 13: J. Pomerene, T. R. Puzak, R. Rcchtschaffen, and F. Sporacio, "Prefetching System for a Cache Having a Second Directory for Sequentially Accessed Blocks", US Patent, Patent Number: 4807110, Feburary 21, 1989.
• 14: A. J. Smith, "Sequential Program Prefetehing in Memory Hierarchies", IEEE Computer, Vol. 11, No. 12, pp. 7--21, December 1978.
• 15: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 16: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 17: W. A. Wong and J. L. Baer, "Modified LRU Policies for Improving Second-Level Cache Behavior", Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, pp. 49--60, Toulouse, France, January 2000.