Energy efficient address assignment through minimized memory row switching

ABSTRACT

Data transfer intensive applications consume a significant amount of energy in memory access. The selection of a memory location from a memory array involves driving row and column select lines. A signal transition on a row select line often consumes significantly more energy than a transition on a column select line. In order to exploit this difference in energy consumption of row and column select lines, we propose a novel address assignment methodology that aims to minimize high energy row transitions by assigning spatially and temporally local data items to the same row. The problem of energy efficient address assignment has been formulated as a multi-way graph partitioning problem and solved with a heuristic. Our experiments demonstrate that our methodology achieves row transition counts very close to the optimum and that the methodology can, for some examples, reduce row transition count by 40--70% over row major mapping. Moreover, we also demonstrate that our methodology is capable of handling access sequences with over 15 million accesses in moderate time.

REFERENCES

• 1: P. Baglietto, M. Maresca, M. Migliardi, and N. Zingirian. Image processing on high-performance RISC systems. Proceedings of the IEEE, 84:917--930, July 1996.
• 2: Luca Benini , Giovanni de Micheli, System-level power optimization: techniques and tools, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.115-192, April 2000 [doi>10.1145/335043.335044]
• 3: R. J. Evans and P. D. Franzon. Energy consumption modeling and optimization for SRAM's. IEEE Journal of Solid-State Circuits, 30:571--579, May 1995.
• 4: P. Fjallstrom. Algorithms for graph partitioning: A survey, 1998.
• 5: M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problem. Theoretical computer science, 1:237--267, 1976.
• 6: Douglas M. Grant , Peter B. Denyer, Address Generation for array access based on modulus m counters, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 7: B. Hendrickson and R. Leland. The Chaco user's guide, version 2.0. Technical Report SAND95-2344, Sandia National Laboratories, July 1995. User Manual.
• 8: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 9: S. Hettiaratchi , P. Cheung , T. Clarke, Performance-Area Trade-Off of Address Generators for Address Decoder-Decoupled Memory, Proceedings of the conference on Design, automation and test in Europe, p.902, March 04-08, 2002
• 10: Harley R. Myler , Arthur R. Weeks, Computer imaging recipes in C, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 11: 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]
• 12: P. R. Panda and N. Dutt. Low power memory mapping through reducing address bus activity. Technical Report 95--32, University of California, Irvine, Nov. 1995.
• 13: Precti Ranjan Panda , Nikil D. Dutt, Low-power memory mapping through reducing address bus activity, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.3, p.309-320, Sept. 1999 [doi>10.1109/92.784092]
• 14: Herman Schmit , Donald E. Thomas, Synthesis of application-specific memory designs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.101-111, March 1997 [doi>10.1109/92.555990]
• 15: I. Verbauwhede, F. Catthoor, J. Vandewalle, and H. D. Man. Background memory management for the synthesis of algebraic algorithms on multi-processor DSP chips. In Proceedings of the International Conference on VLSI, pages 209--218, Aug. 1989.
• 16: S. Wuytack, F. Catthoor, F. Franssen, L. Nachtergaele, and H. D. Man. Global communication and memory optimizing transformations for low power systems. In IEEE International Workshop on Low Power Design, pages 203--208, Apr. 1994.
• 17: Sven Wuytack , Jean-Philippe Diguet , Francky V. M. Catthoor , Hugo J. De Man, Formalized methodology for data reuse exploration for low-power hierarchical memory mappings, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.529-537, Dec. 1998 [doi>10.1109/92.736124]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
address assignment, data layout, memory synthesis