Refine
Keywords
- Verteilter Speicher (1) (remove)
-
Evaluation der Leistungsfähigkeit von gemischt-parallelen Programmen in homogenen und heterogenen Umgebungen unter Berücksichtigung effizienter Schedulingstrategien
(2008)
- Die gemischt-parallele Formulierung von Programmen, welche aus kooperierenden Multiprozessor- Tasks (M-Tasks) bestehen, erlaubt einen höheren Grad an Parallelität als gewöhnliche datenparallele Implementierungen. Um diesen höheren Parallelitätsgrad auszunutzen, bedarf es effizienter gemischt-paralleler Realisierungen von Algorithmen, einer guten Infrastruktur zur Ausführung der Programme und leistungsfähigen Scheduling-Algorithmen, die die einzelnen M-Tasks auf die bestmögliche Menge von Prozessoren abbilden. Im ersten Teil der vorliegenden Arbeit werden exemplarisch verschiedene gemischt-parallele Realisierungen der Matrixmultiplikation zweier dicht besetzter Matrizen untersucht. Dazu werden Algorithmen (z. B. die Matrixmultiplikation nach Strassen) so umstrukturiert, dass die resultierenden Verfahren aus hierarchisch organisierten, datenparallelen Multiprozessor- Tasks bestehen. Durch die abstraktere Beschreibung von Problemen mittels kooperierender Tasks lassen sich Algorithmen einfacher miteinander kombinieren. In dieser Arbeit wurden verschiedene gemischt-parallele Algorithmen zu neuen Poly-Algorithmen zusammengesetzt, wobei die gemischt-parallele Variante von Strassens Algorithmus als Ausgangsalgorithmus gewählt wurde. Die so entstandenen Poly-Algorithmen zur Matrixmultiplikation wurden in einer Vielzahl von Experimenten mit der Leistung datenparalleler Implementierungen auf homogenen parallelen und verteilten Systemen verglichen. Dabei zeigte sich, dass die gemischt-parallelen Varianten für viele Konfigurationen kürzere Laufzeiten als die datenparallelen Algorithmen erreichen. Gemischt-parallele Programme lassen sich als gerichteter azyklischer Graph (DAG) beschreiben. Diese Darstellung ist sehr gut für eine verteilte Abarbeitung der einzelnen Knoten (M-Tasks) über Clustergrenzen hinaus geeignet. Trotzdem benötigt man eine entsprechende Software-Infrastruktur, um gemischt-parallele Programme auf verschiedenen Clustern auszuführen. Aus diesem Grund wurde im Rahmen dieser Arbeit TGrid entwickelt, um gemischt-parallele Applikationen im Grid auszuführen. TGrid ist zum einen eine Middleware, die verschiedene heterogene Systeme zu einem kooperierenden System zusammenfügt. Zum anderen bietet TGrid eine Programmierschnittstelle, um gemischtparallel Programme zu formulieren und diese mit Hilfe der Middleware auszuführen. Die TGrid-Middleware ermöglicht die Co-Allokation von Ressourcen für eine einzige gemischtparallele Anwendung, d. h. ein einziges Programm kann durch mehrere Cluster parallel abgearbeitet werden. Eine weitere wichtige Eigenschaft ist die Unterstützung der automatischen Datenumverteilung zwischen M-Tasks. Der Programmierer muss dazu nur die Abbildung der Ausgangsdatenstrukturen auf die Eingangsdatenstrukturen zweier M-Tasks definieren. Die eigentliche Datenkommunikation übernimmt das TGrid-System. Für eine effiziente Ausführung gemischt-paralleler Programme in Clustern und Multiclustern (Cluster aus Clustern) ist auch die Frage zu klären, in welcher Reihenfolge die ausführbereiten Tasks abgearbeitet werden sollen. Das Ausführen von dynamisch erzeugten M-Taskgraphen in Multiclustern führt zu einer neuen Klasse von Scheduling-Problemen. Deshalb werden in der vorliegenden Arbeit zwei Algorithmen (RePA und DMHEFT) für das Scheduling von dynamisch generierten Taskgraphen entwickelt und deren Leistungsfähigkeit mit Compile-Zeit-Verfahren wie MHEFT verglichen. Da TGrid auch für die Ausführung von statisch definierten Taskgraphen genutzt werden kann, wird ein neuer zweistufiger Scheduling-Algorithmus (RATS) vorgestellt, welcher zu Compile-Zeit arbeitet. Dieser Algorithmus versucht durch gezielte Änderung der Prozessor- Allokation von Tasks, die Kosten der Datenumverteilung zu reduzieren. Nach genauer Analyse mittels Grid-Simulationen konnte festgestellt werden, dass RATS deutlich kürzere Ablaufpläne als andere zweistufige Verfahren, wie z. B. HCPA, auf homogenen Clustern produziert. Zusammenfassend zeigt die vorliegende Arbeit, wie gemischt-parallele Algorithmen entwickelt und effizient ausgeführt werden können. In homogenen parallelen Systemen ermöglichen diese gemischt-parallelen Anwendungen bessere Laufzeiten als datenparallele Implementierungen. Die Arbeit verdeutlicht auch, dass eine gemischt-parallele Formulierung von Algorithmen eine effiziente Ausführung von parallelen Verfahren in Grid-Umgebungen (Multiclustern) erlaubt, die mit anderen parallelen Programmiermodellen in diesen nicht zu erreichen ist.
