| Title:
|
Exploiting the structure of conflict graphs in high level synthesis (English) |
| Author:
|
Jansen, Klaus |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
35 |
| Issue:
|
1 |
| Year:
|
1994 |
| Pages:
|
155-167 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
independent set |
| Keyword:
|
chromatic number |
| Keyword:
|
high level synthesis |
| MSC:
|
05C15 |
| MSC:
|
05C85 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0806.68058 |
| idMR:
|
MR1292591 |
| . |
| Date available:
|
2009-01-08T18:09:34Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118649 |
| . |
| Reference:
|
[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. Zbl 0527.68049 |
| Reference:
|
[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. Zbl 0864.68074 |
| Reference:
|
[3] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NPCompletness.Freeman, San Francisco, 1979. MR 0519066 |
| Reference:
|
[4] Jansen K.: Processor optimization for flow graphs.Theor. Comput. Sci. 104 (1992), 285-298. Zbl 0754.68062, MR 1186182 |
| Reference:
|
[5] Jansen K.: The allocation problem in hardware design.Disc. Appl. Math. 43 (1993), 37-46. Zbl 0776.68094, MR 1218041 |
| Reference:
|
[6] Lawler E.L.: Combinatorial Optimization: Networks and Matroids.Rinehard and Winston, New York, 1976. Zbl 1058.90057, MR 0439106 |
| Reference:
|
[7] Pfahler P.: Übersetzermethoden zur automatischen Hardware-Synthese.Thesis, University of Paderborn, FRG, 1988. |
| Reference:
|
[8] Rajan J.V.: Automatic synthesis of data paths in digital systems.PhD thesis, Carnegie Mellon University, Dec 1988. |
| Reference:
|
[9] Robertson N., Seymour P.: Graph minors. I. Excluding a forest.J. Comb. Theory B 35 (1983), 39-61. Zbl 0521.05062, MR 0723569 |
| Reference:
|
[10] Springer D.L., Thomas D.E.: Exploiting the special structure of conflict and compatibility graphs in high-level synthesis.ICCAD (1990), 254-257. |
| Reference:
|
[11] Tseng C.J., Siewiorek D.P.: Automated synthesis of data paths in digital systems.IEEE Trans. Comp.-Aided Design 5 (1986), 379-395. |
| . |
