Cache-efficient memory layout of aggregate data structures

ABSTRACT

We describe an important memory optimization that arises in the presence of aggregate data structures such as arrays and structs in a C/C++ based system design methodology. We present an algorithm for determining an optimized memory layout of such data. Our implementation consists of a pointer analysis and resolution phase, followed by memory layout optimization. Experiments on typical applications from the DSP domain result in up to 44% improvement in memory performance.

REFERENCES

• 1: The Open SystemC Initiative, http://www.systemc.org.
• 2: The SUIF Compiler System, http://suif.stanford.edu.
• 3: 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
• 4: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 5: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 6: Rajesh Kumar Gupta , Giovanni De Micheli, Co-Synthesis of Hardware and Software for Digital Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 7: 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
• 8: 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]
• 9: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 10: Luc Séméria , Koichi Sato , Giovanni De Micheli, Resolution of dynamic memory allocation and pointers for the behavioral synthesis form C, Proceedings of the conference on Design, automation and test in Europe, p.312-319, March 27-30, 2000, Paris, France [doi>10.1145/343647.343788]
• 11: L. Semeria and G. D. Micheli. Resolution, optimization, and encoding of pointer variables for the behavioral synthesis from C. IEEE Transactions on Computer Aided Design, 20(2):213-233, Feb. 2001.
• 12: S.Wuytack, J. L. da Silva, F.Catthoor, G. Jong, and C. Ykman-Couvreur. Memory management for embedded network applications. IEEE Transactions on Computer Aided Design, 18(5):533-544, May 1999.
• 13: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design
      B.5.2 Design Aids
          Subjects: Automatic synthesis; Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
data cache, data layout, embedded processors