Modular techniques and interfaces for data race detection in multi-paradigm parallel programming

Protze, Joachim; Müller, Matthias S.; Schulz, Martin; Träff, Jesper L.

doi:40556

Modular techniques and interfaces for data race detection in multi-paradigm parallel programming = Modulare Techniken und Schnittstellen zur Erkennung von Speicherzugriffsanomalien in der Parallelprogrammierung mit mehreren Paradigmen

Protze, Joachim^RWTH*

2021

Verantwortlichkeitsangabevorgelegt von Diplom-Informatiker Joachim Protze

ImpressumAachen : Joachim Protze 2021

Umfang1 Online-Ressource : Illustrationen

ISBN978-3-754153-24-6

Dissertation, RWTH Aachen University, 2021

Druckausgabe: 2021. - Auch veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Müller, Matthias S. (Thesis advisor)^RWTH* ; Träff, Jesper L. (Thesis advisor) ; Schulz, Martin (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2021-07-22

Online
DOI: 10.18154/RWTH-2021-07909
URL: https://publications.rwth-aachen.de/record/824881/files/824881.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
HPC (frei) ; MPI (frei) ; OpenMP (frei) ; correctness checking (frei) ; parallel programming (frei) ; tools (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Der stetig wachsende Bedarf an Rechenleistung für wissenschaftliches Rechnen und Simulation hat zur Entwicklung heterogener Rechensysteme mit mehreren Ebenen von Parallelität geführt. Betrachtet man die aggregierte Rechenleistung der Top 500 Hochleistungsrechner (HPC Systeme), so kann man von 1993 bis 2013 einen mittleren jährlichen Zuwachs der Rechenleistung von etwa 85% ableiten. Durch das Mooresche Gesetz lässt sich lediglich eine Zuwachsrate von 40% bis 60% erklären. Das zusätzliche Wachstum der HPC Systeme kann durch die zunehmende Anzahl von Rechnerknoten erklärt werden, welche durch ein Verbindungsnetzwerk zum eigentlichen Hochleistungsrechner verbunden sind. Das message passing interface (MPI) hat sich im Hochleistungsrechnen als dominierendes paralleles Programmierparadigma für Rechnen auf verteiltem Speicher herausgestellt, welches auch die gröbste Ebene der Parallelität darstellt. Während im vorherigen Jahrhundert der durch Gordon Moore formulierte Zuwachs überwiegend in steigende Taktraten umgesetzt wurde, sehen wir seit dem Beginn des neuen Jahrhunderts eine Zunahme der Rechenkerne pro Prozessorsockel. Die Rechenkerne eines Sockels beziehungsweise eines Rechenknotens können auf gemeinsamen, geteilten Speicher zugreifen. Wärend MPI auch zum parallelen Programmieren auf geteiltem Speicher eingesetzt wird, kann explizite Nutzung von geteiltem Speicher, wie etwa mit OpenMP, die Skalierbarkeit einer Anwendung verbessern. Die kombinierte Nutzung von MPI und OpenMP ist daher im Hochleistungsrechnen regelmäßig anzutreffen. Speicherzugriffsanomalien wie Dataraces gehören zu der größten Herausforderung im parallelen Programmieren. An Techniken zur Erkennung von Dataraces wird seit Jahrzehnten gearbeitet; sowohl statische wie dynamische Werkzeuge wurden entwickelt. In dieser Arbeit geht es nicht darum, komplett neue Analyseverfahren zu entwickeln, sondern existierende Analyseverfahren, welche überwiegend auf niedriger Abstraktionebene arbeiten, für die hohe Abstraktionsebene der parallelen Programmiersprachen verfügbar zu machen. Dazu entwickelt und präsentiert diese Arbeit einen Analyseworkflow, mit dem Speicherzugriffsanomalien in hybrid parallelen Anwendungen gefunden werden können. Als Grundlage trägt diese Arbeit parallele Varianten von Speicherzugriffsanomalien zusammen, wie sie aus dem sequenziellen Programmieren bekannt sind, identifiziert aber die spezifischen Fehlermuster für Programmieren mit verteiltem und gemeinsamem Speicher. Die Arbeit identifiziert weiterhin die Synchronisierungs-, Nebenläufigkeits- und Speicherzugriffssemantiken, die von den Standards der höheren parallelen Programmierparadigmen explizit und implizit vorgegeben sind, um diese auf die Analyse abzubilden. Als besondere Herausforderung bei der Abbildung von hoher Sprachabstraktion auf niedrige Analyseabstraktion erweist sich die Abbildung der Nebenläufigkeit. Diese Arbeit erweitert die Analyse auf Basis von Vektoruhren um die Möglichkeit Nebenläufigkeit innerhalb einer Ausführungseinheit abzubilden. Dieser Ansatz wird in der Auswertung mit einem alternativen Ansatz verglichen. Eine Kombination der beiden Ansätze deckt den allgemeinen Fall eines unbekannten Anwendungsverhaltens am besten ab.

The demand for ever-growing computing capabilities in scientific computing and simulation has led to heterogeneous computing systems with multiple parallelism levels. The aggregated performance of the Top 500 high-performance computing (HPC) systems showed an annual growth rate of 85% for the years 1993-2013. As this growth rate significantly exceeds the growth rate of 40% to 60% supported by Moore’s law, the additional growth was always supported by an increasing number of computing nodes with distributed memory and connected by a network. The message passing interface (MPI) proved to be the dominating programming paradigm for distributed memory computing as the most coarse-grain level of parallelism in HPC. While performance gain from Moore’s law in the last century mainly went into single-core performance by increasing the clock frequency, we see an increasing number of computing cores per socket since the beginning of this century. The cores within a socket or a node share the memory. Although MPI can be used and is used for shared memory parallelization, explicit use of shared memory as with OpenMP can improve the scalability and performance of parallel applications. As a result, hybrid MPI and OpenMP programming is a common paradigm in HPC. Memory access anomalies such as data races are a severe issue in parallel programming. Data race detection has been studied for years, and different static and dynamic analysis techniques have been presented. This work will not try and propose fundamentally new analysis techniques but will show how high-level abstraction of MPI and OpenMP can be mapped to the low-level abstraction of analysis tools without impact on the analysis’s soundness. This work develops and presents analysis workflows to identify memory access anomalies in hybrid, multi-paradigm parallel applications. This work collects parallel variants of memory access anomalies known from sequential programming and identifies specific patterns for distributed and shared memory programming. This work identifies the high-level synchronization, concurrency, and memory access semantics implicitly and explicitly defined by the parallel programming paradigms’ specifications to provide a mapping to the analysis abstraction. As part of these high-level concurrency concepts, we can identify several sources of concurrency within a thread. This work compares two techniques to handle this high-level concurrency for data race analysis and finds that a combined approach works best in the general case. The evaluation shows that this work’s analysis workflow provides a high precision while enabling increased recall for concurrency within a thread.

OpenAccess:
PDF
(additional files)