Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25676
Titel: Provably optimal scheduling of similar tasks
Alternativtitel: Beweisbares optimales Scheduling ähnlicher Prozesse
VerfasserIn: Bast, Hannah
Sprache: Englisch
Erscheinungsjahr: 2000
Kontrollierte Schlagwörter: Parallelrechner ; Task ; Programmschleife ; Scheduling
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-1484
hdl:20.500.11880/25732
http://dx.doi.org/10.22028/D291-25676
Erstgutachter: Kurt Mehlhorn
Tag der mündlichen Prüfung: 4-Feb-2000
Datum des Eintrags: 5-Feb-2004
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
HannahBast_ProfDrKurtMehlhorn.pdf1,3 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.