A first look at the interplay of code reordering and configurable caches

ABSTRACT

The instruction cache is a popular target for optimizations of microprocessor-based systems because of the cache's high impact on system performance and power, and because of the cache's predictable temporal and spatial locality. Optimization techniques can be designed based on this predictability. We explore for the first time the interplay of two popular instruction cache optimization techniques: the long-known technique of code reordering and the relatively-new technique of cache configuration. We address the question of whether those two optimizations complement each other or if one optimization dominates the other. Through experiments using embedded system benchmarks, we show that cache configuration dominates a particular category of code reordering techniques with respect to optimizing performance and energy, obviating the need for reordering. We also examine the modern scenario of synthesized custom caches, and show that combining cache configuration with code reordering results in cache size reductions of 13% on average, and up to 89% in some benchmarks, beyond just cache configuration alone.

REFERENCES

• 1: Albonesi, D.H. Selective cache ways: on demand cache resource allocation. Journal of Instruction Level Parallelism, May 2002.
• 2: Altera, Nios Embedded Processor System Development, http://www.altera.com/corporate/news_room/releases/products/nr-nios_delivers_goods.html
• 3: Arc International, www.arccores.com
• 4: ARM, www.arm.com
• 5: Brad Calder , Dirk Grunwald, Reducing branch costs via branch alignment, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.242-251, October 05-07, 1994, San Jose, California, United States
• 6: Cohn, R., Goodwin, P., Lowney, G., Rubin, N. Spike: an optimizer for Alpha/NT executables. in USENIX Windows NT Workshop, August 1997.
• 7: Cohn. R., Lowney, P.G. Design and analysis of profile-based optimization in Compaq's compilation tools for Alpha. Journal of Instruction Level Parallelism, vol. 2, May 2000.
• 8: Dinero IV, http://www.cs.wisc.edu/~markhill/DineroIV/
• 9: EEMBC, the Embedded Microprocessor Benchmark Consortium, www.eembc.org.
• 10: Nikolas Clemens Gloy , Michael D. Smith, Code placement using temporal profile information, 1998
• 11: Nikolas Gloy , Trevor Blackwell , Michael D. Smith , Brad Calder, Procedure placement using temporal ordering information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.303-313, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: Ann Gordon-Ross , Frank Vahid , Nikil Dutt, Automatic Tuning of Two-Level Caches to Embedded Applications, Proceedings of the conference on Design, automation and test in Europe, p.10208, February 16-20, 2004
• 13: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 14: Lee, D., Baer, J., Bershad, B., Anderson, T. Reducing startup latency in web and desktop applications. In Windows NT Symposium, July 1999.
• 15: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: 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]
• 17: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 18: MIPS Technologies, www.mips.com
• 19: Moseley, P., Debray, S., Andrews, G. Checking program profiles. Third IEEE International Workshop of Source Code Analysis and Manipulation, September 2003.
• 20: Robert Muth , Saumya K. Debray , Scott Watterson , Koen De Bosschere, Alto: a link-time optimizer for the Compaq alpha, Software—Practice & Experience, v.31 n.1, p.67-101, Jan. 2001 [doi>10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A]
• 21: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 22: Reinman, G., Jouppi, N.P. Cacti2.0: an integraded cache timing and power model. COMPAQ Western Research Lab, 1999.
• 23: Romer, T., Voelker, G., Lee, D., Wolman, A., Wong, W., Levy, H., Bershad, B., Chen, B. Instrumentation and optimization of Win32/Intel executables using ETCH. In USENIX Windows NT Workshop, August 1997.
• 24: Alan D Samples , Paul N. Hilfinger, Code Reorginazation for Instruction Caches, University of California at Berkeley, Berkeley, CA, 1988
• 25: Scales, D.J. Efficient dynamic procedure placement. Technical Report WRL-98/5, Compaq WRL Research Lab, May 1998.
• 26: Scales, D.J., Randall, K.H, Ghemawat, S., Dean, J. The swift java compiler: design and implementation. Technical Report 2000/2, Compaq Western Research Laboratory, Apr. 2000.
• 27: Scharz, B., Debray, S., Andrews, G., Legendre, M. PLTO: a link-time optimizer for the Intel IA-32 architecture. Proc. 2001 Workshop on Binary Translation (WBT-2001), Sept. 2001.
• 28: Silicon Graphics Inc, Cord manual page. IRIX 5.3.
• 29: Srivastava, A., Wall,D. A practical system for intermodule code optimization at link-time. Technical Report 92/6. Digital Western Rearch Labrartory. June 1992.
• 30: 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]
• 31: Tensilica, Xtensa Processor Generator, http://www.tensilica.com/.
• 32: Chuanjun Zhang , Frank Vahid, Cache Configuration Exploration on Prototyping Platforms, Proceedings of the 14th IEEE International Workshop on Rapid System Prototyping (RSP'03), p.164, June 09-11, 2003
• 33: Chuanjun Zhang , Frank Vahid , Walid Najjar, A highly configurable cache architecture for embedded systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 34: 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

INDEX TERMS

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

General Terms:
Design

Keywords:
architecture tuning, cache exploration, cache hierarchy, cache optimization, code layout, code reordering, code reorganization, configurable cache, low energy, low power