Exploiting the structure of conflict graphs in high level synthesis
Commentationes Mathematicae Universitatis Carolinae (1994)
- Volume: 35, Issue: 1, page 155-167
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topJansen, 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- Arnborg S., Proskurowski A., Linear time algorithms for NP-hard problems on graphs embedded in -trees, TRITA-NA-8404, Dept. of Num. Anal. and Comp. Sci, Royal Institute of Technology, Stockholm, Sweden, 1984. Zbl0527.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. Zbl0864.68074
- Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NPCompletness, Freeman, San Francisco, 1979. MR0519066
- Jansen K., Processor optimization for flow graphs, Theor. Comput. Sci. 104 (1992), 285-298. (1992) Zbl0754.68062MR1186182
- Jansen K., The allocation problem in hardware design, Disc. Appl. Math. 43 (1993), 37-46. (1993) Zbl0776.68094MR1218041
- Lawler E.L., Combinatorial Optimization: Networks and Matroids, Rinehard and Winston, New York, 1976. Zbl1058.90057MR0439106
- 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) Zbl0521.05062MR0723569
- 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)
NotesEmbed ?
topYou 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.