On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems

ABSTRACT

Efficient utilization of on-chip memory space is extremely important in modern embedded system applications based on processor cores. In addition to a data cache that interfaces with slower off-chip memory, a fast on-chip SRAM, called Scratch-Pad memory, is often used in several applications, so that critical data can be stored there with a guaranteed fast access time. We present a technique for efficiently exploiting on-chip Scratch-Pad memory by partitioning the application's scalar and arrayed variables into off-chip DRAM and on-chip Scratch-Pad SRAM, with the goal of minimizing the total execution time of embedded applications. We also present extensions of our proposed memory assignment strategy to handle context switching between multiple programs, as well as a generalized memory hierarchy. Our experiments on code kernels from typical applications show that our technique results in significant performance improvements.

REFERENCES

• 1: AHMAD, I. AND CHEN, C. Y. R. 1991. Post-processor for data path synthesis using multiport memories. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14, 1991), IEEE Computer Society Press, Los Alamitos, CA, 276-279.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: 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
• 4: BALAKRISHNAN, M., BANERJI, D. K., MAJUMDAR, A. K., LINDERS, J. G., AND MAJITHIA, J. C. 1990. Allocation of multiport memories in data path synthesis. IEEE Trans. Comput.- Aided Des. 7, 4 (Apr. 1990), 536-540.
• 5: Florin Balasa , Francky Catthoor , Hugo De Man, Background memory area estimation for multidimensional signal processing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.157-172, June 1995 [doi>10.1109/92.386218]
• 6: Lars Svensson , Francky Catthoor, Application-Driven Architecture Synthesis, Kluwer Academic Publishers, Norwell, MA, 1993
• 7: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 8: Didier Le Gall, MPEG: a video compression standard for multimedia applications, Communications of the ACM, v.34 n.4, p.46-58, April 1991 [doi>10.1145/103085.103090]
• 9: 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
• 10: Pradip K. Jha , Nikil D. Dutt, High-level library mapping for memories, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.566-603, July 2000 [doi>10.1145/348019.348297]
• 11: David Karchmer , Jonathan Rose, Definition and solution of the memory packing problem for field-programmable systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.20-26, November 06-10, 1994, San Jose, California, United States
• 12: Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164900]
• 13: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 14: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Code optimization techniques for embedded DSP microprocessors, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.599-604, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217596]
• 15: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States
• 16: P. E. R. Lippens , J. L. van Meerbergen , W. F. J. Verhaegh , A. van der Werf, Allocation of multiport memories for hierarchical data stream, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.728-735, November 07-11, 1993, Santa Clara, California, United States
• 17: LSI LOGIC CORPORATION. 1992. CW33000 MIPS Embedded Processor User's Manual. VLSI Technologies, Inc..
• 18: MARGOLIN, B. 1997. Embedded systems to benefit from advances in dram technology. Comput. Des., 76-86.
• 19: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 20: Preeti Ranjan Panda , Nikil D. Dutt, Memory optimizations and exploration for embedded systems, 1998
• 21: Preeti R. Panda , Nikil D. Dutt, 1995 high level synthesis design repository, Proceedings of the 8th international symposium on System synthesis, p.170-174, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224537]
• 22: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory Organization for Improved Data Cache Performance in Embedded Processors, Proceedings of the 9th international symposium on System synthesis, p.90, November 06-08, 1996
• 23: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 24: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 25: RAMACHANDRAN, L., GAJSKI, D., AND CHAIYAKUL, V. 1994. An algorithm for array variable clustering. In Proceedings of the European Conference on Design Automation (Feb. 1994),
• 26: RAWAT, J. 1993. Static analysis of cache performance for real-time programming. Master's Thesis. Iowa State Univ., Ames, IA.
• 27: Mazen A. R. Saghir , Paul Chow , Corinna G. Lee, Exploiting dual data-memory banks in digital signal processors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.234-243, October 01-04, 1996, Cambridge, Massachusetts, United States
• 28: Herman Schmit , Donald E. Thomas, Address generation for memories containing multiple arrays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.510-514, November 05-09, 1995, San Jose, California, United States
• 29: STOK, L. AND JESS, J. A. G. 1992. Foreground memory management in data path synthesis. Int. J. Circuits Theor. Appl. 20, 3, 235-255.
• 30: Ashok Sudarsanam , Sharad Malik, Memory bank and register allocation in software synthesis for ASIPs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.388-392, November 05-09, 1995, San Jose, California, United States
• 31: Hiroyuki Tomiyama , Hiroto Yasuura, Optimal Code Placement of Embedded Software for Instruction Caches, Proceedings of the 1996 European conference on Design and Test, p.96, March 11-14, 1996
• 32: H. Tomiyama , H. Yasuura, Size-Constrained Code Placement for Cache Miss Rate Reduction, Proceedings of the 9th international symposium on System synthesis, p.96, November 06-08, 1996
• 33: TSENG, C. AND SIEWIOREK, D. P. 1986. Automated synthesis of data paths in digital systems. IEEE Trans. Comput.-Aided Des. 5, 3 (July 1986), 379-395.
• 34: TURLEY, J. L. 1994. New processor families join embedded fray. Microprocessor Report 8, 17 (Dec.), 1-8.
• 35: VANHOOF, g., BOLSENS, I., AND MAN, H. D. 1991. Compiling multi-dimensional data streams into distributed DSP ASIC memory. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14, 1991), IEEE Computer Society Press, Los Alamitos, CA, 272-275.
• 36: Ingrid M. Verbauwhede , Chris J. Scheers , Jan M. Rabaey, Memory estimation for high level synthesis, Proceedings of the 31st annual conference on Design automation, p.143-148, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196313]
• 37: WILSON, R. 1997. Graphics IC vendors take a shot at embedded DRAM. Elec. Eng. Times 938 (Jan.), 41-57.
• 38: 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

INDEX TERMS

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

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
data cache, data partitioning, memory synthesis, on-chip memory, scratch-pad memory, system design, system synthesis