Self-correcting LRU replacement policies

ABSTRACT

L1 caches must be fast and have a good hit rate at the same time. To be fast, they must remain small. To have a good hit rate, they must be set-associative. With wider associativity the replacement algorithm becomes critical. The wide performance gap between OPT, the optimum off-line algorithm, and LRU suggests that LRU still makes too many mistakes. One way to improve L1 cache behavior is to manage actively the replacement policy to correct these mistakes on the fly.We introduce Self-correcting LRU (SCLRU) which is based on LRU augmented with a feedback loop to constantly monitor and correct replacement mistakes. It relies on several mechanisms to detect, predict, and correct bad replacement decisions. We identify three types of mistakes made by LRU and associate them with memory-access instructions. Our goal is to prevent a mistake to occur more than once. Based on evaluations using a set of seven SPEC95 benchmarks, we show that our approach achieves significant and reliable miss rate improvements, sometimes close to that of OPT, for 2-way and 4-way L1 caches and can do this at a low implementation cost and without affecting the hit cycle time.

REFERENCES

• 1: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 2: L. Belady. A Study of Replacement Algorithms for a Virtual-Storage Computer. In IBM Systems Journal, v. 5, no. 2, pp. 78--101, 1966.
• 3: D. Burger, Doug and T. M. Austin,. The SimpleScalar Tool Set, Version 2. University of Wisconsin-Madison Computer Science Department, TN-1342, 1997.
• 4: 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]
• 5: J. Jalminger and P. Stenstrom. A Novel Approach to Cache Reuse Prediction. In Proceedings of 32nd International Parallel Processing Conference (ICPP-2003). Oct. 2003.
• 6: Teresa L. Johnson , Daniel A. Connors , Matthew C. Merten , Wen-mei W. Hwu, Run-Time Cache Bypassing, IEEE Transactions on Computers, v.48 n.12, p.1338-1354, December 1999 [doi>10.1109/12.817393]
• 7: Teresa L. Johnson , Wen-mei W. Hwu, Run-time adaptive cache hierarchy management via reference analysis, Proceedings of the 24th annual international symposium on Computer architecture, p.315-326, June 01-04, 1997, Denver, Colorado, United States
• 8: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 9: M. Karlsson and E. Hagersten, "Timestamp-based Selective Cache Allocation", High Performance Memory Systems, edited by H. Hadimiouglu, D. Kaeli, J. Kuskin, A. Nanda, and J. Torrellas, Springer-Verlag, 2003.
• 10: Exploration of the Spatial Locality on Emerging Applications and the Consequences for Cache Performance, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.163, May 01-05, 2000
• 11: An-Chow Lai , Cem Fide , Babak Falsafi, Dead-block prediction & dead-block correlating prefetchers, Proceedings of the 28th annual international symposium on Computer architecture, p.144-154, June 30-July 04, 2001, Göteborg, Sweden
• 12: R. L. Mattson, J. Gecsei, D. R. Slutz and I. L. Traiger. Evaluation Techniques for Storage Hierarchies. In IBM Systems Journal, vol. 9, pp. 77--117, 1970.
• 13: V. Milutinovic, B. Markovic, M. Tomasevic, and M. Tremblay. The Split Temporal/Spatial Cache: Initial Performance analysis. In Proceedings of SCIzzL-5, pp. 63--70, March 1996.
• 14: M. Prvulovic, D. Marinov, Z. Dimitrijevic, and V. Milutinovic. Split Temporal/Spatial Cache: A Survey and Reevaluation of Performance, IEEE TCCA Newsletter, pp. 1--10, 1999.
• 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: Standard Performance Evaluation Corporation. http://www.spec.org. SPEC 95. August 1995.
• 17: H. S. Stone. High Performance Computer Architecture. Addison-Wesley 1993 (3rd ed.).
• 18: Edward S. Tam , Jude A. Rivers , Vijayalakshmi Srinivasan , Gary S. Tyson , Edward S. Davidson, Active Management of Data Caches by Exploiting Reuse Information, IEEE Transactions on Computers, v.48 n.11, p.1244-1259, November 1999 [doi>10.1109/12.811113]
• 19: Gary Tyson , Matthew Farrens , John Matthews , Andrew R. Pleszkun, A modified approach to data cache management, Proceedings of the 28th annual international symposium on Microarchitecture, p.93-103, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 20: Wayne A. Wong and Jean-Loup Baer. Modified LRU Policies for Improving Second-level Cache Behavior. In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, pp. 49--60, January 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Microprocessors

General Terms:
Algorithms, Experimentation, Performance

Keywords:
LRU algorithms, mistake prediction, shadow directories