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.
Keywords: independent set, chromatic number, high level synthesis
AMS Subject Classification: 68R10, 05C15