Dezentrale Ablaufplanung für selbstverteilende parallele Systeme

Seit den Anfängen des Computerzeitalters fordern immer komplexer werdende Applikationen immer leistungsfähigere Rechnersysteme. Eine Möglichkeit zur Leistungssteigerung besteht im Einsatz mehrerer Prozessoren, die parallel an der auszuführenden Applikation arbeiten. Zur weiteren Leistungssteigerung kann ein dynamisch rekonfigurierbares, paralleles System beitragen, das vollständig auf eine Client-Server-Struktur verzichtet und dadurch besonders gut skalierbar ist. Als Ausführungsmodell kommt dann nur eine omatische Verteilung von Tasks während der Laufzeit in Frage, damit auf Änderungen des Systems während der Laufzeit reagiert werden kann. Die Hauptmerkmale eines solchen selbstverteilenden parallelen Systems sind die Ausführung der Berechnungen nach einem grobgranularen Datenflussprinzip und ein (ggf. verteilter) gemeinsamer Speicherbereich. Bisherige Scheduling-Systeme für parallele Systeme sind entweder zentral organisiert oder teilen das Scheduling strikt in die zwei unabhängig arbeitenden Bereiche lokales und globales Scheduling auf. Bei einem zentral organisierten Scheduling entsteht prinzipbedingt eine Client-Server-Struktur, in der mit hohen Lasten des Servers bei größeren Rechner-Verbünden zu rechnen ist. Bei einer strikten Trennung in lokales und globales Scheduling hingegen wird Potenzial zur Parallelitätssteigerung verschenkt. Es fehlen also Scheduling-Verfahren, die weder zentral organisiert sind noch das globale und das lokale Scheduling strikt trennen. Zentrales Thema dieser Studie ist die Entwicklung einer solchen Ablaufplanung für selbstverteilende parallele Systeme. Diese Ablaufplanung wird zwar verteilt über alle Rechner durchgeführt, kann jedoch – aufgrund von speziellen Informationen – auch Scheduling-Entscheidungen treffen, die sonst nur zentral gesteuerten Ablaufplanungen vorbehalten sind. Dieses Scheduling-Prinzip wird als „Dezentrale Ablaufplanung“ bezeichnet. Das größte Optimierungspotenzial im Vergleich zu herkömmlichen Schedulingverfahren liegt im Verbergen von Kommunikationslatenzen hinter der Ausführung anderer Berechnungen. Hierfür werden Informationen aus dem grobgranularen Abhängigkeitsgraphen der Applikation extrahiert und während der Laufzeit ausgewertet. Anhand dieser Daten werden mehrere Berechnungsteile gemeinsam zu anderen Prozessoren verschoben, Daten bereits frühzeitig angefordert und das Cache-Kohärenz-Protokoll optimiert. Anhand der Analysen wird auch verhindert, dass die Gesamtlast des Systems zu hoch wird oder dass das parallele System unnötigerweise leer läuft. Zudem kooperieren die einzelnen Prozessoren miteinander und verteilen so selbst auf heterogenen Systemen die Last sehr effektiv. Das dezentrale Scheduling mit mehreren Beispielapplikationen evaluiert. In den Simulationen konnten Leistungsverbesserungen nachgewiesen werden, die in Einzelfällen bis zu 88% gegenüber dem zentral organisierten Scheduling und bis zu 50% gegenüber dem strikt trennenden verteilten Scheduling erreichen.