Exploiting the structure of conflict graphs in high level synthesis

Klaus Jansen

Commentationes Mathematicae Universitatis Carolinae (1994)

  • Volume: 35, Issue: 1, page 155-167
  • ISSN: 0010-2628

Abstract

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

How to cite

top

Jansen, Klaus. "Exploiting the structure of conflict graphs in high level synthesis." Commentationes Mathematicae Universitatis Carolinae 35.1 (1994): 155-167. <http://eudml.org/doc/247600>.

@article{Jansen1994,
abstract = {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.},
author = {Jansen, Klaus},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {independent set; chromatic number; high level synthesis; flow graphs},
language = {eng},
number = {1},
pages = {155-167},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Exploiting the structure of conflict graphs in high level synthesis},
url = {http://eudml.org/doc/247600},
volume = {35},
year = {1994},
}

TY - JOUR
AU - Jansen, Klaus
TI - Exploiting the structure of conflict graphs in high level synthesis
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1994
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 35
IS - 1
SP - 155
EP - 167
AB - 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.
LA - eng
KW - independent set; chromatic number; high level synthesis; flow graphs
UR - http://eudml.org/doc/247600
ER -

References

top
  1. 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. Zbl0527.68049
  2. 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. Zbl0864.68074
  3. Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NPCompletness, Freeman, San Francisco, 1979. MR0519066
  4. Jansen K., Processor optimization for flow graphs, Theor. Comput. Sci. 104 (1992), 285-298. (1992) Zbl0754.68062MR1186182
  5. Jansen K., The allocation problem in hardware design, Disc. Appl. Math. 43 (1993), 37-46. (1993) Zbl0776.68094MR1218041
  6. Lawler E.L., Combinatorial Optimization: Networks and Matroids, Rinehard and Winston, New York, 1976. Zbl1058.90057MR0439106
  7. Pfahler P., Übersetzermethoden zur automatischen Hardware-Synthese, Thesis, University of Paderborn, FRG, 1988. 
  8. Rajan J.V., Automatic synthesis of data paths in digital systems, PhD thesis, Carnegie Mellon University, Dec 1988. 
  9. Robertson N., Seymour P., Graph minors. I. Excluding a forest, J. Comb. Theory B 35 (1983), 39-61. (1983) Zbl0521.05062MR0723569
  10. Springer D.L., Thomas D.E., Exploiting the special structure of conflict and compatibility graphs in high-level synthesis, ICCAD (1990), 254-257. 
  11. Tseng C.J., Siewiorek D.P., Automated synthesis of data paths in digital systems, IEEE Trans. Comp.-Aided Design 5 (1986), 379-395. (1986) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.