Simple penalty-sensitive replacement policies for caches

ABSTRACT

Classic cache replacement policies assume that miss costs are uniform. However, the correlation between miss rate and cache performance is not as straightforward as it used to be. Ultimately, the true cost measure of a miss should be the penalty, i.e. the actual processing bandwidth lost because of the miss. It is known that, contrary to loads, the penalty of stores is mostly hidden in modern processors. To take advantage of this observation, we propose simple schemes to replace load misses by store misses. We extend classic replacement algorithms such as LRU (Least Recently Used) and PLRU (Partial LRU) to reduce the aggregate miss penalty instead of the miss count.One key issue is to predict the next access type to a block, so that higher replacement priority is given to blocks that will be accessed next with a store. We introduce and evaluate various prediction schemes based on instructions, and broadly inspired from branch predictors. To guide the design we run extensive trace-driven simulations on eight Spec95 benchmarks with a wide range of cache configurations and observe that our simple penalty-sensitive policies yield positive load miss improvements over classic algorithms across most the benchmarks and cache configurations. In some cases the improvements are very large.

REFERENCES

• 1: Santosh G. Abraham , Rabin A. Sugumar , Daniel Windheiser , B. R. Rau , Rajiv Gupta, Predictability of load/store instruction latencies, Proceedings of the 26th annual international symposium on Microarchitecture, p.139-152, December 01-03, 1993, Austin, Texas, United States
• 2: Burger, D., and Austin, T., The SimpleScalar Tool Set, Version 2.0. Computer Sciences Dept. Tech. Report #1342, Univ. of Wisconsin-Madison, June 1997.
• 3: Tien-Fu Chen, Data prefetching for high-performance processors, University of Washington, Seattle, WA, 1993
• 4: Jamison D. Collins , Dean M. Tullsen, Hardware identification of cache conflict misses, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.126-135, November 16-18, 1999, Haifa, Israel
• 5: John W. C. Fu , Janak H. Patel , Bob L. Janssens, Stride directed prefetching in scalar processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.102-110, December 01-04, 1992, Portland, Oregon, United States
• 6: 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]
• 7: Jaeheon Jeong , Michel Dubois, Optimal replacements in caches with two miss costs, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.155-164, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305636]
• 8: Jaeheon Jeong , Michel Dubois, Cost-sensitive cache replacement algorithms, 2002
• 9: Jaeheon Jeong , Michel Dubois, Cost-Sensitive Cache Replacement Algorithms, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.327, February 08-12, 2003
• 10: 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
• 11: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 12: Stefanos Kaxiras , James R. Goodman, Improving CC-NUMA Performance Using Instruction-Based Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.161, January 09-12, 1999
• 13: An-Chow Lai , Babak Falsafi, Selective, accurate, and timely self-invalidation using last-touch prediction, Proceedings of the 27th annual international symposium on Computer architecture, p.139-148, June 2000, Vancouver, British Columbia, Canada
• 14: Farnaz Mounes-Toussi , David J. Lilja, The Effect of using State-Based Priority Information in a Shared-Memory Multiprocessor Cache Replacement Policy, Proceedings of the 1998 International Conference on Parallel Processing, p.217-224, August 10-14, 1998
• 15: Todd Carl Mowry, Tolerating latency through software-controlled data prefetching, Stanford University, Stanford, CA, 1995
• 16: Shubhendu S. Mukherjee , Mark D. Hill, Using prediction to accelerate coherence protocols, Proceedings of the 25th annual international symposium on Computer architecture, p.179-190, June 27-July 02, 1998, Barcelona, Spain
• 17: Seznec, A., and Lloansi, F., About Effective Cache Miss Penalty on Out-of-Order Superscalar Processors. IRISA Report #970, Nov. 1995.
• 18: Kevin Skadron , Douglas W. Clark, Design Issues and Tradeoffs for Write Buffers, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.144, February 01-05, 1997
• 19: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 20: Kimming So , Rudolph N. Rechtschaffen, Cache Operations by MRU Change, IEEE Transactions on Computers, v.37 n.6, p.700-709, June 1988 [doi>10.1109/12.2208 ]
• 21: Srikanth T. Srinivasan , Roy Dz-ching Ju , Alvin R. Lebeck , Chris Wilkerson, Locality vs. criticality, Proceedings of the 28th annual international symposium on Computer architecture, p.132-143, June 30-July 04, 2001, Göteborg, Sweden
• 22: Standard Performance Evaluation Corporation, http:// www.specbench.org.
• 23: Per Stenström , Mats Brorsson , Lars Sandberg, An adaptive cache coherence protocol optimized for migratory sharing, Proceedings of the 20th annual international symposium on Computer architecture, p.109-118, May 16-19, 1993, San Diego, California, United States
• 24: Harold S. Stone, High-performance computer architecture (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 25: 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
• 26: Wong, W., and Baer, J., Modified LRU Policies for Improving Second-Level Cache Behavior. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture, Jan. 2000, 49--60.
• 27: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
cache, memory system, penalty, replacement policy