Design space optimization of embedded memory systems via data remapping

ABSTRACT

In this paper, we provide a novel compile-time data remapping algorithm that runs in linear time. This remapping algorithm is the first fully automatic approach applicable to pointer-intensive dynamic applications. We show that data remapping can be used to significantly reduce the energy consumed as well as the memory size needed to meet a user-specified performance goal (i.e., execution time) -- relative to the same application executing without being remapped. These twin advantages afforded by a remapped program -- reduced cache size and energy needs -- constitute a key step in a framework for design space exploration: for any given performance goal, remapping allows the user to reduce the primary and secondary cache size by 50%, yielding a concomitant energy savings of 57%. Additionally, viewed as a compiler optimization for a fixed processor, we show that remapping improves the energy consumed by the cache subsystem by 25%. All of the above savings are in the context of the cache subsystem in isolation. We also show that remapping yields an average 20% energy saving for an ARM-like processor and cache subsystem. All of our improvements are achieved in the context of DIS, Olden and SPEC2000 pointer-centric benchmarks.

REFERENCES

• 1: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 2: Chidamber Kulkarni , Francky Catthoor , Hugo De Man, Advanced Data Layout Optimization for Multimedia Applications, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.186-193, May 01-05, 2000
• 3: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 4: John B. Carter , Wilson C. Hsieh , Mark R. Swanson , Lixin Zhang , Erik Brunvand , Al Davis , Chen-Chi Kuo , Ravindra Kuramkote , Michael Parker , Lambert Schaelicke , Leigh Stoller , Terry Tateyama, Memory System Support for Irregular Applications, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.17-26, May 28-30, 1998
• 5: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 6: L. N. Chakrapani , P. Korkmaz , V. J. Mooney, III , K. V. Palem , K. Puttaswamy , W. F. Wong, The emerging power crisis in embedded processors: what can a poor compiler do?, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502246]
• 7: L. Chakrapani, K. Palem, and W. Wong. Triceps: Enhancing the trimaran compiler infrastructure for strongarm code generation. Technical Report CREST-TR-01-001, Georgia Institute of Technology, May 2001
• 8: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 10: 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
• 11: Data-Intensive Systems benchmark suite. www.aaec.com/projectweb/dis/
• 12: Milind B. Kamble , Kanad Ghose, Analytical energy dissipation models for low-power caches, Proceedings of the 1997 international symposium on Low power electronics and design, p.143-148, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263310]
• 13: Thomas Kistler , Michael Franz, Automated data-member layout of heap objects to improve memory-hierarchy performance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.490-505, May 2000 [doi>10.1145/353926.353937]
• 14: P. Korkmaz, K. Puttaswamy, and V. Mooney. Energy modeling of a processor core using synopsys and of the memory hierarchy using the kamble and ghose model. Technical Report CREST-TR-02-002, Georgia Institute of Technology, Feb. 2002
• 15: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 16: Olden benchmark suite. www.cs.princeton.edu/~mcc/olden.html
• 17: K. Palem and R. Rabbah. Data remapping for design space optimization of embedded cache systems. Technical Report GIT-CC-02-10, Georgia Institute of Technology, Mar. 2002
• 18: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 19: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory data organization for improved cache performance in embedded processor applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.384-409, Oct. 1997 [doi>10.1145/268424.268464]
• 20: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 21: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.682-704, July 2000 [doi>10.1145/348019.348570]
• 22: Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.101-112, January 16-18, 2002, Portland, Oregon
• 23: Standard Performance Evaluation Corporation CPU2000 benchmark suite. www.spec.org
• 24: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 25: The simplescalar-arm power modeling project. www.eecs.umich.edu/~jringenb/power/
• 26: S. Thompson, P. Packan, and M. Bohr. Mos scaling: Transistor challenges for the 21st century. Technical Report~Q3, Intel Technology Journal, July 1994
• 27: Triceps: A trimaran-based arm code generator. www.trimaran.org/triceps.shtml
• 28: D. N. Truong , F. Bodin , A. Seznec, Improving Cache Behavior of Dynamically Allocated Data Structures, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.322, October 12-18, 1998
• 29: S. Wilton and N. Jouppi. An enhanced access and cycle time model for on-chip caches. Technical Report 93.5, WRL Research Report, July 1994

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General
      D.2.2 Design Tools and Techniques

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
data remapping, design space exploration, power aware