Global task data dependencies in the partitioned global address space

Abstract

High-Performance Computing (HPC) has become an important part of scientific discovery in many fields and takes an important role in many engineering processes, harnessing the power of large amounts of computational resources to gain insights into otherwise hidden technological and natural phenomena. The dominating programming model driving today’s parallel applications is a two-level approach consisting of message-based communication between processes using MPI and static loop-level thread-parallel execution using OpenMP constructs. However, two programming models have tried to challenge this status quo. First, the Partitioned Global Address Space (PGAS) model is an attempt to elevate shared memory programming to the level of distributed systems and to directly expose modern network hardware features to the application developer. Second, task-based programming aims at providing abstractions that help discover a greater amount of concurrency in parallel applications, which in turn can be used to better exploit the computational resources at hand. Both models are an attempt to break up the strict synchronization imposed by the traditional models: the PGAS model decouples synchronization and communication while task-based programming models minimize the required synchronization to a set of constraints on the order of the execution of tasks. This work proposes a novel way of orchestrating the execution of tasks at a global scale by using distributed task graph discovery and data dependencies in the global memory space. The results demonstrate that applications exhibiting concurrency beyond single loop parallelism may use this new model to significantly improve performance and scalability by combining the benefits of task-based programming and one-sided communication in the PGAS model.

Der Bereich des Hochleistungsrechnens (HPC) hat sich zu einem wichtigen Bestandteil heutiger Forschungs- und Entwicklungsarbeit entwickelt. Dabei werden hohe Rechenkapazitäten genutzt um Einsichten in ansonsten weitgehend unsichtbare natürliche und technische Phenomäne zu erhalten. Das dominante Programmiermodell für parallel Anwendungen ist dabei eine Kombination von Parallelität auf zwei Ebenen: die nachrichtenbasierte inter-prozess Kommunikation mit Hilfe von MPI sowie schleifenbasierte Parallelisierung auf der Basis von Threads mit Hilfe von OpenMP. Zwei neue Programmiermodelle sind angetreten um diesen Status Quo zu ändern. Zum Einen hat der Partitioned Global Address Space (PGAS, partitionierter globaler Addressraum) zum Ziel, die Programmierung auf gemeinsamem Speicher in den Bereich der Systeme mit verteiltem Speicher abzubilden und dabei die Fähigkeiten moderner Netzwerke direkt den Entwicklern paralleler Anwendungen zur Verfügung zu stellen. Zum Anderen zielt die Task-basierte Programmierung darauf ab, einen größeren Grad an verfügbarer Parallelität in Anwendungen zu nutzen um die verfügbaren Rechenressourcen besser auszulasten. Beide Modelle sind ein Versuch die strikte Synchronität der traditionellen Programmiermodelle aufzuheben: im Partitioned Global Address Space (PGAS)-Modell sind Kommunikation und Synchronisierung voneinander getrennt, während bei Task-basierter Programmierung im Idealfall nur genau soviel Synchronisierung stattfindet wie für die korrekte Ausführung einer Anwendung nötig ist. Die vorliegende Arbeit untersucht daher die Verbindung dieser beiden Programmiermodelle in dem Versuch deren Vorteile in einem Modell zu kombinieren, in dem auf globaler Ebene die Ausführungsreihenfolge von Tasks anhand von Datenabhängigkeiten im globalen Addressraum organisiert wird. Die in dieser Arbeit präsentierten Ergebnisse zeigen dabei, dass für Anwendungen mit hinreichend verfügbarer Parallelität die Kombination aus Task-basierter Programmierung und der Nutzung von PGAS zur Kommunikation eine signifikante Effizienzsteigerung möglich ist. Das entwickelte Programmiermodell macht es Entwicklern dabei einfach existierende Anwendungen zu portieren.