Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
independent set; chromatic number; high level synthesis
independent set; chromatic number; high level synthesis
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.
References:
[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
[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
[3] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NPCompletness. Freeman, San Francisco, 1979. MR 0519066
[4] Jansen K.: Processor optimization for flow graphs. Theor. Comput. Sci. 104 (1992), 285-298. MR 1186182 | Zbl 0754.68062
[5] Jansen K.: The allocation problem in hardware design. Disc. Appl. Math. 43 (1993), 37-46. MR 1218041 | Zbl 0776.68094
[6] Lawler E.L.: Combinatorial Optimization: Networks and Matroids. Rinehard and Winston, New York, 1976. MR 0439106 | Zbl 1058.90057
[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. MR 0723569 | Zbl 0521.05062
[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.
Search
Partner of
