Recursive function data allocation to scratch-pad memory

ABSTRACT

This paper presents the first automatic scheme to allocate local (stack) data in recursive functions to scratch-pad memory (SPM) in embedded systems. A scratch-pad is a fast directly addressed compiler-managed SRAM memory that replaces the hardware-managed cache. It is motivated by its significantly lower access time, energy consumption, real-time bounds, area and overall runtime. Existing compiler methods for allocating data to scratch-pad are able to place only code, global, heap and non-recursive stack data in scratch-pad memory; stack data for recursive functions is allocated entirely in DRAM, resulting in poor performance.

In this paper we present a dynamic yet compiler-directed allocation method for recursive function stack data that for the first time, is able to place a portion of recursive stack data in scratch-pad. It has almost no software-caching overhead, and is able to move recursive function data back and forth between scratch-pad and DRAM to better track the program's locality characteristics. With our method, all code, global, stack and heap variables can share the same scratch-pad. When compared to placing all recursive function data in DRAM and all other variables in scratch-pad, our results show that our method reduces the average runtime of our benchmarks by 29.3%, and the average power consumption by 31.1%, for the same size of scratch-pad fixed at5% of total data size. Furthermore,significant savings were observedwhen comparing our method against cache-based alternatives for SPM allocation. Finally, we show results that analyze the effects of profile variation on our allocation approach and present a modified version of our method which minimizes variation for profile-based allocations.

REFERENCES

• 1: M. Adiletta, M. Rosenbluth, D. Bernstein, G. Wolrich, and H. Wilkinson. The Next Generation of Intel IXP Network Processors. Intel Technology Journal, 6(3), Aug. 2002. http://developer.intel.com/technology/itj/2002/volume06issue03/.
• 2: 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]
• 3: Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, 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.502223]
• 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: 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]
• 6: R. S. Bird, Notes on recursion elimination, Communications of the ACM, v.20 n.6, p.434-439, June 1977 [doi>10.1145/359605.359630]
• 7: D. Brash. The ARM architecture Version 6 (ARMv6). ARM Ltd., January 2002. White Paper.
• 8: William D. Clinger, Proper tail recursion and space efficiency, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.174-185, June 17-19, 1998, Montreal, Quebec, Canada
• 9: Cacti 3.2. P. Shivaumar and N. P. Jouppi, Revised 2004. http://research.compaq.com/wrl/people/jouppi/CACTI.html.
• 10: 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
• 11: GNU. GNU Compiler Collection. Cambridge, Massachusetts, USA, http://gcc.gnu.org/, 2006. Also available at http://gcc.gnu.org/.
• 12: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 13: Peter Harrison , Hessam Khoshnevisan, Efficient compilation of linear recursive functions into object level loops, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.207-218, June 25-27, 1986, Palo Alto, California, United States
• 14: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 15: Jason D. Hiser , Jack W. Davidson, EMBARC: an efficient memory bank assignment algorithm for retargetable compilers, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 16: Intel. Intel StrongARM SA1110 Embedded Procesor, 2000. http://developer.intel.com/design/pca/applications-- processors/1110 brf.htm.
• 17: J. Janzen. Calculating Memory System Power for DDR DRAM. In DesignLine Journal, volume 10(2). Micron Technology Inc., 2001. http://www.micron.com/publications/designline.html.
• 18: 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]
• 19: 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]
• 20: Owen Kaser , C. R. Ramakrishnan , Shaunak Pawagi, On the conversion of indirect to direct recursion, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.151-164, March–Dec. 1993 [doi>10.1145/176454.176510]
• 21: Mike Tien-Chien Lee , Masahiro Fujita , Vivek Tiwari , Sharad Malik, Power analysis and minimization techniques for embedded DSP software, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.123-135, March 1997 [doi>10.1109/92.555992]
• 22: Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.73-82, January 22-23, 2000, Boston, Massachusetts, United States
• 23: 128Mb DDR SDRAM data sheet. (Dual data-rate synchronous DRAM) Micron Technology Inc., 2003. http://www.micron.com/products/dram/ddrsdram/.
• 24: 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]
• 25: Csaba Andras Moritz , Matthew Frank , Saman P. Amarasinghe, FlexCache: A Framework for Flexible Compiler Generated Data Caching, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.135-146, November 12, 2000
• 26: M-CORE-MMC2001 Reference Manual. Motorola Corporation, 1998. (A 32-bit processor). http://www.motorola.com/SPS/MCORE/-info documentation.htm.
• 27: 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]
• 28: Compilation Challenges for Network Processors. Industrial Panel, ACM Conference on Languages, Compilers and Tools for Embedded Systems (LCTES), June 2003. Slides at http://www.cs.purdue.edu/s3/LCTES03/.
• 29: Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
• 30: J. Sjodin, B. Froderberg, and T. Lindgren. Allocation of Global Data Objects in On-Chip RAM. Compiler and Architecture Support for Embedded Computing Systems, December 1998.
• 31: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, 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.502221]
• 32: 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
• 33: Sumesh Udayakumaran , Angel Dominguez , Rajeev Barua, Dynamic allocation for scratch-pad memory using compile-time decisions, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.2, p.472-511, May 2006 [doi>10.1145/1151074.1151085]
• 34: TMS370Cx7x 8-bit microcontroller. Texas Instruments, Revised Feb. 1997. http://wwws.ti.com/sc/psheets/spns034c/spns034c.pdf.
• 35: 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]
• 36: DineroIV Cache simulator. J. Edler and M. D. Hill, Revised 2004. http://www.cs.wisc.edu/ markhill/DineroIV/.
• 37: 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
• 38: 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]
• 39: 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]
• 40: L. Wehmeyer and P. Marwedel. Influence of onchip scratchpad memories on wcet prediction. In Proceedings of the 4th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2004.
• 41: S. Wilton and N. Jouppi. Cacti: An enhanced cache access and cycle time model. In IEEE Journal of Solid-State Circuits, 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Dynamic memory (DRAM); Static memory (SRAM)

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Management, Performance

Keywords:
compiler, embedded systems, memory allocation, profile dependance, recursive functions, scratch-pad memory