TR01-090 Authors: Andreas Jakoby, Maciej Liskiewicz, RĂ¼diger Reischuk

Publication: 29th November 2001 09:07

Downloads: 913

Keywords:

In parallel and distributed computing scheduling low level tasks

on the available hardware is a fundamental problem.

Traditionally, one has assumed that the set of tasks to be executed

is known beforehand.

Then the scheduling constraints are given by a precedence graph.

Nodes represent the elementary tasks and edges the dependencies among

tasks. This static approach is not appropriate in situations

where the set of tasks is not known exactly in advance,

for example, when different options how to continue a program may

be granted.

In this paper a new model for parallel and distributed programs,

the dynamic process graph, will be introduced, which

represents all possible executions of a program in a compact way.

The size of this representation is small -- in many cases

only logarithmically with respect to the size of any execution.

An important feature of our model is that

the encoded executions are directed acyclic graphs

having a "regular" structure that is typical of parallel programs.

Dynamic process graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

With respect to such a compact representation we investigate the

complexity of different aspects of the scheduling problem:

the question whether a legal schedule exists at all and how to find

an optimal schedule. Our analysis takes into account communication

delays between processors exchanging data.

Precise characterization of the computational complexity of various

variants of this compact scheduling problem will be given

in this paper. The results range from easy, that is NL-complete,

to very hard, namely NEXPTIME-complete.