Accession Number : ADA113400

Title :   Well Structured Parallel Programs are not Easier to Schedule,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Mayr,Ernst W

PDF Url : ADA113400

Report Date : Sep 1981

Pagination or Media Count : 18

Abstract : The scheduling problem for unit time task systems with arbitrary precedence constraints 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. (Author)

Descriptors :   *Parallel processing, *Scheduling, Computer program verification, Computer architecture, Hierarchies, Multiprocessors, Optimization, Algorithms, Polynomials, Combinatorial analysis, Nonlinear programming

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE