Memory layout techniques for variables utilizing efficient DRAM access modes in embedded system design

ABSTRACT

The delay of memory access is one of the major bottlenecks in embedded systems' performance. In software compilation, it is known that there is high variations in memory access delay depending on the ways of storing/retrieving the variables in code to/from the memories. In this paper, we propose an effective storage assignment technique for variables to maximize the use of memory bandwidth. Specifically, we study the problem of DRAM memory layout for storing the non-array variables in code to achieve a maximum utilization of page and/or burst modes for the memory accesses. The contributions of our work are, for each of page and burst modes: (1) We prove that the problem is NP-hard; (2) We propose an exact formulation of the problem and efficient memory layout algorithms, called Solve-MLP for the page mode and Solve-MLB for the burst mode; >From experiments with a set of benchmark programs, we confirm that our proposed techniques use on average 20.0% and 9.9% more page accesses and 54.0% and 86.6% more burst accesses than those by OFU (the order of first use) and the technique in [1, 2], respectively.

REFERENCES

• 1: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Exploiting off-chip memory access modes in high-level synthesis, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.333-340, November 09-13, 1997, San Jose, California, United States
• 2: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory data organization for improved cache performance in embedded processor applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.384-409, Oct. 1997 [doi>10.1145/268424.268464]
• 3: N. D. Dutt, "Memory Organization and Exploration for Embedded Systems-on-Silicon," Inter. Conf. on VLSI and CAD, 1997.
• 4: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 5: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 6: Andrew W. Appel , Maia Ginsburg, Modern Compiler Implementation in C, Press Syndicate of the University of Cambridge, 1998
• 7: Sven Wuytack , Francky Catthoor , Gjalt de Jong , Bill Lin , Hugo de Man, Flow Graph Balancing for Minimizing the Required Memory Bandwidth, Proceedings of the 9th international symposium on System synthesis, p.127, November 06-08, 1996
• 8: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 9: IBM, "IBM Cu-11 Embedded DRAM Macro," http://www-3.ibm.com/chips/techlib/techlib.nsf/techdocs/4CBB96F927E2D6D287256B98004E1D98/$file/Cu11_embedded_DRAM.10.pdf, 2002.
• 10: Fujitsu, "CS70DL Embedded DRAM," http://www.fme.fujitsu.com/products/asic/pdf/CS70DLFS.pdf, 1999.
• 11: A. Khare et al., "High-Level Synthesis with Synchronous and RAMBUS DRAMs," SASIMI, 1998.
• 12: Peter Grun , Nikil Dutt , Alex Nicolau, Memory aware compilation through accurate timing extraction, Proceedings of the 37th conference on Design automation, p.316-321, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337428]
• 13: Peter Grun , Nikil Dutt , Alex Nicolau, APEX: access pattern based memory architecture exploration, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500007]
• 14: K. Ayukawa et al., "An Access Sequence Control Scheme to Enhance Random-Access Performance of Embedded DRAMs," IEEE Journal of Solid- State Circuits, 1998.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: V. Zivojnovic, et al., "Dspstone: A DSP-oriented Benchmarking Methodology," International Conference on Signal Processing Applications and Technology, 1994.
• 17: "Bench mark Archives at CBL," http://www.cbl.ncsu.edu/CBL_Docs/Bench.html
• 18: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles

General Terms:
Algorithms, Performance

Keywords:
embedded system, memory layout, page/burst modes, storage assignment