Benutzer- und datengesteuertes Schleifen-Scheduling auf Parallelrechnern mit Distributed Shared Memory

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