An optimal memory allocation scheme for scratch-pad-based embedded systems

ABSTRACT

This article presents a technique for the efficient compiler management of software-exposed heterogeneous memory. In many lower-end embedded chips, often used in microcontrollers and DSP processors, heterogeneous memory units such as scratch-pad SRAM, internal DRAM, external DRAM, and ROM are visible directly to the software, without automatic management by a hardware caching mechanism. Instead, the memory units are mapped to different portions of the address space. Caches are avoided due to their cost and power consumption, and because they make it difficult to guarantee real-time performance. For this important class of embedded chips, the allocation of data to different memory units to maximize performance is the responsibility of the software.Current practice typically leaves it to the programmer to partition the data among different memory units. We present a compiler strategy that automatically partitions the data among the memory units. We show that this strategy is optimal, relative to the profile run, among all static partitions for global and stack data. For the first time, our allocation scheme for stacks distributes the stack among multiple memory units. For global and stack data, the scheme is provably equal to or better than any other compiler scheme or set of programmer annotations. Results from our benchmarks show a 44.2% reduction in runtime from using our distributed stack strategy vs. using a unified stack, and a further 11.8% reduction in runtime from using a linear optimization strategy for allocation vs. a simpler greedy strategy; both in the case of the SRAM size being 20% of the total data size. For some programs, less than 5% of data in SRAM achieves a similar speedup.

REFERENCES

• 1: Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.243-253, June 2001, Snowbird, Utah, United States
• 2: 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]
• 3: Rajeev Barua , Walter Lee , Saman Amarasinghe , Anant Agarawal, Compiler Support for Scalable and Efficient Memory Systems, IEEE Transactions on Computers, v.50 n.11, p.1234-1247, November 2001 [doi>10.1109/12.966497]
• 4: Bhattacharyya, S. S., Leupers, R., and Marwedel, P. 2000. Software synthesis and code generation for signal processing systems. IEEE Trans. Circuits Syst. 47, 9 (Sept.).
• 5: Consortium, T. T. 1999. The Trimaran benchmark suite. Available at http://www.trimaran.org/.
• 6: Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 2001. MiBench: A free, commercially representative embedded benchmark suite. Available at http://www.eecs.umich.edu/jringenb/mibench/.
• 7: 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
• 8: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 9: 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]
• 10: Matlab 6.1. The Math Works, Inc., 2001. http://www.mathworks.com/products/matlab/.
• 11: 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
• 12: CPU12 Reference Manual. Motorola Corporation, 2000. http://e-www.motorola.com/brdata/PDFDB/MICROCONTROLLERS/16_BIT/68HC12_FAMILY/REF_MAT/CPU12RM.pdf.
• 13: M-CORE---MMC2001 Reference Manual. Motorola Corporation, 1998. http://www.motorola. com/SPS/MCORE/info_documentation.htm.
• 14: New York City, Office of Budget and Management. 1999. Website on frequently asked questions on linear programming. http://www.eden.rutgers.edu/∼pil/FAQ.html. New York, NY.
• 15: University of Toronto Digital Signal Processing (UTDSP). 1992. University of Toronto Digital Signal Processing (UTDSP) Benchmark Suite. Available at http://www.eecg.toronto.edu/.
• 16: 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]
• 17: Paulin, P., Liem, C., Cornero, M., Nacabal, F., and Goossens, G. 1997. Embedded software in real-time signal processing systems: Application and architecture trends. Invited paper, Proc. IEEE 85, 3 (Mar.).
• 18: Rutter, P., Orost, J., and Gloistein, D. BTOA: Binary to printable ASCII converter source code. Available at http://www.bookcase.com/library/software/msdos.devel.lang.c.html.
• 19: Sjodin, J., Froderberg, B., and Lindgren, T. 1998. Allocation of global data objects in on-chip RAM. Compiler and Architecture Support for Embedded Computing Systems. Dec.
• 20: 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]
• 21: TMS370Cx7x 8-bit microcontroller. Texas Instruments, Revised Feb. 1997. http://www-s.ti.com/sc/psheets/spns034c/spns034c.pdf.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

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

General Terms:
Design, Measurement, Performance

Keywords:
Memory, allocation, embedded, heterogeneous, storage