Automatic data flow optimizations for parallel patterns on hierarchical memory architectures

Wassermann, Christian; Schmitz, Adrian; Lübbecke, Marco; Müller, Matthias S.; Miller, Julian

doi:10.18154/RWTH-2023-06006

Automatic data flow optimizations for parallel patterns on hierarchical memory architectures = Automatische Datenflussoptimierung für parallele Muster auf Architekturen mit hierarchischem Speicher

Wassermann, Christian^RWTH*

2023

VerantwortlichkeitsangabeChristian Wassermann

ImpressumAachen : RWTH Aachen University 2023

Umfang1 Online-Ressource : Illustrationen, Diagramme

Masterarbeit, RWTH Aachen University, 2023

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Müller, Matthias S. (Thesis advisor)^RWTH* ; Lübbecke, Marco (Thesis advisor)^RWTH* ; Schmitz, Adrian (Consultant)^RWTH* ; Miller, Julian (Consultant)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2023-03-15

Online
DOI: 10.18154/RWTH-2023-06006
URL: https://publications.rwth-aachen.de/record/960031/files/960031.pdf

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Für viele Anwendungsfelder ist die Nutzung hochgradig paralleler Hochleistungsrechner ein integraler Teil der Forschungsaktivitäten geworden. Mit der steigenden Nachfrage nach mehr Rechenleistung hat heterogene Hardware Einzug in heutige Hochleistungsrechnersysteme gefunden, um die Ausführung spezialisierter Applikationen zu unterstützen. Dazu gehören nicht nur Beschleuniger wie General-Purpose Graphics Processing Units (GPGPUs) sondern auch neue Speichertechnologien wie High-Bandwidth Memory (HBM). Die damit einhergehende zunehmende Komplexität stellt Fachwissenschaftler und Experten für Hochleistungsrechnen gleichermaßen vor die Herausforderung, die verfügbare Hardware bestmöglich auszunutzen. Das Parallel Pattern Language (PPL)-Projekt wurde von der Gruppe für Hochleistungsrechnen der RWTH Aachen ins Leben gerufen, um diese Herausforderungen zu adressieren. Hierbei werden parallele Applikationen als eine hierarchische Kombination paralleler Muster modelliert. Teil des Projekts ist eine prototypische Implementierung mit einer domänenspezifischen Sprache für produktive parallel Programmierung, die gleichzeitig portable Performance bietet. Diese Arbeit baut auf den im Rahmen des PPL-Projekts eingeführten Ideen auf und setzt den Schwerpunkt der Ausarbeitung auf dessen Optimierungskomponente. Diese berechnet den Ausführungsplan für ein paralleles Programm und eine gegebene Hardwarezusammensetzung zur Kompilierzeit. Zur Modellierung dieser Variante des parallelen Maschinenplanungsproblems werden drei neue Modelle mittels gemischt-ganzzahliger linearer Programmierung (MILP) aufgestellt, die insbesondere Erweiterungen zur Berücksichtigung heterogener und hierarchischer Speicherressourcen enthalten. Zur Integration in die bereits existierenden Komponenten des PPL-Projekts werden passende Konvertierungen der genutzten Daten beschrieben. Eine prototypische Implementierung wird auf einem konfigurierbaren Benchmark mit vier verschiedenen MILP-Lösern evaluiert. Die Ergebnisse zeigen einen signifikanten Laufzeitvorteil einer einzigen Modell- und Löser-Kombination. Anschließend werden Modellvarianten sowie die Einsatzmöglichkeiten von Parallelität mittels Multi-Threading bewertet. Eine detaillierte Analyse des Rechenverhaltens während des Lösungsprozesses und ein Vergleich mit dem bisher im PPL-Projekt verwendeten ebenenbasierten Schedulingansatz vervollständigen die wissenschaftlichen Beiträge dieser Arbeit.

The usage of large-scale high performance computing (HPC) resources has become the norm in a wide variety of disciplines and enables numerous advances in scientific research. As the demand for compute power growths, HPC systems have adopted an increasing amount of heterogeneity in their hardware setups to suit the needs of specialized applications. This includes not just accelerator devices like general-purpose graphics processing units (GPGPUs) but also emerging memory technologies like high-bandwidth memory (HBM). The additional complexity caused by these developments challenges domain scientists and HPC experts alike to utilize the available hardware to its fullest potential. The parallel pattern language (PPL) project was created by the HPC group of the RWTH Aachen University to address these concerns. Its theoretical representation considers parallel applications as a hierarchical combination of parallel patterns. As part of the project a prototypical implementation with a domain specific language for productive and performance portable parallel programming is provided. This thesis builds on the ideas introduced within the PPL project and focuses on its optimization component. It computes the execution schedule of the parallel program for a given hardware composition at compile time. To model this variant of a parallel machine scheduling problem, three new mixed-integer linear programming (MILP) models are formulated especially considering the necessary extensions for incorporating heterogeneous and hierarchical memory resources. Appropriate conversions are laid out to integrate with the existing foundation of the PPL project. The prototypical implementation is evaluated on a configurable benchmark with four different MILP solvers. The results highlight the runtime advantage of a single model and solver combination before assessing model variations and the benefit of shared memory parallelism. A detailed analysis of the computational behavior of the solving process and a comparison to the previously used layer-based scheduling in the PPL project complete the contributions of this thesis.

OpenAccess:
PDF
(additional files)