Heterogeneous memory management for embedded systems

ABSTRACT

This paper presents a technique for the efficient compiler management of software-exposed heterogeneous memory. In many lower-end embedded chips, often used in micro-controllers 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 because of 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 the different memory units. We present a compiler strategy that automatically partitions the data among the memory units. We show that this strategy is optimal among all static partitions for global and stack data, and a good heuristic for heap data. For global and stack data, the scheme is provably equal to or better than any other compiler scheme or set of programmer annotations. Preliminary results show the benefits of optimal allocation: with just 20% of the data in SRAM, the formulation is able to decrease the runtime by 39% on average for our benchmarks vs. allocating all data to slow memory, without any programmer involvement. 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: 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]
• 3: S.S.Bhattacharyya,R.Leupers,and P.Marwedel. Software Synthesis and Code Generation for Signal Processing Systems.IEEE Transactions on Circuits and Systems ,47(9),September 2000.
• 4: T.T.Consortium.The Trimaran benchmark suite. Available at http://www.trimaran.org/,1999.
• 5: 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
• 6: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 7: 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]
• 8: Matlab 6.1 .The Math Works,Inc.,2001. http://www.mathworks.com/products/matlab/.
• 9: 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
• 10: CPU12 Reference Manual .Motorola Corporation, 2000.http://e-www.motorola.com/brdata/PDFDB/- MICROCONTROLLERS/16 BIT/- 68HC12 FAMI LY/REF MAT/CPU12RM.pdf.
• 11: M-CORE -MMC2001 Reference Manual .Motorola Corporation,1998.http://www.motorola.com/SPS/- MCORE/info documentation.htm.
• 12: New York City,O .ce of Budget and Management. Website on frequently asked questions on linear programming . http://www.eden.rutgers.edu/~pil/FAQ.html,New York,NY,1999.
• 13: 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]
• 14: P.Paulin,C.Liem,M.Cornero,F.Nacabal,and G.Goossens.Embedded Software in Real-Time Signal Processing Systems:Application and Architecture Trends.Invited paper,Proceedings of the IEEE ,85(3), March 1997.
• 15: P.Rutter,J.Orost,and D.Gloistein.BTOA:Binary to printable ASCII converter source code.Available at http://www.bookcase.com/library/software/- msdos.devel.lang.c.html .
• 16: 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.
• 17: TMS370Cx7x 8-bit microcontroller .Texas Instruments,Revised Feb.1997.http://wwws.ti.com/sc/psheets/spns034c/spns034c.pdf.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories

Additional Classification:
  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: Compilers

General Terms:
Algorithms, Design, Theory

Keywords:
embedded, heterogeneous, memory, storage