Exploiting bank locality in multi-bank memories

ABSTRACT

Bank locality can be defined as localizing the number of load/store accesses to a small set of memory banks at a given time. An optimizing compiler can modify a given input code to improve its bank locality. There are several practical advantages of enhancing bank locality, the most important of which is reduced memory energy consumption. Recent trends indicate that energy consumption is fast becoming a first-order design parameter as processor-based systems continue to become more complex and multi-functional. Off-chip memory energy consumption in particular can be a limiting factor in many embedded system designs. This paper presents a novel compiler-based strategy for maximizing the benefits of low-power operating modes available in some recent DRAM-based multi-bank memory systems. In this strategy, the compiler uses linear algebra to represent and optimize bank locality in a mathematical framework. We discuss that exploiting bank locality can be cast as loop (iteration space) and array layout (data space) transformations. We also present experimental data showing the effectiveness of our optimization strategy. Our results show that exploiting bank locality can result in large energy savings.

REFERENCES

• 1: Saman P. Amarasinghe , Jennifer M. Anderson , Christopher S. Wilson , Shih-Wei Liao , Brian R. Murphy , Robert S. French , Monica S. Lam , Mary W. Hall, Multiprocessors from a Software Perspective, IEEE Micro, v.16 n.3, p.52-61, June 1996 [doi>10.1109/40.502406]
• 2: 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
• 3: and M. J. Irwin, DRAM Energy Management Using Sof ware and Hardware Directed Power Mode Control, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.159, January 20-24, 2001
• 4: Victor De La Luz , Mahmut Kandemir, Array Regrouping and Its Use in Compiling Data-Intensive Embedded Applications, IEEE Transactions on Computers, v.53 n.1, p.1-19, January 2004 [doi>10.1109/TC.2004.1255787]
• 5: X. Fan, C. S. Ellis, and A. R. Lebeck. Modeling of DRAM Power Control Policies Using Deterministic and Stochastic Petri Nets. In Proc. Workshop on Power-Aware Computer Systems, Springer-Verlag, February 2002.
• 6: Keith I. Farkas , Jason Flinn , Godmar Back , Dirk Grunwald , Jennifer M. Anderson, Quantifying the energy consumption of a pocket computer and a Java virtual machine, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.252-263, June 18-21, 2000, Santa Clara, California, United States
• 7: A. Farrahi, G. Tellez, and M. Sarrafzadeh. Exploiting Sleep Mode for Memory Partitions and Other Applications. VLSI Design, Vol. 7, No. 3, pp. 271--287.
• 8: W-M. W. Hwu. Embedded Microprocessor Comparison. http://www.crhc.uiuc.edu/IMPACT/ece412/public_html/Notes/412_lec1/ppframe.htm.
• 9: Milind B. Kamble , Kanad Ghose, Analytical energy dissipation models for low-power caches, Proceedings of the 1997 international symposium on Low power electronics and design, p.143-148, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263310]
• 10: Mahmut Kandemir , Ugur Sezer , Victor Delaluz, Improving memory energy using access pattern classification, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 11: Mahmut T. Kandemir , Ibrahim Kolcu , Ismail Kadayif, Influence of Loop Optimizations on Energy Consumption of Multi-bank Memory Systems, Proceedings of the 11th International Conference on Compiler Construction, p.276-292, April 08-12, 2002
• 12: Alvin R. Lebeck , Xiaobo Fan , Heng Zeng , Carla Ellis, Power aware page allocation, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.105-116, November 2000, Cambridge, Massachusetts, United States
• 13: S. -T. Leung and J. Zahorjan. Optimizing Data Locality by Array Restructuring. Technical Report TR 95-09-01, Dept. of Computer Science and Engineering, University of Washington, September 1995.
• 14: Wei Li, Compiling for numa parallel machines, Cornell University, Ithaca, NY, 1993
• 15: M. F. P. O'Boyle , P. M. W. Knijnenburg, Integrating Loop and Data Transformations for Global Optimisation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.12, October 12-18, 1998
• 16: 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
• 17: 128/144-MBit Direct RDRAM Data Sheet, Rambus Inc., May 1999.
• 18: 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
• 19: Ashok Sudarsanam , Sharad Malik, Simultaneous reference allocation in code generation for dual data memory bank ASIPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.242-264, April 2000 [doi>10.1145/335043.335047]
• 20: Wayne Wolf, Modern VLSI Design, Prentice Hall PTR, Upper Saddle River, NJ, 2002
• 21: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 22: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
affine program, bank locality, embedded systems, energy consumption, optimizing compilers