Please use this identifier to cite or link to this item: doi:10.22028/D291-25676
Title: Provably optimal scheduling of similar tasks
Other Titles: Beweisbares optimales Scheduling ähnlicher Prozesse
Author(s): Bast, Hannah
Language: English
Year of Publication: 2000
SWD key words: Parallelrechner ; Task ; Programmschleife ; Scheduling
DDC notations: 004 Computer science, internet
Publikation type: Dissertation
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.
Wir betrachten das Problem, eine gegebene Anzahl von Aufgaben (engl.tasks)möglichst schnell auf einer gegebenen Anzahl von Prozessoren zu bearbeiten, wenn die Bearbeitungszeiten der Aufgaben nicht im Vorhinein bekannt sind.
Link to this record: urn:nbn:de:bsz:291-scidok-1484
Advisor: Kurt Mehlhorn
Date of oral examination: 4-Feb-2000
Date of registration: 5-Feb-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
HannahBast_ProfDrKurtMehlhorn.pdf1,3 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.