Thesis (Server


Doctoral dissertation | @PhdThesis{BastPhD2000, ... | Doktorarbeit

Bast, Hannah

Provably Optimal Scheduling of Similar Tasks

Universität des Saarlandes, February, 2000

We consider the problem of processing a given number of tasks on
a given number of processors as quickly as possible when the
processing times of the tasks are variable and not known in advance.
The tasks are assigned to the processors in chunks consisting
of several tasks at a time, and the difficulty lies in finding
the optimal tradeoff between the processors' load balance, which
is favoured by having small chunks, and the total scheduling overhead,
which will be the lower the fewer chunks there are.
Our studies are motivated by a practical problem from
high-performance computing, namely parallel-loop scheduling,
for which a large variety of heuristics have been proposed
in the past, but hardly any rigorous analysis has been presented to date.
Our work is based on a generic approach that covers
the whole spectrum of processing time irregularity.
This approach does not make any assumptions about task processing times,
but instead works with estimated ranges for processing times,
one for each chunk size, and a measure for the overall deviation of
the actual processing times from these estimates.
Our analysis provides a general upper bound applicable
for every conceivable setting of these parameters, together with lower
bounds showing that no algorithm can do significantly better than
the ones we propose.
Our general result implies optimal bounds for a
whole variety of specific settings, including the modelling of
task processing times as independent, identically
distributed random variables, which underlies most of the
previously existing heuristics.
Our results confirm the practicability of certain
well-established techniques for parallel-loop scheduling,
while, on the other hand, revealing major flaws in other approaches.

Scheduling, High-Performance Parallel Computing, Parallel Loops
Prof. Dr. Kurt Mehlhorn
Prof. Dr. Susanne Albers
Prof. Dr. Birgit Pfitzmann
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:
AUTHOR = {Bast, Hannah},
TITLE = {Provably Optimal Scheduling of Similar Tasks},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2000},
TYPE = {Doctoral dissertation}
MONTH = {February},

Entry last modified by Hannah Bast, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Hannah Bast
03/21/2000 12:07:03 PM

Hannah Bast

Edit Date
21/03/2000 12:07:09