Front page (enlarge, 180kB)
This issue is devoted to problems of task scheduling in parallel or distributed systems.
The idea of this special issue was raised during the seminar on
"Scheduling in Parallel and Distributed Systems",
held in Marseille from 10 June to 14 June 1996.
Participants presented results from the area of task scheduling under consideration of communication delays.
Altogether we received eleven high quality submissions for publication,
and we were able to accept six of them for the special issue.
The first three papers consider scheduling of tasks subject to explicit communication delays.
The fourth paper deals with multiprocessor tasks where the communication delays are taken into account
implicitly, and the last two papers are based on models that take the processor interconnection
topology into account. The paper of J. Verriet discusses a scheduling problem where tasks
are subject to communication delays. Unit processing times and interval ordered precedence constraints
are assumed. The topology of the processor interconnection network is of no concern because
the communication delays are uniformly assumed to be 1. An O(n2) time algorithm
for constructing minimum-tardiness schedules is presented.
The paper of R.H. Möhring and M.W. Schäffter considers the problem of scheduling tasks
with arbitrary processing times on an unbounded number of processors.
Tasks execution is restricted by series-parallel precedence constraints and unit communication delays.
For the objectives of minimizing makespan and minimizing weighted average completion time,
polynomial time optimization algorithms are presented. If the communication delays are 0 or 1,
the problem is shown to be NP-hard.
The paper of A. Munier concerns general communication delays for tree dependent tasks
and arbitrary processing times and communication delays. Under the assumption of an unlimited number
of processors, an approximation algorithm is presented whose performance depends on the maximum ratio
between communication delays and task processing times.
The paper of A. Amoura et al. considers the problem of scheduling multiprocessor tasks
on three dedicated processors. A new algorithm is presented and its performances are compared
with those of existing algorithms of the literature.
The paper of C. Hoeres and V.E.F. Rebello discusses the origins of delays when dependent tasks on
distinct processors need to communicate. It is pointed out that latency, due to the data transmission,
is often negligible compared to other communication-related activities.
A model in which this CPU penalty is the dominant communication parameter is considered in detail.
In the last paper, presented by J. Blazewicz et al., a model of divisible tasks is assumed where tasks
are computations that can be divided into independent parts with arbitrary granularity.
Based on a simple model of communication delay and computation time,
various computer architectures and communication methods are analyzed.
These papers are important and innovative contributions in the area of task scheduling
in distributed or parallel systems. Reviewing the contributions and preparing and editing
this issue was only possible with the help from many sides.
First, we would like to thank the authors who submitted papers,
then our referees for their thorough and responsible work.
Special thanks are due to Denis Trystram who was the seminar organizer;
without his strong support the appearance of this issue would not have been possible.
Evripidis Bampis, Jacek B³a¿ewicz and Klaus Ecker
Aussois, June 1998
Contents