Exploiting the structure of conflict graphs in high level synthesis
Jansen, Klaus
Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994), p. 155-167 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

In this paper we analyze the computational complexity of a processor optimization problem. Given operations with interval times in a branching flow graph, the problem is to find an assignment of the operations to a minimum number of processors. We analyze the complexity of this assignment problem for flow graphs with a constant number of program traces and a constant number of processors.

Publié le : 1994-01-01
Classification:  05C15,  05C85,  68Q25,  68R10 
@article{118649,
     author = {Klaus Jansen},
     title = {Exploiting the structure of conflict graphs  in high level synthesis},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {35},
     year = {1994},
     pages = {155-167},
     zbl = {0806.68058},
     mrnumber = {1292591},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118649}
}

Jansen, Klaus. Exploiting the structure of conflict graphs  in high level synthesis. Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994) pp. 155-167. http://gdmltest.u-ga.fr/item/118649/

Arnborg S.; Proskurowski A. Linear time algorithms for NP-hard problems on graphs embedded in $k$-trees, TRITA-NA-8404, Dept. of Num. Anal. and Comp. Sci, Royal Institute of Technology, Stockholm, Sweden, 1984. | Zbl 0527.68049

Bodlaender H.L. A linear time algorithm for finding tree-decompositions of small treewidth, Report RUU-CS-92-27, Dept. of Computer Sci., Utrecht University, 1992. | Zbl 0864.68074

Garey M.R.; Johnson D.S. Computers and Intractability: A Guide to the Theory of NPCompletness, Freeman, San Francisco, 1979. | MR 0519066

Jansen K. Processor optimization for flow graphs, Theor. Comput. Sci. 104 (1992), 285-298. (1992) | MR 1186182 | Zbl 0754.68062

Jansen K. The allocation problem in hardware design, Disc. Appl. Math. 43 (1993), 37-46. (1993) | MR 1218041 | Zbl 0776.68094

Lawler E.L. Combinatorial Optimization: Networks and Matroids, Rinehard and Winston, New York, 1976. | MR 0439106 | Zbl 1058.90057

Pfahler P. Übersetzermethoden zur automatischen Hardware-Synthese, Thesis, University of Paderborn, FRG, 1988.

Rajan J.V. Automatic synthesis of data paths in digital systems, PhD thesis, Carnegie Mellon University, Dec 1988.

Robertson N.; Seymour P. Graph minors. I. Excluding a forest, J. Comb. Theory B 35 (1983), 39-61. (1983) | MR 0723569 | Zbl 0521.05062

Springer D.L.; Thomas D.E. Exploiting the special structure of conflict and compatibility graphs in high-level synthesis, ICCAD (1990), 254-257.

Tseng C.J.; Siewiorek D.P. Automated synthesis of data paths in digital systems, IEEE Trans. Comp.-Aided Design 5 (1986), 379-395. (1986)