Verlag des Forschungszentrums Jülich
JUEL-3552
Berrendorf, Hans Rudolf
Benutzer- und datengesteuertes Schleifen-Scheduling auf Parallelrechnern mit Distributed Shared Memory
181 S., 1998
Parallelrechner mit Distributed Shared Memory haben einen physikalisch
verteilten Speicher und globalen kohärenten Adreßraum für Programme. Zur
effizienten Nutzung dieser Rechner auch bei großen Prozessorzahlen muß bei
der Programmierung zwei Aspekten besonderes Interesse gelten: der Lastbalance
zwischen den Prozessoren und der Minimierung der Interprozessorkommunikation.
Die vorliegende Arbeit stellt zwei neue Ansätze dazu vor, die beide auf dem
Grundprinzip basieren, daß parallel ausführbare Aufgaben (Tasks) gezielt auf
die Prozessoren verteilt werden (Scheduling).
Der erste Ansatz, das benutzergesteuerte Scheduling, ist für solche Programme
entwickelt worden, in denen die Ausführungszeiten von Tasks durch den
Programmierer abschätzbar und das Speicherzugriffsmuster von geringer
Komplexität ist. Templates stellen einen abstrakten Iterationsraum dar, in
dem eine Verteilung von Tasks auf Prozessoren gespeichert werden kann. Diese
Arbeit stellt spezielle Verteilungen für Templates vor, mit deren Hilfe der
Benutzer in der Lage ist, parallele Tasks so auf die Prozessoren zu verteilen,
daß die Kommunikation im System minimiert wird.
Der zweite neue Ansatz, das datengesteuerte Scheduling, eignet sich für
Programme mit sequentiell iterierten Programmteilen, in denen die Task-Zeiten a
priori nicht bestimmbar oder die Speicherzugriffsmuster komplex sind. Ein
Compiler modifiziert den entsprechenden Programmteil so, daß zur Laufzeit des
Programmes statistische Daten über das Zugriffsverhalten und die Laufzeit von
Tasks gesammelt werden. Aus diesen Daten wird ein spezieller gewichteter Graph
konstruiert, dessen Knoten Tasks und dessen Kanten Kommunikationsvorgänge
repräsentieren. Über Verfahren der Graphpartitionierung wird der Graph so in
Teilgraphen zerlegt, daß die Summe der Knotengewichte der Teilgraphen gleich
und der Kantenschnitt zwischen den Teilgraphen minimal wird. Die berechnete
Aufteilung der Knoten des Graphen auf die Teilgraphen repräsentiert eine
Verteilung der Tasks auf die Prozessoren. Dieser Schedule wird in einem
Template abgespeichert und bei weiteren Ausführungen dieses Programmteils
effizient dazu genutzt, die Tasks auf die Prozessoren zu verteilen.
Sowohl für das benutzergesteuerte als auch das datengesteuerte Scheduling
werden die Effizienzvorteile gegenüber vergleichbaren Verfahren auf zwei
verschiedenen Parallelrechnern mit bis zu 128 Prozessoren gezeigt.
Neuerscheinungen
Schriften des Forschungszentrums Jülich
Ihre Ansprechperson
Heike Lexis
+49 2461 61-5367
zb-publikation@fz-juelich.de