Report Number: CS-TR-81-880
Institution: Stanford University, Department of Computer Science
Title: Well structured parallel programs are not easier to schedule
Author: Mayr, Ernst W.
Date: September 1981
Abstract: The scheduling problem for unit time task systems with
arbitrary precedence constrainls is known to be NP-complete.
We show that the same is true even if the precedence
constraints are restricted to certain subclasses which make
the corresponding parallel programs more structured. Among
these classes are those derived from hierarchic cobegin-coend
programming constructs, level graph forests, and the parallel
or serial composition of an out-tree and an in-tree. In each
case, the completeness proof depends heavily on the number of
processors being part of the problem instances.