research-article

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Authors:

Paolo IenneAuthors Info & Claims

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

Pages 172 - 179

Published: 05 November 2007 Publication History

Abstract

Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is spilled to memory. Previously, an optimal polynomial-time algorithm for this problem has been presented for individual procedures represented in Static Single Assignment (SSA) Form. This result is now extended to complete programs (or sub-programs), as long as: (1) each procedure is represented in SSA Form; and (2) at every procedure call, all live variables are split at the call point. With this representation, it is possible to ensure that the interprocedural interference graph (IIG) is chordal, and can therefore be colored optimally in polynomial time. An optimal coloring of the IIG can be achieved by allocating registers for each procedure individually. Previous work has shown that optimal register allocation in SSA Form does not require an interference graph. Optimal interprocedural register allocation, therefore, is achieved without constructing an interference graph, giving the optimal algorithm a significant runtime advantage over prior sub-optimal heuristics.

References

[1]

R. Beidas and J. Zhu, "Scalable interprocedural register allocation for high-level synthesis," Asia South Pacific Design Automation Conf., Shanghai, China, pp. 511--516, January 2005.

Digital Library

[2]

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, "Register allocation and spill complexity under SSA," Technical Report 2005-33, ENS-Lyon, Lyon, France, 2005.

[3]

F. Bouchez, A. Darte, and F. Rastello, "On the compleixty of register coalescing" Int. Symp. Code Generation and Optimization, San Jose, CA, USA, pp. 102--114, March 2007.

Digital Library

[4]

F. Bouchez, A. Darte, and F. Rastello, "On the compleixty of spill everywhere under SSA form" Conf. Languages, Compilers, and Tools for Embedded Systems, San Diego, CA, USA, pp. 103--112, June 2007.

Digital Library

[5]

P. Briggs, K. D. Cooper, T. J. Harvey, and L. T. Simpson, "Practical improvements to the construction and destruction of static single assignment form," Software---Practice and Experience, vol. 28, no. 8, pp. 859--881, July 1998.

Digital Library

[6]

P. Briggs, K. D. Cooper, and L. Torczon, "Improvements to graph coloring register allocation," ACM Trans. Programming Languages and Systems, vol. 16, no. 3, pp. 428--455, May 1994.

Digital Library

[7]

P. Brisk, F. Dabiri, R. Jafari, and M. Sarrafzadeh, "Optimal register sharing for high-level synthesis of SSA form programs," IEEE Trans. Computer-Aided Design, vol. 25, no. 5, pp. 772--779, May 2006.

Digital Library

[8]

G. J. Chaitin, "Register allocaiton and spilling via graph coloring," SIGPLAN Symp. Compiler Construction, Boston, MA, USA, pp. 98--101, June 1982.

Digital Library

[9]

F. Chow, "Minimizing register usage penalty at procedure calls," Int. Conf. Programming Language Design and Implementation, Atlanta, GA, USA, pp. 85--94, June 1988.

Digital Library

[10]

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, "The strong perfect graph theorem," Annals of Mathematics, vol. 164, no. 1, pp. 51--229, July, 2006.

[11]

K. D. Cooper and L. Torczon, Engineering a Compiler, San Francisco: Morgan-Kaufmann, 2003.

[12]

M. Farach-Colton and V. Liberatore, "On local register allocation," J. Algorithms, vol. 37, no. 1, pp. 37--65, October 2000.

Digital Library

[13]

F. Gavril, "Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph," SIAM J. Comput., vol. 1, no. 2, pp. 180--187, June 1972.

Digital Library

[14]

D. Grund and S. Hack, "A fast cutting-plane algorithm for optimal coalescing," Int. Conf. Compiler Construction, Lisbon, Portugal, pp. 111--125, March 2007.

Digital Library

[15]

M. R. Guthaus, et al., "MiBench: a free commercially representative embedded benchmark suite," Workshop on Workload Characterziation, Austin, TX, USA, pp. 3--14, December 2001.

Digital Library

[16]

S. Hack and G. Goos, "Optimal register allocation for SSA-form programs in polynomial time," Information Processing Letters, vol. 98, no. 4, pp. 150--155, May 2006.

Digital Library

[17]

S. Hack, D. Grund, and G. Goos, "Register allocation for programs in SSA-form," Int. Conf. Compiler Construction, Vienna, Austria, pp. 247--262, March 2006.

Digital Library

[18]

A. B. Kempe, "On the geographical problem of the four colors," American Journal of Mathematics, vol. 2, pp. 193--200, 1879.

[19]

F. J. Kurdahi and A. C. Parker, "REAL: a porgrma for register allocation," Design Automation Conf. Miami Beach, FL, USA, pp. 210--215, June-July 1987.

Digital Library

[20]

S. M. Kurlander and C. N. Fischer, "Minimum cost interprocedural register allocation," Symp. Principles of Programming Languages, St. Petersburg Beach, FL, USA, pp. 230--241, January 1996.

Digital Library

[21]

C. Lee, M. Potkonjak, and W. H. Mangione-Smith, "MediaBench: a tool for evaluating and synthesizing multimedia and communications systems," Int. Symp. Microarchitecture, Research Triangle Park, NC, USA, pp. 330--335, December 1997.

Digital Library

[22]

D. W. Matula and L. L. Beck, "Smallest last-ordering and clustering graph coloring algorithms," Journal of the ACM, vol. 30, no. 3, pp. 417--427, July 1983.

Digital Library

[23]

R. Muth and S. K. Debray, "On the comlexity of function pointer may-alias analysis," Int. Joint Conf. CAAP/FASE on Theory and Practice of Software Development, Lille, France, pp. 381--392, April 1997.

Digital Library

[24]

B. Pangrle, "On the complexity of connectivity binding," IEEE Trans. Computer Aided Design, vol. 10, no. 11, pp. 1460--1465, November 1991.

Digital Library

[25]

H. H. Seward, "Information sorting in the application of electronic digital copmuters to business operations," M.S. Thesis, Masschusetts Institute of Technology, 1954.

[26]

M. D. Smith and G. Holloway, "An introduction to Machine SUIF and its portable libraries for analysis and optimization," Technical Report, Harvard University, 2002. Available online.

[27]

D. L. Springer and D. E. Thomas, "Exploiting the special structure of conflict and compatibility grpahs in high-level synthesis," IEEE Trans. Computer Aided Design, vol. 13, no. 7, pp. 843--856, July 1994.

Digital Library

[28]

R. E. Tarjan, "Depth-first search and linear graph algorithms," SIAM J. Comput., vol. 1, no. 2, pp. 146--160, June 1972.

Digital Library

[29]

R. E. Tarjan and M. Yannakakis, "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs," SIAM J. Comput., vol. 13, no. 3, pp. 566--579, August 1984.

Digital Library

[30]

C-J. Tseng and D. P. Siewiorek, "Automated synthesis of data paths in digital systems," IEEE Trans. Computer Aided Design, vol. 5, no. 3, pp. 379--395, July, 1986.

Digital Library

[31]

R. Vemuri, S. Katkoori, M. Kaul, and J. Roy, "An efficient register optimization algorithm for high-level synthesis from hierarhical behavioral specifications," ACM Trans. Design Automation of Electronic Systems, vol. 7, no. 1, pp. 189--216, January 2002.

Digital Library

[32]

S. Zhang and B. G. Ryder, "Complexity of single level function pointer aliasing analysis," Tech. Report LCSR-TR-233, Laboratory of Computer Science Research, Rutgers University, October 1994.

Cited By

Fowers JStitt GHutchings BBetz V(2013)DynafuseProceedings of the ACM/SIGDA international symposium on Field programmable gate arrays10.1145/2435264.2435300(201-210)Online publication date: 11-Feb-2013
https://dl.acm.org/doi/10.1145/2435264.2435300
Gomathisankaran MMehta GNamuduri K(2010)Power, performance and security optimized hardware design for H.264Proceedings of the Sixth Annual Workshop on Cyber Security and Information Intelligence Research10.1145/1852666.1852735(1-4)Online publication date: 21-Apr-2010
https://dl.acm.org/doi/10.1145/1852666.1852735
Mehta GStander JBaz MHunsaker BJones A(2009)Interconnect customization for a hardware fabricACM Transactions on Design Automation of Electronic Systems10.1145/1455229.145524014:1(1-32)Online publication date: 23-Jan-2009
https://dl.acm.org/doi/10.1145/1455229.1455240

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Approaches to interprocedural register allocation
An optimal linear-time algorithm for interprocedural register allocation in high level synthesis using SSA form

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ...
Optimal register allocation in polynomial time
CC'13: Proceedings of the 22nd international conference on Compiler Construction

A graph-coloring register allocator that optimally allocates registers for structured programs in polynomial time is presented. It can handle register aliasing. The assignment of registers is optimal with respect to spill and rematerialization costs, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
167
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fowers JStitt GHutchings BBetz V(2013)DynafuseProceedings of the ACM/SIGDA international symposium on Field programmable gate arrays10.1145/2435264.2435300(201-210)Online publication date: 11-Feb-2013
https://dl.acm.org/doi/10.1145/2435264.2435300
Gomathisankaran MMehta GNamuduri K(2010)Power, performance and security optimized hardware design for H.264Proceedings of the Sixth Annual Workshop on Cyber Security and Information Intelligence Research10.1145/1852666.1852735(1-4)Online publication date: 21-Apr-2010
https://dl.acm.org/doi/10.1145/1852666.1852735
Mehta GStander JBaz MHunsaker BJones A(2009)Interconnect customization for a hardware fabricACM Transactions on Design Automation of Electronic Systems10.1145/1455229.145524014:1(1-32)Online publication date: 23-Jan-2009
https://dl.acm.org/doi/10.1145/1455229.1455240

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.

Figures

Tables

Media

View Table of Conten