A table-based method for single-pass cache optimization

ABSTRACT

Due to the large contribution of the memory subsystem to total system power, the memory subsystem is highly amenable to customization for reduced power/energy and/or improved performance. Cache parameters such as total size, line size, and associativity can be specialized to the needs of an application for system optimization. In order to determine the best values for cache parameters, most methodologies utilize repetitious application execution to individually analyze each configuration explored. In this paper we propose a simplified yet efficient technique to accurately estimate the miss rate of many different cache configurations in just one single-pass of execution. The approach utilizes simple data structures in the form of a multi-layered table and elementary bitwise operations to capture the locality characteristics of an application's addressing behavior. The proposed technique intends to ease miss rate estimation and reduce cache exploration time.

REFERENCES

• 1: N.B.A. Milenkovic, M. Milenkovic. A performance evaluation of memory hierarchy in embedded systems. In Proceedings of the 35th Southeastern Symposium on System Theory, pages 427--431, March 2003.
• 2: D.H. Albonesi. Selective cache ways: On-demand cache resource allocation. Journal of Instruction-Level Parallelism, 2, May 2000.
• 3: E. Berg , E. Hagersten, StatCache: a probabilistic approach to efficient and accurate data locality analysis, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.20-27, March 10-12, 2004
• 4: Gunnar Braun , Andreas Wieferink , Oliver Schliebusch , Rainer Leupers , Heinrich Meyr , Achim Nohl, Processor/Memory Co-Exploration on Multiple Abstraction Levels, Proceedings of the conference on Design, Automation and Test in Europe, p.10966, March 03-07, 2003
• 5: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 6: Arijit Ghosh , Tony Givargis, Analytical Design Space Exploration of Caches for Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10650, March 03-07, 2003
• 7: Ann Gordon-Ross , Frank Vahid, A self-tuning configurable cache, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278537]
• 8: Ann Gordon-Ross , Frank Vahid , Nikil Dutt, Fast configurable-cache tuning with a unified second-level cache, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077681]
• 9: Ann Gordon-Ross , Pablo Viana , Frank Vahid , Walid Najjar , Edna Barros, A one-shot configurable-cache tuner for improved energy and performance, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 10: S. Gosh, M. Martonosi, and S. Malik. Cache miss equations: An analytical representation of cache misses. In In the Proceedings of the Workshop on Interaction between Compilers and Computer Architectures (HPCA-3), 1997.
• 11: K. Grimsrud , J. Archibald , R. Frost , B. Nelson, Locality As a Visualization Tool, IEEE Transactions on Computers, v.45 n.11, p.1319-1326, November 1996 [doi>10.1109/12.544490]
• 12: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 13: Andhi Janapsatya , Aleksandar Ignjatović , Sri Parameswaran, Finding optimal L1 cache configuration for embedded systems, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118482]
• 14: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 15: R.L. Mattson, J. Gecsei, D.R. Slutz, and I.L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 16: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 17: S. Segars. Low-power design techniques for microprocessors. In ISSCC'01: International Solid State Circuits Conference, San Francisco, CA, USA, 2001. IEEE Computer Society.
• 18: R. Sugumar and S. Abraham. Efficient simulation of multiple cache configurations using binomial trees. In Technical Report CSE-TR-111-91., 1991.
• 19: Chuanjun Zhang , Frank Vahid , Roman Lysecky, A Self-Tuning Cache Architecture for Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.10142, February 16-20, 2004
• 20: Chuanjun Zhang , Frank Vahid , Walid Najjar, A highly configurable cache for low energy embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.2, p.363-387, May 2005 [doi>10.1145/1067915.1067921]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**

General Terms:
Algorithms

Keywords:
cache optimization, configurable cache tuning, low energy