Energy-aware variable partitioning and instruction scheduling for multibank memory architectures

ABSTRACT

Many high-end DSP processors employ both multiple memory banks and heterogeneous register files to improve performance and power consumption. The complexity of such architectures presents a great challenge to compiler design. In this article, we present an approach for variable partitioning and instruction scheduling to maximally exploit the benefits provided by such architectures. Our approach is built on a novel graph model which strives to capture both performance and power demands. We propose an algorithm to iteratively find the variable partition such that the maximum energy saving is achieved while satisfying the given performance constraint. Experimental results demonstrate the effectiveness of our approach.

REFERENCES

• 1: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: Luca Benini , Alberto Macii , Massimo Poncino, A recursive algorithm for low-power memory partitioning, Proceedings of the 2000 international symposium on Low power electronics and design, p.78-83, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344518]
• 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: Jeonghun Cho , Yunheung Paek , David Whalley, Efficient register and memory assignment for non-orthogonal architectures via graph coloring and MST algorithms, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 5: Victor Delaluz , Mahmut Kandemir , N. Vijaykrishnan , Anand Sivasubramaniam , Mary Jane Irwin, Hardware and Software Techniques for Controlling DRAM Power Modes, IEEE Transactions on Computers, v.50 n.11, p.1154-1173, November 2001 [doi>10.1109/12.966492]
• 6: V. Delaluz , A. Sivasubramaniam , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Scheduler-based DRAM energy management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514095]
• 7: Desoli, G. 1998. Instruction assignment for clustered VLIW DSP compilers: A new approach. Tech. Rep. HPL-98-13. Hewlett-Packard Company, Palo alto, CA.
• 8: Goldschmidt, O. and Hochbaum, D. S. 1998. Polynomial algorithm for the k-cut problem. In Proceedings of the 29th Annual Symposium on the Foundations of Computer Science. 444--451.
• 9: Sungjoon Jung , Yunheung Paek, The very portable optimizer for digital signal processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502230]
• 10: Leupers, R. and Kotte, D. 2001. Variable partitioning for dual memory bank DSPS. In Proceedings of ICASSP.
• 11: Markus Lorenz , David Koffmann , Steven Bashford , Rainer Leupers , Peter Marwedel, Optimized address assignment for DSPs with SIMD memory accesses, Proceedings of the 2001 conference on Asia South Pacific design automation, p.415-420, January 2001, Yokohama, Japan [doi>10.1145/370155.370430]
• 12: Yung-Hsiang Lu , Luca Benini , Giovanni De Micheli, Low-power task scheduling for multiple devices, Proceedings of the eighth international workshop on Hardware/software codesign, p.39-43, May 2000, San Diego, California, United States [doi>10.1145/334012.334020]
• 13: V. De La Luz , M. Kandemir , I. Kolcu, Automatic data migration for reducing energy consumption in multi-bank memory systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513973]
• 14: Micron. 1999. 1mb syncburst SRAM data sheet. Micron Technology Inc., Boise, ID. Website: www.micron.com.
• 15: Prim, R. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 6.
• 16: Rambus. 1999. 128/144-mbit direct RDRAM data sheet. Rambus Inc., Losaltos, CA. Website: www.rambus.com.
• 17: 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
• 18: 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]
• 19: Wang, Z. and Hu, X. S. 2004. Variable partitioning and scheduling for multiple memory banks. Tech. rep. CSE Dept., University of Notre Dame, Notre Dame, IN.
• 20: Sven Wuytack , Francky Catthoor , Gjalt de Jong , Hugo J. De Man, Minimizing the required memory bandwidth in VLSI system realizations, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.4, p.433-441, Dec. 1999 [doi>10.1109/92.805750]
• 21: Zeithofer, T. and Wess, B. 2001. Integrated scheduling and register assignment for VLIW--DSP architectures. In Proceedings of the 14th Annual IEEE International ASIC/SOC Conference. 339--343.
• 22: Zhuge, Q., Xiao, B., and Sha, E. H.-M. 2001. Exploring variable partitioning in dual data-memory bank processors. In Proceedings of the 34th International Symposium on Micro-Architecture (MICRO-34), the 3rd Workshop on Media and Streaming Processors (MSP-3 Workshop). 42--55.
• 23: Zivoljnovic, V., Velarde, J., Schager, C., and Meyr, H. 1994. Dspstone---a DSP oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing Applications and Technology.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Algorithms, Performance

Keywords:
Multiple memory banks, instruction scheduling, nonorthogonal architecture, operating mode, parallelism and serialism balance, runtime and energy saving tradeoff