Fast, predictable and low energy memory references through architecture-aware compilation

ABSTRACT

The design of future high-performance embedded systems is hampered by two problems: First, the required hardware needs more energy than is available from batteries. Second, current cache-based approaches for bridging the increasing speed gap between processors and memories cannot guarantee predictable real-time behavior. A contribution to solving both problems is made in this paper which describes a comprehensive set of algorithms that can be applied at design time in order to maximally exploit scratch pad memories (SPMs). We show that both the energy consumption as well as the computed worst case execution time (WCET) can be reduced by up to to 80% and 48%, respectively, by establishing a strong link between the memory architecture and the compiler.

REFERENCES

• 1: ARM Ltd. ARM946E-S: Embedded core with flexible cached memory system & DSP instruction set extensions. http://www.arm.com/armtech/ARM946E_S?OpenDocument.
• 2: Atmel. Atmel Corporation Homepage. http://www.atmel.com, 2003.
• 3: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 4: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 5: M. Chen. A Timing Analysis Language - (TAL) - Programmer's Manual. Technical report, Dept. of Computer Sciences, University of Texas, Ausin, TX, USA, 1987.
• 6: Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.2-11, October 02-07, 1998, San Jose, California, United States
• 7: H. De Man. Keynote session at DATE'02. http://www.date-conference.com/conference/keynotes/index.htm, 2002.
• 8: L. Eggermont. Embedded Systems Roadmap. Technical report, STW, http://www.stw.nl/progress/ESroadmap/index.html, 2002.
• 9: S. C. A. Gordon-Ross and F. Vahid. Exploiting Fixed Programs in Embedded Systems: A Loop Cache Example. Computer Architecture Letters, January 2002.
• 10: Yerang Hur , Young Hyun Bae , Sung-Soo Lim , Sung-Kwan Kim , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Minsuk Lee , Heonshik Shin , Chong Sang Kim, Worst case timing analysis of RISC processors: R3000/R3010 case study, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.308, December 05-07, 1995
• 11: ILOG. CPLEX. http://www.ilog.com/products/cplex.
• 12: Mahmut Kandemir , Ismail Kadayif , Ugur Sezer, Exploiting scratch-pad memory using Presburger formulas, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500004]
• 13: R. Kirner and P. Puschner. Consideration of Optimizing Compilers in the Context of WCET Analysis. In Proc. Deutsche Informatiktage 2000, Bad Schussenried, pages 123--126. GI Gesellschaft für Informatik e.V., Oct. 2000.
• 14: R. Kirner and P. Puschner. International Workshop on WCET Analysis - Summary. Research Report 12/2000, Technische Universität Wien, Institut für Technische Informatik, Treitlstr. 1-3/182-1, 1040 Vienna, Austria, 2002.
• 15: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 16: Lea Hwang Lee , Bill Moyer , John Arends, Instruction fetch energy reduction using loop caches for embedded applications with small tight loops, Proceedings of the 1999 international symposium on Low power electronics and design, p.267-269, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313944]
• 17: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.298, December 05-07, 1995
• 18: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 19: Y.-T. S. Li , S. Malik , A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.254, December 04-06, 1996
• 20: S. Lim, Y. H. Bea, G. T. Jang, B. Rhee, S. L. Min, C. Y. Park, H. Shin, and C. S. Kim. An Accurate Worst Case Timing Analysis for RISC Processors. In Proceedings of the 15th Real-Time Systems Sympoisum, pages 97--108, 1994.
• 21: P. Machanik. Approaches to Addressing the Memory Wall. Technical Report, November, Univ. Brisbane, 2002.
• 22: A. K. Mok, P. Amerasinghe, M. Chen, and K. Tantisirivat. Evaluating Tight Execution Time Bounds of Programs by Annotations. In Proc. of the 6th IEEE Workshop on Real-Time Operating Systems and Software, pages 74--80, 1989.
• 23: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 24: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 25: Peter Puschner , Alan Burns, Guest Editorial: A Review of Worst-Case Execution-TimeAnalysis, Real-Time Systems, v.18 n.2-3, p.115-128, May 2000 [doi>10.1023/A:1008119029962]
• 26: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 27: S. Steinke. Investigation of the Potential for Energy Savings in Embedded Systems enabled by Energy Optimizing Compilers. PhD thesis, (in German), Embedded Systems Group, CS Dept., University of Dortmund, Dortmund, Germany, 2003.
• 28: Stefan Steinke , Nils Grunwald , Lars Wehmeyer , Rajeshwari Banakar , M. Balakrishnan , Peter Marwedel, Reducing energy consumption by dynamic copying of instructions onto onchip memory, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581247]
• 29: S. Steinke , L. Wehmeyer , B. Lee , P. Marwedel, Assigning Program and Data Objects to Scratchpad for Energy Reduction, Proceedings of the conference on Design, automation and test in Europe, p.409, March 04-08, 2002
• 30: M. Theokharidis. Energiemessung von ARM7TDMI Prozessor-Instruktionen. Master's thesis, (in German), Embedded Systems Group, CS Dept., University of Dortmund, Dortmund, Germany, 2000.
• 31: Manish Verma , Stefan Steinke , Peter Marwedel, Data partitioning for maximal scratchpad usage, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119788]
• 32: Manish Verma , Lars Wehmeyer , Peter Marwedel, Cache-Aware Scratchpad Allocation Algorithm, Proceedings of the conference on Design, automation and test in Europe, p.21264, February 16-20, 2004
• 33: Lei Wang , Waibhav Tembe , Santosh Pande, A Framework for Loop Distribution on Limited On-Chip Memory Processors, Proceedings of the 9th International Conference on Compiler Construction, p.141-156, March 25-April 02, 2000
• 34: S. Wilton and N. Jouppi. CACTI: An enhanced access and cycle time model. Int. Journal on Solid State Circuits, 31(5):677--688, 1996.
• 35: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]
• 36: Jia Xu , David Lorge Parnas, On satisfying timing constraints in hard-real-time systems, ACM SIGSOFT Software Engineering Notes, v.16 n.5, p.132-146, Dec. 1991
• 37: N. Zhang , A. Burns , M. Nicholson, Pipelined processors and worst case execution times, Real-Time Systems, v.5 n.4, p.319-343, Oct. 1993 [doi>10.1007/BF01088834]