A dynamic code placement technique for scratchpad memory using postpass optimization

ABSTRACT

In this paper, we propose a fully automatic dynamic scratch-pad memory (SPM) management technique for instructions. Our technique loads required code segments into the SPM on demand at runtime. Our approach is based on postpass analysis and optimization techniques, and it handles the whole program, including libraries. The code mapping is determined by solving mixed integer linear programming formulation that approximates our demand paging technique. We increase the effectiveness of demand paging by extracting from functions natural loops that are smaller in size and have a higher instruction fetch count. The postpass optimizer analyzes the object files of an application and transforms them into an application binary image that enables demand paging to the SPM. We evaluate our technique on eleven embedded applications and compare it to a processor core with an instruction cache in terms of its performance and energy consumption. The cache size is about 20% of the executed code size, and the SPM size is chosen such that its die area is equal to that of the cache. The experimental results show that, on average, the processor core and memory subsystem's energy consumption can be reduced by 21.6% and the performance improved by 20.2%. Moreover, in comparison with the optimal static placement strategy, our technique reduces energy consumption by 23.7% and improves performance by 22.9%,on average.

REFERENCES

• 1: Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 1986.
• 2: Federico Angiolini, Luca Benini, and Alberto Caprara. Polynomial-Time Algorithm for On-chip Scratchpad Memory Partitioning. In International Conference on Compilers, Architectures and Synthesis of Embedded Systems (CASES 2003), October 2003.
• 3: Federico Angiolini, Francesco Menichelli, Alberto Ferrero, Luca Benini, and Mauro Oliveri. A Post-Compiler Approach to Scratchpad Mapping of Code. In International Conference on Compilers, Architectures and Synthesis of Embedded Systems (CASES 2004), September 2004.
• 4: ARM. http://www.arm.com.
• 5: 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]
• 6: 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]
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: R Cytron , P G Loewner, An automatic overlay generator, IBM Journal of Research and Development, v.30 n.6, p.603-608, Nov. 1986
• 9: Bernhard Egger , Jaejin Lee , Heonshik Shin, Scratchpad memory management for portable systems with a memory management unit, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176933]
• 10: Poletti Francesco , Paul Marchal , David Atienza , Luca Benini , Francky Catthoor , Jose M. Mendias, An integrated hardware/software approach for run-time scratchpad management, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996634]
• 11: Ann Gordon-Ross , Susan Cotterell , Frank Vahid, Exploiting Fixed Programs in Embedded Systems: A Loop Cache Example, IEEE Computer Architecture Letters, v.1 n.1, p.2, January 2006 [doi>10.1109/L-CA.2002.4]
• 12: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 13: http://www.xvid.org. Xvid MPEG-4 Video Codec. 2004.
• 14: Andhi Janapsatya , Aleksandar Ignjatović , Sri Parameswaran, A novel instruction scratchpad memory optimization method based on concomitance metric, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118443]
• 15: M. Kandemir , A. Choudhary, Compiler-directed scratch pad memory hierarchy design and management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514077]
• 16: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 17: 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
• 18: 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]
• 19: Inc Micron Technology. Mt48h8m16lf mobile sdram. 2003.
• 20: Micron Technology, Inc. Mobile SDRAM Power Calc 10. 2004.
• 21: 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]
• 22: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 23: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 24: Chanik Park , Junghee Lim , Kiwon Kwon , Jaejin Lee , Sang Lyul Min, Compiler-assisted demand paging for embedded systems with flash memory, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017775]
• 25: Aviral Shrivastava , Ilya Issenin , Nikil Dutt, Compilation techniques for energy reduction in horizontally partitioned cache architectures, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086310]
• 26: Abraham Silberschatz , Peter Galvin , Greg Gagne, Applied Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 2001
• 27: 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]
• 28: 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
• 29: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 30: 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
• 31: Manish Verma , Lars Wehmeyer , Peter Marwedel, Dynamic overlay of scratchpad memory for energy minimization, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016748]
• 32: S. Wilton and Norman Jouppi. CACTI: An Enhanced Access and Cycle Time Model. IEEE Journal of Solid State Circuits, 31(5): 677--688, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Code generation
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory; Storage hierarchies; Secondary storage

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
code placement, compilers, demand paging, embedded systems, heterogeneous memory, postpass optimization, scratchpad memory