Efficient global register allocation for minimizing energy consumption

ABSTRACT

Data referencing during program execution can be a significant source of energy consumption especially for data-intensive programs. In this paper, we propose an approach to minimize such energy consumption by allocating data to proper registers and memory. Through careful analysis of boundary conditions between consecutive blocks, our approach efficiently handles various control structures including branches, merges and loops, and achieves the allocation results benefiting the whole program. The computational cost for solving the energy minimization allocation problem is rather low comparing with known approaches while the quality of the results are very encouraging.

REFERENCES

• 1: Andrew W. Appel, Modern Compiler Implementation in C: Basic Techniques, Cambridge University Press, New York, NY, 1997
• 2: Reinaldo A. Bergamaschi , Raul Camposano , Michael Payer, Allocation algorithms based on path analysis, Integration, the VLSI Journal, v.13 n.3, p.283-299, Sept. 1992 [doi>10.1016/0167-9260(92)90032-T]
• 3: T. Burd and Brad Peters, "A Power Analysis of a Microprocessor: A Study of an Implementation of the MIPS R3000 Architecture," Technical Report, University of California, Berkeley, 1994.
• 4: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 5: Martin C. Carlisle , Errol L. Lloyd, On the k-coloring of intervals, Discrete Applied Mathematics, v.59 n.3, p.225-235, May 26, 1995 [doi>10.1016/0166-218X(93)E0174-W]
• 6: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 7: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cooke, M. E. Hopkins, and P. W. Markstein, "Register allocation via graph coloring," Computer Language, vol. 6, 1981, pp. 47-57.
• 8: A. P. Chandrakasan, M. P. Potkonjak, R. Mehra, J. Rabaey, and R. W. Brodersen, "Optimizing power using transformations," IEEE Transactions on CAD of Integrated Circuits and Systems, vol. 14, no. 1, January 1995, pp. 12-30.
• 9: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 10: Paul M. Chirlian, Digital Circuits with Microprocessor Applications, Weber Systems Inc., Chesterland, OH, 1981
• 11: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 12: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 13: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 14: U. I. Gupta, D. T. Lee, and J. Y. Leung, "An optimal solution for the channel-assignment problem," IEEE Transactions on Computers, vol. c-28, no. 11, November 1979, pp. 807-810.
• 15: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 16: Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]
• 17: P. E. Landman and J. Rabaey, "Activity-sensitive architectural power analysis," IEEE Transactions on CAD of Integrated Circuits and Systems, vol. 15, no. 6, June 1996, pp. 571-587.
• 18: E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
• 19: E. Luque, A. Ripoll, and T. Diez, "Heuristic algorithms for register allocation," IEEE Proceedings-E, vol. 139, no. 1, January 1992, pp. 73-80.
• 20: Guei-Yuan Lueh , Thomas Gross , Ali-Reza Adl-Tabatabai, Global Register Allocation Based on Graph Fusion, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.246-265, August 08-10, 1996
• 21: Cindy Norris , Lori L. Pollock, The design and implementation of RAP: a PDG-based register allocator, Software—Practice & Experience, v.28 n.4, p.401-424, April 10, 1998 [doi>10.1002/(SICI)1097-024X(19980410)28:4<401::AID-SPE159>3.0.CO;2-R]
• 22: Massoud Pedram, Power minimization in IC design: principles and applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.3-56, Jan. 1996 [doi>10.1145/225871.225877]
• 23: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 24: Todd A. Proebsting , Charles N. Fischer, Demand-driven register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.683-710, Nov. 1996 [doi>10.1145/236114.236117]
• 25: J. Wang, Y. Jeang, M. Sheu, and J. Lee, "On the register allocation problems and algorithms," Proceedings of International Symposium on VLSI Technology, Systems, and Applications, 1989, pp. 126-128.
• 26: Nam-Sung Woo, A global, dynamic register allocation and binding for a data path synthesis system, Proceedings of the 27th ACM/IEEE conference on Design automation, p.505-510, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123384]
• 27: Y. Zhang, X. S. Hu, and D. Z. Chen, "Low energy register allocation beyond basic blocks" IEEE International Symposium on Circuits and Systems, 1999, pp. 290-293.
• 28: Yumin Zhang , Xiaobo (Sharon) Hu , Danny Z. Chen, Global register allocation for minimizing energy consumption, Proceedings of the 1999 international symposium on Low power electronics and design, p.100-102, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313877]

INDEX TERMS

Keywords:
low energy, register allocation