Fakultät für Mathematik

Lehrstuhl Mathematik & Informatik

Approximative Lösungen des Mehrprozessor-Scheduling-Problems

Abstract.  Der Ursprung des Scheduling-Problems für mehrere Prozessoren liegt in der Organisation des Arbeitsablaufes großer Unternehmen. Hierbei wird eine komplexe Gesamtaufgabe in Teilaufgaben zerlegt und ein Zeitplan aufgestellt, der die Teilaufgaben den vorhandenen Betriebsmitteln zuordnet. Optimierungsziel ist es, die Gesamtausführungsdauer zu minimieren. Zu diesem Zweck muß die wechselseitige Unabhängigkeit einzelner Teilaufgaben im Sinne paralleler Verarbeitung ausgenutzt werden.
Durch den technischen Fortschritt ist es möglich geworden, parallele Computerarchitekturen zu entwerfen und wirtschaftlich aufzubauen. Zum einen geschieht dies in Gestalt von Mehrprozessorsystemen. Zum anderen werden auch die parallelen Verarbeitungsmöglichkeiten einzelner Prozesoren erhöht, indem ihre Mikroarchitektur mit voneinander unabhängigen Ressourcen ausgestattet wird. Es ist daher nicht verwunderlich, daß dem Scheduling-Problem für mehrere Prozessoren in den letzten zwei Jahrzehnten beträchtliche Aufmerksamkeit gewidmet wurde, sowohl in der theoretischen wie in der praktischen Informatik.
Es zeigte sich sehr bald, daß es zur Klasse der sogenannten NP-vollständigen Probleme gehört, für deren optimale Lösung nur Verfahren mit exponentiellem Zeitaufwand bekannt sind. Da die Aufstellung eines Plans nicht mehr Zeit erfordern sollte, als dieser dann einspart, wurde der Anspruch auf eine optimale Lösung des allgemeinen Problems fallengelassen. Stattdessen formulierte man vereinfachte Versionen und entwarf Heuristiken zu ihrer Lösung.
Der vorliegende Bericht ist folgendermaßen aufgebaut: In Abschnitt 1 wird eine vereinfachte Version des Mehrprozessor-Scheduling-Problems vorgestellt, die einer formalen Analyse zugänglich ist. In Abschnitt 2 definieren wir die wichtige Klasse der Listenpläne und ein formales Gütekriterium für Heuristiken. Abschnitt 3 gibt eine Übersicht über die bezüglich des worst-case Verhaltens besten derzeit bekannten Polynomialzeitheuristiken. Eine besondere Rolle spielt, ihrer einfachen Implementierbarkeit wegen, die CP-Heuristik (CP Critical Path). Sie wird in Abschnitt 4 definiert. Die CP-Heuristik liefert, trotz ihrer Einfachheit, im worst-case zufriedenstellende Ergebnisse und für spezielle Datenabhängigkeitsstrukturen sogar optimales Verhalten. Einige anwendungsspezifische Datenabhängigkeitsstrukturen werden in Abschnitt 5 vorgestellt. Die wichtigsten Resultate über die CP-Heuristik sind in Abschnitt 6 aufgelistet. In Abschnitt 7 werden formale Analysetechniken präsentiert und einige der Resultate aus Abschnitt 6 bewiesen. Abschnitt 8 enthält bibliographische Anmerkungen.