Optimal Register Sharing for High-Level Synthesis of SSA Form Programs Conference Paper

abstract

• Register sharing for high-level synthesis of programs represented in static single assignment (SSA) form is proven to have a polynomial-time solution. Register sharing is modeled as a graph-coloring problem. Although graph coloring is NP-Complete in the general case, an interference graph constructed for a program in SSA form probably belongs to the class of chordal graphs that have an optimal O(|V| + E) time algorithm. Chordal graph coloring reduces the number of registers allocated to the program by as much as 86 % and 64.93 % on average compared to linear scan register allocation. 2006 IEEE.

authors

• Jafari, Roozbeh

published proceedings

• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

author list (cited authors)

• Brisk, P., Dabiri, F., Jafari, R., & Sarrafzadeh, M.

citation count

• 22

complete list of authors

• Brisk, Philip||Dabiri, Foad||Jafari, Roozbeh||Sarrafzadeh, Majid

publication date

• May 2006

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems  Journal

Digital Object Identifier (DOI)

• 10.1109/tcad.2006.870409

start page

• 772

end page

• 779

volume

• 25

issue

• 5

URL

• http://dx.doi.org/10.1109/tcad.2006.870409