Zusammenfassung zur Dissertation

Compilezeit-Scheduling in Multiprozessorsystemen

Dipl.-Inf. Frank Drews

5. Juli 2002

Das Problem der Verteilung der Tasks einer parallelen Applikation auf die Prozessoren eines Multiprozessorsystems zur Minimierung der Gesamtausführungszeit stellt eines der Grundprobleme der Parallelverarbeitung dar.  Im so genannten  Compilezeit-Scheduling wird vorausgesetzt, dass die wesentlichen Informationen über die auszuführenden Tasks  vor der eigentlichen Programmausführung – also zur Compilezeit – bekannt sind. Es existieren eine Reihe von Optimierungsmodellen, die sich im Wesentlichen dahingehend unterscheiden, wie das zugrundeliegende Multiprozessorsystem modelliert und die Verarbeitung der Tasks beschrieben wird. Die existierenden Modelle erfassen dabei ausschließlich die echt-parallele Verarbeitung von Tasks auf unterschiedlichen Prozessoren.

In praktisch allen modernen Betriebssystemen für Multiprozessorsysteme existiert jedoch die Betriebsart des Multitasking. Hiermit ist es neben der echt-parallelen Verarbeitung von Tasks auch möglich, Tasks quasi-parallel auf einem Prozessor auszuführen. Dies kann – insbesondere bei ein-/ausgabeintensiveren Anwendungen – durch eine bessere Auslastung der Prozessoren zu einer deutlichen Reduzierung der Gesamtausführungszeiten führen. Moderne Prozessoren tragen darüber hinaus hardwareseitig dazu bei, den durch Kontextwechsel verursachten Overhead zu reduzieren und das Multitasking zu optimieren.

Alle existierenden Modelle des Compilezeit-Scheduling basieren auf einem von zwei Grundparadigmen: Der unterbrechbaren und der nicht-unterbrechbaren Task-Ausführung. In dieser Arbeit wird gezeigt, dass beide Grundparadigmen ungeeignet sind, die Verarbeitung von Tasks im Multitasking-Betrieb zu beschreiben.

Der Grundansatz dieser Arbeit ist deshalb die Einführung eines neuen Scheduling-Modells, welches als MT-Scheduling-Modell bezeichnet wird. Dazu wird zunächst die Verarbeitung von Tasks auf Betriebssystemebene mathematisch durch ein Warteschlangenmodell formalisiert und gezeigt, dass praktisch alle gängigen Betriebssystem-Scheduling-Strategien auf diese Weise erfasst werden können. Es wird dann eine Integration der Task-Verarbeitung durch das Betriebssystem in das eigentliche Compilezeit-Scheduling-Modell vorgenommen.

Das so entstehenden Modell wird zunächst als Grundmodell formuliert. Hierbei wird vereinfachend davon ausgegangen, dass durch das Multitasking kein zusätzlicher Overhead entsteht und dass die Tasks keine – oder nur wenige – Ein-/Ausgabeoperationen ausführen. Zu diesem Modell werden gründliche theoretische Untersuchungen durchgeführt. Eine Komplexitätsbetrachtung zeigt, dass das entstehende Problem i. Allg. NP-vollständig ist. Daneben werden Schranken für optimale Schedules hergeleitet und ein  analytischer Vergleich mit existierenden Scheduling-Modellen angestellt. Es wird ferner eine Repräsentation von Schedules eingeführt, die bei Anwendung lokaler Suchverfahren eine systematische Suche im zulässigen Lösungsraum ermöglicht. Unter Zugrundelegung dieser Repräsentation wird ein auf dem lokalen Suchverfahren Simulated Annealing basierender heuristischer Lösungsansatz präsentiert. Die Optimierungsergebnisse zeigen, dass sich im MT-Scheduling-Modell die Gesamtausführungszeit im Vergleich zu existierenden Ansätzen  bereits signifikant reduzieren lässt. 

Um die praktische Anwendbarkeit des Modell zu zeigen, wird schließlich eine Validierung des MT-Scheduling-Modells  vorgenommen. Hierzu werden Schedules praktisch implementiert, wobei als Testumgebung ein symmetrisches Multiprozessorsystem unter dem Betriebssystem Linux verwendet wird. Es zeigt sich, dass die Abweichungen zwischen den vom Modell prognostizierten Zeiten und den gemessenen realen Laufzeiten für überwiegend rechenintensive Schedules praktisch im Bereich der Messungenauigkeit liegen. Allerdings nehmen die Abweichungen mit steigendem Ein-/Ausgabegrad zu. Das Grundmodell erweist sich  in  diesem Fall als nicht geeignet.

Um auch ein-/ausgabeintensive Anwendungen durch das Modell beschreiben zu können, wird eine Erweiterung des Modells um Ressourcen vorgenommen, wobei auf einen neueren Ansatz der Ressourcen-Modellierung aus der Literatur zurückgegriffen wird. Hierdurch ist es möglich, eine funktionale Abhängigkeit der Bearbeitungszeiten der Tasks von der Inanspruchnahme der Ressourcen zu formulieren. Eine erneute Validierung des Modells unter Berücksichtigung dieser Modellerweiterungen zeigt, dass die im Grundmodell auftretenden Abweichungen zwischen Prognose und Laufzeitmessungen signifikant reduziert werden können, so dass das erweiterte Modell auch für ein-/ausgabeintensive Anwendungen geeignet ist. Darüber hinaus zeigt sich bei Anwendung des Simulated Annealing-Algorithmus im erweiterten Modell, dass sich die Gesamtausführungszeit im Vergleich zum Grundmodell  noch deutlich stärker reduzieren lässt.