Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Bast, Hannah

MPI-INF D1 Publications
Show all entries of:this year (2019)last year (2018)two years ago (2017)Open in Notes
Action:login to update

Thesis - Doctoral dissertation | @PhdThesis | Doktorarbeit

Author(s)*:Bast, Hannah
BibTeX citekey*:BastPhD2000

Title, School
Title*:Provably Optimal Scheduling of Similar Tasks
School:Universität des Saarlandes
Type of Thesis*:Doctoral dissertation

Note, Abstract, Copyright
LaTeX Abstract: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.

Keywords:Scheduling, High-Performance Parallel Computing, Parallel Loops
HyperLinks / References / URLs:

Referees, Status, Dates
1. Referee:Prof. Dr. Kurt Mehlhorn
2. Referee:Prof. Dr. Susanne Albers
Date Kolloquium:4 February 2000
Chair Kolloquium:Prof. Dr. Birgit Pfitzmann

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance: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