Dynamic data scratchpad memory management for a memory subsystem with an MMU

ABSTRACT

In this paper, we propose a dynamic scratchpad memory (SPM)management technique for a horizontally-partitioned memory subsystem with an MMU. The memory subsystem consists of a relatively cheap direct-mapped data cache and SPM. Our technique loads required global data and stack pages into the SPM on demand when a function is called. A scratchpad memory managerloads/unloads the data pages and maintains a page table for the MMU. Our approach is based on post-pass analysis and optimization techniques, and it handles the whole program including libraries. The data page mapping is determined by solving an integer linear programming (ILP) formulation that approximates our demand paging technique. The ILP model uses a dynamic call graph annotated with the number of memory accesses and/or cache misses obtained by profiling. We evaluate our technique on thirteen embedded applications. We compare the results to a reference system with a 4-way set associative data cache and the ideal case with the same 4-way cache and SPM, where all global and stack data is placed in the SPM. On average, our approach reduces the total system energy consumption by 8.1% with no performance degradation. This is equivalent to exploiting 60% of the room available in energy reduction between the reference case and the ideal case.

REFERENCES

• 1: Advanced Compiler Research Laboratory. Seoul National University Advanced Compiler Tool Kit (SNACK). http://aces.snu.ac.kr/snack.html, 2004.
• 2: Federico Angiolini , Luca Benini , Alberto Caprara, Polynomial-time algorithm for on-chip scratchpad memory partitioning, 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.951751]
• 3: Federico Angiolini , Francesco Menichelli , Alberto Ferrero , Luca Benini , Mauro Olivieri, A post-compiler approach to scratchpad mapping of code, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023869]
• 4: 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]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Angel Dominguez , Sumesh Udayakumaran , Rajeev Barua, Heap data allocation to scratch-pad memory in embedded systems, Journal of Embedded Computing, v.1 n.4, p.521-540, December 2005
• 7: Bernhard Egger , Chihun Kim , Choonki Jang , Yoonsung Nam , Jaejin Lee , Sang Lyul Min, A dynamic code placement technique for scratchpad memory using postpass optimization, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176788]
• 8: 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]
• 9: John Fotheringham, Dynamic storage allocation in the Atlas computer, including an automatic use of a backing store, Communications of the ACM, v.4 n.10, p.435-436, Oct. 1961 [doi>10.1145/366786.366800]
• 10: 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]
• 11: Lindo Systems Inc. What's Best! 8.0. http://www.lindo.com/products/wb/wbm.html, 2007.
• 12: Intel. Intel XScale Core Developers Manual, January 2004.
• 13: Lars Wehmeyer , Urs Helmig , Peter Marwedel, Compiler-optimized usage of partitioned memories, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.114-120, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054959]
• 14: 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
• 15: ARM Ltd. ARM926EJ-S,. http://www.arm.com/products/CPUs/ARM926EJ-S.html, 2002.
• 16: ARM Ltd. ARM926EJ-S Technical Reference Manual, 2003.
• 17: Micron Technology, Inc. MT48H8M16LF Mobile SDRAM. http://www.micron.com/products/dram/mobilesdram/, 2003.
• 18: Micron Technology, Inc. Mobile SDRAM Power Calc 10. http://www.micron.com/systemcalc, 2004.
• 19: MP3 Reference Decoder. http://www.mp3-tech.org/programmer/sources/dist10.tgz, 1996.
• 20: Nghi Nguyen , Angel Dominguez , Rajeev Barua, Memory allocation for embedded systems with a compile-time-unknown scratch-pad size, 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.1086313]
• 21: Pretty Good Privacy (PGPi). http://www.pgpi.org/, 2002.
• 22: Samsung Semiconductor. K4X51163PC Mobile DDR SRAM. http://www.samsung.com/products/semiconductor/MobileSDRAM/, 2005.
• 23: 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]
• 24: 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]
• 25: 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
• 26: 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]
• 27: 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]
• 28: 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]
• 29: Steven J. E. Wilton and Norman P. Jouppi. CACTI: An Enhanced Cache Access and Cycle Time Model. IEEE Journal of Solid State Circuits, 31(5):677--688, 1996.
• 30: Xvid MPEG-4 Video Codec. http://www.xvid.org, 2005.

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

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

Keywords:
compilers, demand paging, horizontally-partitioned memory, post-pass optimization, scratchpad memory