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 t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 1994-07, Vol.13 (7), p.843-856
Main Authors: Springer, D.L., Thomas, D.E.
Format: Article
Language:English
Subjects:
Applied sciences
Control system synthesis
Design. Technologies. Operation analysis. Testing
Electronics
Exact sciences and technology
Flow graphs
Graph theory
Hardware design languages
High level synthesis
Integrated circuits
Partitioning algorithms
Polynomials
Processor scheduling
Registers
Scheduling algorithm
Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:0278-0070
1937-4151
DOI:10.1109/43.293941