Well Structured Parallel Programs are not Easier to Schedule,

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1981
Accession Number
ADA113400

Entities

People

  • Ernst W. Mayr

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Architecture
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Language
  • Linguistics
  • Military Research
  • Notation
  • Parallel Processors
  • Polynomials
  • Programming Languages
  • Scheduling (Production)
  • United States
  • United States Government

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Forest Ecology
  • Operations Research