Memory allocation for embedded systems with a compile-time-unknown scratch-pad size

ABSTRACT

This paper presents the first memory allocation scheme for embedded systems having scratch-pad memory whose size is unknown at compile time. A scratch-pad memory (SPM) is a fast compiler-managed SRAM that replaces the hardware-managed cache. Its uses are motivated by its better real-time guarantees as compared to cache and by its significantly lower overheads in energy consumption, area and access time.Existing data allocation schemes for SPM all require that the SPM size be known at compile-time. Unfortunately, the resulting executable is tied to that size of SPM and is not portable to processor implementations having a different SPM size. Such portability would be valuable in situations where programs for an embedded system are not burned into the system at the time of manufacture, but rather are downloaded onto it during deployment, either using a network or portable media such as memory sticks. Such post-deployment code updates are common in distributed networks and in personal hand-held devices. The presence of different SPM sizes in different devices is common because of the evolution in VLSI technology across years. The result is that SPM cannot be used in such situations with downloaded code.To overcome this limitation, this work presents a compiler method whose resulting executable is portable across SPMs of any size. The executable at run-time places frequently used objects in SPM; it considers code, global variables and stack variables for placement in SPM. The allocation is decided by modified loader software before the program is first run and once the SPM size can be discovered. The loader then modifies the program binary based on the decided allocation. To keep the overhead low, much of the pre-processing for the allocation is done at compile-time. Results show that our benchmarks average a 36% speed increase versus an all-DRAM allocation, while the optimal static allocation scheme, which knows the SPM size at compile-time and is thus an un-achievable upper-bound, is only slightly faster (41% faster than all-DRAM). Results also show that the overhead from our embedded loader averages about 1% in both code-size and run-time of our benchmarks.

REFERENCES

• 1: 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]
• 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: ARM968E-S 32-bit Embedded Core. Arm, Revised March 2004. http://www.arm.com/products/CPUs/ARM968E-S.html.
• 4: 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]
• 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: Cnetx. Downloadable software. http://www.cnetx.com/slideshow/.
• 8: CodeSourcery. http://www.codesourcery.com/.
• 9: A. Dominguez, S. Udayakumaran, and R. Barua. Heap Data Allocation to Scratch-Pad Memory in Embedded Systems. Journal of Embedded Computing(JEC), 2005. Cambridge International Science Publishing. To appear August 2005.
• 10: Intel wireless flash memory (W30). Intel Corporation. http://www.intel.com/design/flcomp/datashts/290702.htm.
• 11: Handango. Downloadable software. http://www.handango.com/.
• 12: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 13: 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
• 14: J. Janzen. Calculating Memory System Power for DDR SDRAM. In DesignLine Journal, volume 10(2). Micron Technology Inc., 2001. http://www.micron.com/publications/designline.html.
• 15: Landware. Downloadable software. http://www.landware.com/pocketquicken/.
• 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: 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]
• 18: Phatware. Downloadable software. http://www.phatware.com/phatnotes/.
• 19: 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/.
• 20: 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.
• 21: J. Sjodin and C. V. Platen. Storage Allocation for Embedded Processors. Compiler and Architecture Support for Embedded Computing Systems, November 2001.
• 22: Softmaker. Downloadable software. http://www.softmaker.de.
• 23: 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
• 24: 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]
• 25: 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
• 26: 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]
• 27: Xi-art. Downloadable software. http://www.xi-art.com/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Dynamic memory (DRAM)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Static memory (SRAM)
      B.3.2 Design Styles
          Subjects: Cache memories

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Algorithms, Design, Management, Performance

Keywords:
compiler, data linked list, downloadable codes, embedded loading, embedded systems, memory allocation, scratch-pad