Zero cost indexing for improved processor cache performance

ABSTRACT

The increasing use of microprocessor cores in embedded systems as well as mobile and portable devices creates an opportunity for customizing the cache subsystem for improved performance. In traditional cache design, the index portion of the memory address bus consists of the K least significant bits, where K = log₂ D and D is the depth of the cache. However, in devices where the application set is known and characterized (e.g., systems that execute a fixed application set) there is an opportunity to improve cache performance by choosing a near-optimal set of bits used as index into the cache. This technique does not add any overhead in terms of area or delay. In this article, we present an efficient heuristic algorithm for selecting K index bits for improved cache performance. We show the feasibility of our algorithm by applying it to a large number of embedded system applications as well as the integer SPEC CPU 2000 benchmarks. Specifically, for data traces, we show up to 45% reduction in cache misses. Likewise, for instruction traces, we show up to 31% reduction in cache misses. When a unified data/instruction cache architecture is considered, our results show an average improvement of 14.5% for the Powerstone benchmarks and an average improvement of 15.2% for the SPEC'00 benchmarks.

REFERENCES

• 1: Jaume Abella, Near-Optimal Loop Tiling by Means of Cache Miss Equations and Genetic Algorithms, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.568, August 18-21, 2002
• 2: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Peter Grun , Nikil Dutt , Alex Nicolau, Memory aware compilation through accurate timing extraction, Proceedings of the 37th conference on Design automation, p.316-321, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337428]
• 6: Peter Grun , Nikil D. Dutt , Alexandru Nicolau, Aggressive Memory-Aware Compilation, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.147-151, November 12, 2000
• 7: Eitan M. Gurari, An Introduction to the Theory of Computation, W. H. Freeman & Co., New York, NY, 1989
• 8: Huang, Q., Xue, J., and Vera, X. 2003. Code tiling for improving the cache performance of pde solvers. In Proceedings of the International Conference on Parallel Processing. ACM, New York, 615--626.
• 9: ITRS. 2005. Technology roadmap for semiconductors. http://www.itrs.com.
• 10: Christoforos E. Kozyrakis , David A. Patterson, A New Direction for Computer Architecture Research, Computer, v.31 n.11, p.24-32, November 1998 [doi>10.1109/2.730733]
• 11: 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]
• 12: Preeti Ranjan Panda , Hiroshi Nakamura , Nikil D. Dutt , Alexandru Nicolau, Improving cache Performance Through Tiling and Data Alignment, Proceedings of the 4th International Symposium on Solving Irregularly Structured Problems in Parallel, p.167-185, June 12-13, 1997
• 13: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 14: Peter Petrov , Alex Orailğlu, Towards effective embedded processors in codesigns: customizable partitioned caches, Proceedings of the ninth international symposium on Hardware/software codesign, p.79-84, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371687]
• 15: PowerStone. 1999. The powerstone benchmarks. www.motorola.com.
• 16: Gabriel Rivera , Chau-Wen Tseng, Compiler optimizations for eliminating cache conflict misses, University of Maryland at College Park, College Park, MD, 1997
• 17: SPEC'00. Spec cpu 2000. http://www.spec.org.
• 18: Ching-Long Su , Alvin M. Despain, Cache design trade-offs for power and performance optimization: a case study, Proceedings of the 1995 international symposium on Low power design, p.63-68, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224093]
• 19: Kazumasa Suzuki , Tomohisa Arai , Kouhei Nadehara , Ichiro Kuroda, V830R/AV: Embedded Multimedia Superscalar RISC Processor, IEEE Micro, v.18 n.2, p.36-47, March 1998 [doi>10.1109/40.671401]
• 20: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 21: Frank Vahid , Tony Givargis, The case for a configure-and-execute paradigm, Proceedings of the seventh international workshop on Hardware/software codesign, p.59-63, March 1999, Rome, Italy [doi>10.1145/301177.301211]
• 22: Wong, S., Vassiliadis, S., and Cotofana, S. 2004. Future directions of (programmable and reconfigurable) embedded processors. In Domain-Specific Processors: Systems, Architecture, Modeling, and Simulation. Marcel Dekker, Inc., London, UK, 235--257.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General

General Terms:
Design, Performance

Keywords:
Cache optimization, design exploration, index hashing