More Web Proxy on the site http://driver.im/

article

Efficient global register allocation for minimizing energy consumption

Authors:

Xiaobo (Sharon) Hu,

Danny Z. ChenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 37, Issue 4

Pages 42 - 53

https://doi.org/10.1145/510857.510867

Published: 01 April 2002 Publication History

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]

A. W. Appel, Modern Compiler Implementation in C, Cambridge University Press, 1997.

Digital Library

[2]

R. A. Berganaschi, R. Camposano, and M. Payer, "Allocation algorithms based on path analysis," The VLSI Journal, 1992, pp. 283-299.

Digital Library

[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]

D. Callahan and B. Koblenz, "Register allocation via hierarchical graph coloring," ACM SIGPLAN, 1991, pp. 192-203.

Digital Library

[5]

M. C. Carlisle and E. L. Lloyd, "On the k-coloring of intervals," Applied Discrete Mathematics, vol. 59, no. 3, May 1995, pp. 225-235.

Digital Library

[6]

G. J. Chaitin, "Register allocation and spilling via graph coloring," ACM SIGPLAN Symposium on Compiler Constructions, 1982, pp. 98-101.

Digital Library

[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.

Digital Library

[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.

Digital Library

[9]

J. Chang and M. Pedram, "Register allocation and binding for lower power," Design Automation Conference, 1995, pp. 29-35.

Digital Library

[10]

P. M. Chirlian, Digital Circuits with Microprocessor Applications, Matrix Publishers, INC., 1982.

Digital Library

[11]

F. C. Chow and J. L. Hennessy, "The priority-based coloring approach to register allocation," ACM Transactions on Programming Languages and Systems, vol. 12, no. 4, October 1990, pp. 501-536.

Digital Library

[12]

C. H. Gebotys, "Low energy memory and register allocation using network flow," Design Automation Conference, 1997, pp. 435-440.

Digital Library

[13]

D. W. Goodwin and K. D. Wilken, "Optimal and near-optimal global register allocation using 0-1 integer programming," Software Practice and Experience, vol. 26(8), August 1996, pp. 929-965.

Digital Library

[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.

Digital Library

[15]

J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 2nd edition. Morgan Kaufmann Publishers, 1996.

Digital Library

[16]

W. Hsu, C. N. Fischer, and J. R. Goodman, "On the minimization of loads/stores in local register allocation," IEEE Transactions on Software Engineering, vol. 15, no. 10, 1989, pp. 1252-1260.

Digital Library

[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.

Digital Library

[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]

G. Lueh, T. Gross, and A. Adl-Tabatabai, "Global register allocation based on graph fusion," Proceedings of LCPC, 1996, pp. 246-265.

Digital Library

[21]

C. Norris and L. Pollock, "The design and implementation of RAP: a PDG-based register allocator," Software-Practice and Experience, vol. 28, no. 4, April 1998, pp. 401-424.

Digital Library

[22]

M. Pedram, "Power minimization in IC design: Principles and applications," ACM Transactions on Design Automation of Electronic Systems, vol. 1, no. 1, January 1996, pp. 3-56.

Digital Library

[23]

C. H. Papadimitriou and K. Steiglitz Combinatorial Optimization, Prentice-Hall, Inc., 1982.

Digital Library

[24]

T. A. Proebsting and C. N. Fischer, "Demand-driven register allocation," ACM Transactions on Programming Languages and Systems, vol. 18, no. 6, November 1996, pp. 683-710.

Digital Library

[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]

N. Woo, "A global dynamic register allocation and binding," Design Automation Conference, 1990, pp. 505-510.

Digital Library

[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]

Y. Zhang, X. S. Hu, and D. Z. Chen, "Global register allocation for minimizing energy consumption" International Symposium on Low Power Electronic and Design, 1999, pp. 100-102.

Digital Library

Cited By

Anand VXie ZStolet MDe Viti RDavidson TKarimipour RAlzayat SMace J(2023)The Odd One Out: Energy is Not Like Other MetricsACM SIGEnergy Energy Informatics Review10.1145/3630614.36306273:3(71-77)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1145/3630614.3630627
Luna MSilva FAttrot W(2015)Decreasing Spill Code to Decrease Energy ConsumptionProceedings of the 2015 Brazilian Symposium on Computing Systems Engineering (SBESC)10.1109/SBESC.2015.31(128-131)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1109/SBESC.2015.31
Wang YJia ZChen RWang MLiu DShao Z(2014)Loop scheduling with memory access reduction subject to register constraints for DSP applicationsSoftware—Practice & Experience10.1002/spe.218644:8(999-1026)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1002/spe.2186
Show More Cited By

Recommendations

A framework for energy consumption based design space exploration for wireless sensor nodes
ISLPED '08: Proceedings of the 2008 international symposium on Low Power Electronics & Design

In wireless sensor networks due to the small transmission distances involved, the computation energy along with the radio energy determines the battery life. Energy consumption of error control codes (ECCs) is a complex function of the energy ...
Lifetime holes aware register allocation for clustered VLIW processors
DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

This paper presents an on-the-fly register allocator which dynamically detects and utilises lifetime holes for clustered VLIW processors. A lifetime hole is an interval in which a variable does not contain a valid value. A register holding a lifetime ...
Register allocation for embedded systems to simultaneously reduce energy and temperature on registers

Energy and thermal issues are two important concerns for embedded system design. Diminished energy dissipation leads to a longer battery life, while reduced temperature hotspots decelerate the physical failure mechanisms. The instruction fetch logic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 37, Issue 4

April 2002

64 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/510857

Issue’s Table of Contents

Copyright © 2002 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2002

Published in SIGPLAN Volume 37, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
293
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anand VXie ZStolet MDe Viti RDavidson TKarimipour RAlzayat SMace J(2023)The Odd One Out: Energy is Not Like Other MetricsACM SIGEnergy Energy Informatics Review10.1145/3630614.36306273:3(71-77)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1145/3630614.3630627
Luna MSilva FAttrot W(2015)Decreasing Spill Code to Decrease Energy ConsumptionProceedings of the 2015 Brazilian Symposium on Computing Systems Engineering (SBESC)10.1109/SBESC.2015.31(128-131)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1109/SBESC.2015.31
Wang YJia ZChen RWang MLiu DShao Z(2014)Loop scheduling with memory access reduction subject to register constraints for DSP applicationsSoftware—Practice & Experience10.1002/spe.218644:8(999-1026)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1002/spe.2186
Liu TOrailoglu AXue CLi M(2013)Register allocation for embedded systems to simultaneously reduce energy and temperature on registersACM Transactions on Embedded Computing Systems10.1145/2539036.253904613:3(1-26)Online publication date: 24-Dec-2013
https://dl.acm.org/doi/10.1145/2539036.2539046
Raghavan PCatthoor F(2012)Storage Allocation for Streaming-Based Register FileEnergy-Aware Memory Management for Embedded Multimedia Systems10.1201/b11418-6(151-194)Online publication date: 4-Jan-2012
https://doi.org/10.1201/b11418-6
Tiantian Liu Orailoglu AXue CMinming Li (2011)Register allocation for simultaneous reduction of energy and peak temperature on registers2011 Design, Automation & Test in Europe10.1109/DATE.2011.5763010(1-6)Online publication date: Mar-2011
https://doi.org/10.1109/DATE.2011.5763010
Catthoor FRaghavan PLambrechts AJayapala MKritikakou AAbsar JCatthoor FRaghavan PLambrechts AJayapala MKritikakou AAbsar J(2010)Global State-of-the-Art OverviewUltra-Low Energy Domain-Specific Instruction-Set Processors10.1007/978-90-481-9528-2_2(17-32)Online publication date: 3-Jul-2010
https://doi.org/10.1007/978-90-481-9528-2_2
Raghavan PCatthoor FRosenstiel WWakabayashi K(2009)SARAProceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1629435.1629442(41-50)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629435.1629442
Wang MLiu DWang YShao Z(2009)Loop scheduling with memory access reduction under register constraints for DSP applications2009 IEEE Workshop on Signal Processing Systems10.1109/SIPS.2009.5336239(139-144)Online publication date: Oct-2009
https://doi.org/10.1109/SIPS.2009.5336239
Chen DCong JFan YZhang Z(2007)High-Level Power Estimation and Low-Power Design Space Exploration for FPGAsProceedings of the 2007 Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2007.358040(529-534)Online publication date: 23-Jan-2007
https://dl.acm.org/doi/10.1109/ASPDAC.2007.358040

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents