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

Publication: 14th May 2001 22:57

Downloads: 3538

Keywords:

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program in a very compact way.

The size of this representation can be as small as logarithmic

with respect to the size of any execution of the program.

In a preceding paper we have analysed the expressive power

of the general model and various variants of it.

We have considered the scheduling problem for DPGs given enough parallelism

taking into account communication delays between processors when exchanging data.

Given a DPG the question arises whether it can be executed

(that means whether the corresponding parallel program has been specified

correctly), and what is its minimum schedule length.

In this paper we study a subclass of DPGs called PAR-output DPGs,

which are appropriate in many situations, and investigate their expressive power.

We have shown that the problem to determine the minimum schedule length is

still intractable for this subclass, namely this problem is NEXPTIME-complete as is the general case.

Here we will investigate structural properties of the executions of such graphs.

A natural graph-theoretic conjecture that executions must always split

into components that are isomorphic to subgraphs turns out to be wrong.

We are able to prove a weaker property.

This implies a quadratic upper bound on the schedule length that may be

necessary in the worst case, in contrast to the general case, where the

optimal schedule length may be exponential with respect to the size of the representing DPG.

Making this bound constructive, we obtain an approximation to an NEXPTIME-complete problem.

Computing such a schedule and then executing the program can be done

on a parallel machine in polynomial time in a hihgly distributive fashion.