Exploiting the special structure of conflict and compatibility graphs in high-level synthesis

Coloring of conflict graphs and clique partitioning of compatibility graphs have been used in high-level synthesis to map operators, values, and data transfers onto shared resources. However, finding a minimum sized coloring or clique partition is NP hard. One method to overcome this complexity is to identify special types of graphs that can be colored or clique partitioned in polynomial time. Existing high-level synthesis systems have exploited two special types of conflict graphs-interval and circular-arc graphs. However, they have provided no insight into why and how frequently these graphs occur. This paper will investigate the features of behavioral representations and synthesis algorithms that give rise to special conflict and compatibility graphs. We will identify two additional types of graphs useful for high-level synthesis-chordal and comparability graphs-and demonstrate their use in an existing high-level synthesis system