Processor optimization for flow graphs

In the synthesis of hardware, operations of a scheduled flow graph (acyclic, but with branching nodes) are assigned to processors. First we show that the problem of finding an assignment with minimum number of processors is NP-complete and that the problem of finding a maximum compatible set of operations can be solved in polynomial time. Then we show that the generalized processor optimization problem with nonuniversal processors is a generalization of the set-covering problem. At last we give an approximative algorithm for this problem with multiplicative factor O(log(|Op|)).

Authors

• Klaus Jansen

Keywords

No keywords are indexed for this paper.