Improved indexing for cache miss reduction in embedded systems

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=log2(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 an optimal set of bits used as index into the cache. This technique does not add any overhead in terms of area or delay. We give 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.

REFERENCES

• 1: Technology Roadmap for Semiconductors. <http://www.itrs.net>.
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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]
• 10: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 11: 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
• 12: Arnout Vandecappelle , Miguel Miranda , Erik Brockmeyer , Francky Catthoor , Diederik Verkest, Global multimedia system design exploration using accurate memory organization feedback, Proceedings of the 36th ACM/IEEE conference on Design automation, p.327-332, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309945]
• 13: Gabriel Rivera , Chau-Wen Tseng, Compiler optimizations for eliminating cache conflict misses, University of Maryland at College Park, College Park, MD, 1997
• 14: 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
• 15: M. Waldvogel, et al. Scalable High Speed IP Routing Lookups. ACM Special Interest Group on Data Communication, 1997.
• 16: S. Nilsson , G. Karlsson, Fast address look-up for internet routers, Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications, p.11-22, April 01-03, 1998
• 17: Eitan M. Gurari, An Introduction to the Theory of Computation, W. H. Freeman & Co., New York, NY, 1989
• 18: SPEC CPU 2000. <http://www.spec.org>.
• 19: D. Burger, T.M. Austin, The SimpleScalar Tool Set, Version 2.0. University of Wisconsin-Madison Computer Sciences Department Technical Report #1342, June 1997.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cache optimization, design space exploration, index hashing