Multiprozessor Task Scheduling - Entwicklung und Vergleich von Algorithmen zur optimalen Auslastung eines Parallelrechners

Diese Arbeit befaßt sich mit der Berechnung eines möglichst optimalen Schedules für eine gegebene Anzahl an formbaren Modulen, wobei jedes Modul von einer beliebigen Anzahl an Prozessoren ausgeführt werden kann. Die Laufzeit eines Moduls hängt dabei von der zur Ausführung des Moduls verwendeten Anzahl an Prozessoren ab. Die Laufzeiten aller Module sind vor dem Start des Schedulingalgorithmus vollständig bekannt. Als weitere Eingabe nimmt ein Großteil der in dieser Arbeit vorgestellten Schedulingalgorithmen einen gerichteten azyklischen Graph entgegen. Dieser repräsentiert die Abhängigkeiten zwischen den einzelnen Modulen. Gehört der gegebene Graph zur Klasse der serien - parallelen Graphen, so wird diese zusätzliche Strukturinformation von einem Algorithmus zur Erstellung des Schedules ausgenutzt. Als Ergebnis liefern alle Algorithmen einen Schedule, welcher eine möglichst geringe Gesamtlaufzeit zur Ausführung aller Module auf einer gegebenen Anzahl an Prozessoren benötigt. Zum Erreichen einer minimalen Gesamtlaufzeit versuchen alle Algorithmen die Parallelität zwischen verschiedenen Modulen (Taskparallelität) und die Parallelität innerhalb eines Moduls (Datenparallelität) optimal auszunutzen. Im Gegensatz zu vielen anderen Arbeiten zu diesem oder einem verwandten Thema muß bei den meisten der hier vorgestellten Algorithmen der Aufwand zur Ausführung eines Moduls bei der Hinzunahme eines Prozessors nicht zwangsweise steigen. Dadurch sind die in dieser Arbeit angegebenen Schedulingalgorithmen unabhängig von den Werten der Eingabedaten nutzbar. Bei der Entwicklung der Algorithmen wurde viel Wert auf ihre praktische Verwendbarkeit gelegt. Dies äußert sich insbesondere in einer geringen Laufzeit der Algorithmen zur Berechnung des Schedules, sowohl bei einer sehr großen Anzahl an gegebenen Modulen, als auch bei sehr vielen zur Verfügung stehenden Prozessoren. Die Laufzeit der meisten in dieser Arbeit vorgestellten Algorithmen wird durch die Sortierung der Module bezüglich ihrer Modullaufzeit dominiert. Es werden aber auch Algorithmen angegeben, deren Laufzeit in der Größenordnung der Mächtigkeit der Eingabedaten liegt. Die in verwandten Arbeiten vorgestellten Schedulingalgorithmen haben sehr häufig eine wesentlich höhere Laufzeit, so daß diese nur bedingt in der Praxis einsetzbar sind. Selbstverständlich soll trotz der geringen Laufzeiten der Algorithmen ein sehr guter Schedule berechnet werden. Falls keine Abhängigkeiten zwischen den Modulen vorliegen, so wird ein Schedule erreicht, welcher im schlechtesten Fall die dreifache Gesamtlaufzeit gegenüber der Gesamtlaufzeit des optimalen Schedules benötigt. Liegen hingegen Modulabhängigkeiten vor, so richtet sich die garantierte Ergebnisgüte bei allen vorgestellten Schedulingalgorithmen nach den Eigenschaften der Eingabedaten. Die in der Arbeit angegebenen Schedulingalgorithmen lassen sich nach ihrer Funktionsweise grob in drei Gruppen einteilen: Die erste Art partitioniert alle Module in mehrere Modulmengen, so daß zwischen den in einer Modulmenge enthaltenen Modulen keine Abhängigkeiten mehr bestehen. Für jede dieser Modulmengen wird dann ein Schedule errechnet. Diese Teilschedules werden am Ende zu einem Gesamtschedule zusammengefügt. Die zweite Art versucht, durch die gezielte Parallelisierung von Modulen, die auf dem kritischen Pfad liegen, einen möglichst guten Schedule zu berechnen. Die dritte Art reduziert schrittweise die Modulanzahl. Dies geschieht durch die Zusammenlegung zweier oder mehrerer in bestimmten Abhängigkeiten stehender Module. Diese Art des Schedulings ist im Gegensatz zu den erstgenannten beiden Arten noch in keiner anderen bekannten Arbeit untersucht wurden. Alle vorgestellten Schedulingalgorithmen wurden in C implementiert und anhand von zufällig erstellten Eingabedaten umfangreich getestet. Dabei lag die benötigte Gesamtlaufzeit des erzielen Schedule fast immer unter dem der grob nach unten abgeschätzten Gesamtlaufzeit des optimalen Schedules. In anderen Arbeiten wurden Schedulingalgorithmen mit pseudopolynomieller Laufzeit entwickelt, welche für den ermittelten Schedule gegenüber dem optimalen Schedule eine maximal um den Faktor 4,7 höhere Gesamtlaufzeit garantieren. Die praktisch ermittelten Ergebnisse der in dieser Arbeit vorgestellten Algorithmen liegen also in nahezu allen Fällen in dem von laufzeitintensiven Algorithmen garantierten Bereich, was wiederum für den Einsatz der schnellen Algorithmen in der Praxis spricht. Weiterhin wurden die Schedulingalgorithmen an Beispielen, denen die LR - Zerlegung nach Gauß, die Matrixmultiplikation bzw. die Fast Fourier Transformation zugrunde liegt, getestet. Anhand dieser Beispiele wurden die Schedulingergebnisse der vorgestellten Algorithmen direkt miteinander verglichen. Zusätzlich wird in dieser Arbeit für sehr viele Schedulingalgorithmen auch eine Version für nichtformbare Module vorgestellt. Dadurch können auch Module verarbeitet werden, die aufgrund ihrer internen Implementierung eine bestimmte Anzahl an Prozessoren voraussetzen.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bayreuth

Year

2014

Author dc:creator

• Baumgarten, Kai

Contributors dc:contributor

• Rauber, Thomas

Repository record source_url

https://epub.uni-bayreuth.de/id/eprint/44/

OAI identifier oai:identifier

oai:epub.uni-bayreuth.de:44