Memory access optimization through combined code scheduling, memory allocation, and array binding in embedded system design

ABSTRACT

In many of embedded systems, particularly for those with high data computations, the delay of memory access is one of the major bottlenecks in the system's performance. It has been known that there are high variations in memory access delays depending on the ways of designing memory configurations and assigning arrays to memories. Furthermore, embedded DRAM technology that provides efficient access modes is actively developed, possibly becoming a mainstream in future embedded system design. In that context, in this paper we propose an effective solution to the problem of (embedded DRAM) memory allocation and mapping in memory access code generation with the objective of minimizing the total memory access time. Specifically, the proposed approach, called MACCESS-opt, solves the three problems simultaneously: (i) determination of memories, (ii) mapping of arrays to memories, and (iii) scheduling of memory access operations, so that the use of DRAM access modes is maximized while satisfying the storage size constraint of embedded system. Experimental data on a set of benchmark designs are provided to show the effectiveness of the proposed integrated approach. In short, MACCESS-opt reduces the total memory access latency by over 18%, from which we found that our memory mapping and scheduling techniques in MACCESS-opt contribute about 12% and 6% reductions of total memory access latency, respectively.

REFERENCES

• 1: B. Prince, High Performance Memories, New Architecture DRAMs and SRAMs Evolution and Function, Wiley, West Sussex, 1996.
• 2: S. Przybylski, "Sorting out the new DRAMs", In Hot Chips Tutorial, Stanford, CA, 1997.
• 3: Herman Schmit , Donald E. Thomas, Array mapping in behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.90-95, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224508]
• 4: Preeti Ranjan Panda, Memory bank customization and assignment in behavioral synthesis, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.477-481, November 07-11, 1999, San Jose, California, United States
• 5: P. R. Panda et al., "Incorporating DRAM Access Modes into High-level Synthesis", IEEE TCAD, Vol. 17, 1998.
• 6: W. T. Shiue and C. Chakrabarti, "Memory Exploration for Low Power Embedded Systems", DAC, 2001.
• 7: Florin Balasa , Francky Catthoor , Hugo De Man, Dataflow-driven memory allocation for multi-dimensional signal processing systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.31-34, November 06-10, 1994, San Jose, California, United States
• 8: Jaewon Seo , Taewhan Kim , Preeti R. Panda, An integrated algorithm for memory allocation and assignment in high-level synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514072]
• 9: Smita Bakshi , Daniel D. Gajski, A memory selection algorithm for high-performance pipelines, Proceedings of the conference on European design automation, p.124-129, September 18-22, 1995, Brighton, England
• 10: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 11: I. Kadayif , M. Kandemir , I. Kolcu , G. Chen, Locality-conscious process scheduling in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774829]
• 12: Yoonseo Choi , Taewhan Kim, Memory layout techniques for variables utilizing efficient DRAM access modes in embedded system design, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776053]
• 13: W-T. Shiue, et al., "Low Power Multi-Module, Multi-Port Memory Design for Embedded Systems", Workshop on Signal Processing, 2000.
• 14: 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]
• 15: W. H. Press, et al., "Numerical Recipes in C", Cambridge university press, 1992.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
binding, memory access, scheduling