Nghi Nguyen
Rajeev Barua
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.
- F. Angiolini, L. Benini, and A. Caprara. Polynomial-time algorithm for on-chip scratchpad memory partitioning. In Proceedings of the 2003 international conference on Compilers, architectures and synthesis for embedded systems, pages 318--326. ACM Press, 2003.]] Google Scholar
Digital Library
- F. Angiolini, F. Menichelli, A. Ferrero, L. Benini, and M. Olivieri. A post-compiler approach to scratchpad mapping of code. In Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, pages 259--267. ACM Press, 2004.]] Google ScholarDigital Library
- ARM968E-S 32-bit Embedded Core. Arm, Revised March 2004. http://www.arm.com/products/CPUs/ARM968E-S.html.]]Google Scholar
- O. Avissar, R. Barua, and D. Stewart. Heterogeneous Memory Management for Embedded Systems. In Proceedings of the ACM 2nd International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (CASES), November 2001. Also at http://www.ece.umd.edu/~barua.]] Google ScholarDigital Library
- O. Avissar, R. Barua, and D. Stewart. An Optimal Memory Allocation Scheme for Scratch-Pad Based Embedded Systems. ACM Transactions on Embedded Systems (TECS), 1(1), September 2002.]] Google ScholarDigital Library
- R. Banakar, S. Steinke, B.-S. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad Memory: A Design Alternative for Cache On-chip memory in Embedded Systems. In Tenth International Symposium on Hardware/Software Codesign (CODES), Estes Park, Colorado, May 6-8 2002. ACM.]] Google ScholarDigital Library
- Cnetx. Downloadable software. http://www.cnetx.com/slideshow/.]]Google Scholar
- CodeSourcery. http://www.codesourcery.com/.]]Google Scholar
- 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.]] Google ScholarDigital Library
- Intel wireless flash memory (W30). Intel Corporation. http://www.intel.com/design/flcomp/datashts/290702.htm.]]Google Scholar
- Handango. Downloadable software. http://www.handango.com/.]]Google Scholar
- J. Hennessy and D. Patterson. Computer Architecture A Quantitative Approach. Morgan Kaufmann, Palo Alto, CA, second edition, 1996.]] Google ScholarDigital Library
- J. D. Hiser and J. W. Davidson. Embarc: an efficient memory bank assignment algorithm for retargetable compilers. In Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 182--191. ACM Press, 2004.]] Google ScholarDigital Library
- 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.]]Google Scholar
- Landware. Downloadable software. http://www.landware.com/pocketquicken/.]]Google Scholar
- M. Kandemir, J. Ramanujam, M.J. Irwin, N. Vijaykrishnan, I. Kadayif, and A. Parikh. Dynamic Management of Scratch-Pad Memory Space. In Design Automation Conference, pages 690--695, 2001.]] Google ScholarDigital Library
- P. R. Panda, N. D. Dutt, and A. Nicolau. On-Chip vs. Off-Chip Memory: The Data Partitioning Problem in Embedded Processor-Based Systems. ACM Transactions on Design Automation of Electronic Systems, 5(3), July 2000.]] Google ScholarDigital Library
- Phatware. Downloadable software. http://www.phatware.com/phatnotes/.]]Google Scholar
- 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/.]]Google Scholar
- 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.]]Google Scholar
- J. Sjodin and C. V. Platen. Storage Allocation for Embedded Processors. Compiler and Architecture Support for Embedded Computing Systems, November 2001.]] Google ScholarDigital Library
- Softmaker. Downloadable software. http://www.softmaker.de.]]Google Scholar
- S. Steinke, L. Wehmeyer, B. Lee, and P. Marwedel. Assigning program and data objects to scratchpad for energy reduction. In Proceedings of the conference on Design, automation and test in Europe, page 409. IEEE Computer Society, 2002.]] Google ScholarDigital Library
- S. Udayakumaran and R. Barua. Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In Proceedings of the international conference on Compilers, architectures and synthesis for embedded systems (CASES), pages 276--286. ACM Press, 2003.]] Google ScholarDigital Library
- M. Verma, L. Wehmeyer, and P. Marwedel. Cache-aware scratchpad allocation algorithm. In Proceedings of the conference on Design, automation and test in Europe, page 21264. IEEE Computer Society, 2004.]] Google ScholarDigital Library
- L. Wehmeyer, U. Helmig, and P. Marwedel. Compiler-optimized usage of partitioned memories. In Proceedings of the 3rd Workshop on Memory Performance Issues (WMPI2004), 2004.]] Google ScholarDigital Library
- Xi-art. Downloadable software. http://www.xi-art.com/.]]Google Scholar
Index Terms
- Memory allocation for embedded systems with a compile-time-unknown scratch-pad size
Recommendations
Compiler-decided dynamic memory allocation for scratch-pad based embedded systems
CASES '03: Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systemsThis paper presents a highly predictable, low overhead and yet dynamic, memory allocation strategy for embedded systems with scratch-pad memory. A scratch-pad is a fast compiler-managed SRAM memory that replaces the hardware-managed cache. It is ...
Dynamic allocation for scratch-pad memory using compile-time decisions
In this research, we propose a highly predictable, low overhead, and, yet, dynamic, memory-allocation strategy for embedded systems with scratch pad memory. A scratch pad is a fast compiler-managed SRAM memory that replaces the hardware-managed cache. ...
Memory allocation for embedded systems with a compile-time-unknown scratch-pad size
This article presents the first memory allocation scheme for embedded systems having a 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. All ...
Comments