Evaluation der Leistungsfähigkeit von gemischt-parallelen Programmen in homogenen und heterogenen Umgebungen unter Berücksichtigung effizienter Schedulingstrategien

Titelangaben

Hunold, Sascha:
Evaluation der Leistungsfähigkeit von gemischt-parallelen Programmen in homogenen und heterogenen Umgebungen unter Berücksichtigung effizienter Schedulingstrategien.
Bayreuth , 2008
( Dissertation, 2009 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

	Format: PDF Name: hunold2009.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
	Download (2MB)

Abstract

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.

Abstract in weiterer Sprache

The formulation of applications in a mixed-parallel way, in which a program is composed of concurrently executable multiprocessor tasks (M-tasks), can lead to a higher degree of parallelism than common data-parallel implementations. It is challenging to obtain efficiently performing mixed-parallel applications. Well-suited programming environments and well-performing scheduling algorithms should be available to exploit the full potential of this class of algorithms. In the present work, several mixed-parallel realizations of matrix multiplication algorithms are developed to study the performance potential of mixed-parallel applications. Two new mixed-parallel realizations of a matrix multiplication for square dense matrices are introduced. The first algorithm is a mixed-parallel version of a panel-panel algorithm called tpMM. Secondly, a realization of Strassen´s algorithm is presented using a recursive decomposition into a hierarchy of M-tasks. Since Strassen´s algorithm is formulated hierarchically it is possible to use different building blocks to solve the remaining sub-problems at the cut-off level of Strassen´s algorithm. This leads to a hierarchy of building blocks which can be combined to obtain different poly-algorithms, all starting with a mixed-parallel decomposition using Strassen´s algorithm. The performance of these mixed-parallel combinations is compared with commonly used data-parallel implementations, e.g. PDGEMM of ScaLAPACK, on homogeneous distributed memory systems. The experimental results show that a mixed-parallel realization of Strassen´s algorithm can lead to a better performance than data-parallel matrix multiplication algorithms. The resulting performance mainly depends on the number of processors and the size of the input matrices. Mixed-parallel applications can be modeled as directed acyclic graphs (DAGs), in which a node represents an M-task and the edges denote data dependencies between M-tasks. Such a representation is well-suited to execute mixed-parallel algorithms across different clusters. Since the distributed execution of M-tasks on the grid requires a specific software infrastructure, TGrid has been developed as part of the present work. TGrid is a grid middleware and a runtime system to develop and to execute mixed-parallel applications. The TGrid middleware targets multi-clusters, which are clusters of clusters. In contrast to other grid middleware systems, TGrid allows the co-allocation of resources of different clusters to M-tasks belonging to the same application. It also provides a redistribution component that automatically performs data redistributions between cooperating M-tasks and that does not require to write data redistribution code by hand. The execution of mixed-parallel applications also raises the question of how to schedule executable M-tasks on the platform. Hence, the present work introduces two novel scheduling algorithms, RePA and DMHEFT. They can be used to schedule dynamically generated DAGs of M-tasks in a multi-cluster environment. The scheduling performance in terms of makespan of both algorithms is compared to well-performing compile time algorithms such as MHEFT. Since TGrid can also be used to execute static DAGs, this work also introduces a novel compile time scheduling algorithm (RATS) for homogeneous clusters. The RATS algorithm uses two steps to produce the compile time schedule. First, an allocation phase assigns a number of processors to each M-task. In a second phase, the algorithm maps the allocations onto the platform using a list-scheduling approach. The RATS algorithm attempts to reduce the redistribution costs of cooperating M-tasks by reconsidering the allocation size in the mapping phase and by changing this size where applicable. Simulations have shown that the RATS algorithm significantly improves the performance of two-step approaches such as HCPA on homogeneous clusters. In summary, the present work shows how mixed-parallel applications can be developed and efficiently executed. These mixed-parallel algorithms can lead to faster execution times than data-parallel implementations on homogeneous parallel systems. The present work also demonstrates that, in contrast to other programming models, mixed-parallel applications can be efficiently executed in grid environments such as multi-clusters.