Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/TCAD.2006.870409 | IEEE Trans. on CAD of Integrated Circuits and Systems |
Keywords | DocType | Volume |
SSA form program,high-level synthesis,register allocation,register sharing,interference graph,chordal graph coloring,graph-coloring problem,SSA form,chordal graph,general case,optimal register sharing,graph coloring | Journal | 25 |
Issue | ISSN | Citations |
5 | 0278-0070 | 16 |
PageRank | References | Authors |
0.67 | 17 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philip Brisk | 1 | 80 | 10.05 |
| Foad Dabiri | 2 | 288 | 27.01 |
| Roozbeh Jafari | 3 | 987 | 93.51 |
| M. Sarrafzadeh | 4 | 635 | 63.19 |