COMPLEXITY OF SCHEDULING IN HIGH-LEVEL SYNTHESIS

This work examines the complexity of scheduling for high level synthes is. It has been shown that the problem of finding the minimum time sch edule for a set of chains of operations of two types using two process ors, one of each type, is NP-complete. However, for two chains only, a polynomial time algorithm can been obtained for scheduling with two p rocessors. The problem of scheduling a rooted binary tree of two opera tion types on two processors, one of each type, has been shown to be N P-complete. It has also been proved that absolute approximations for s chedule length minimization or processor minimization are NP-complete. A related resource constrained scheduling problem has also been shown to be NP-hard.