Skip to main content
eScholarship
Open Access Publications from the University of California

Optimal register sharing for high-level synthesis of SSA form programs

  • Author(s): Brisk, P
  • Dabiri, F
  • Jafari, R
  • Sarrafzadeh, M
  • et al.
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 NIP-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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View