Parallelisierung numerischer Algorithmen in C++
Beschreibung
Praktisch relevante Anwendungsprobleme aus Industrie und Wissenschaft führen häufig zu Simulationsaufgaben, die durch partielle Differentialgleichungen (PDEs) beschrieben werden. Die numerische Lösung von PDEs mithilfe gitterbasierter Methoden ist daher ein unverzichtbarer Bestandteil moderner Softwareframeworks.
In den vergangenen Jahren hat sich die Struktur gängiger Hardwarearchitekturen jedoch grundlegend zugunsten paralleler Hochleistungssysteme gewandelt. Moderne Hochleistungssysteme sind somit zunehmend heterogen: sie umfassen Multi-Core-Prozessoren (CPUs), Graphics Processing Units (GPUs), FPGAs oder andere sog. Beschleuniger.
Die Nutzung dieser heterogenen Hardware stellt für die klassischen gitterbasierten Methoden bestehender Softwareframeworks allerdings eine große Herausforderung dar. Die zugrundeliegenden Berechnungen sind oft durch die Speicherbandbreite limitiert und lassen sich daher nur schwer effizient parallelisieren. Zudem ist die Performanz der parallelisierten Methoden meist nicht portabel: Anwendungen die für ein bestimmtes System optimiert wurden, erreichen so z.B. mitunter schlechtere Performanz auf neueren Systemen.
In diesem Projektseminar werden wir uns verschiedenen Ansätzen zur Parallelisierung numerischer gitterbasierter Methoden widmen. Dazu sollen sich die Teilnehmer zunächst mit den verwendeten Softwareframeworks PACXX und DUNE vertraut machen, um anschließend eine Integration beider Frameworks vornehmen zu können. Durch diesen Ansatz erreichen wir echte Performanzportabilität: bestehende gitterbasierte Methoden, implementiert in DUNE, werden
mithilfe des PACXX Frameworks parallelisiert und hardwarespezifisch optimiert, sodass eine hohe Performanz auf verschiedenen Architekturen gewährleistet werden kann.
Das Distributed and Unified Numerics Environment (DUNE) Framework ist ein modulares C++-Framework zum Lösen partieller Differentialgleichungen mithilfe gitterbasierter Methoden. Im Rahmen eines gemeinsamen Projekts wurden vom Institut für Numerik (AG Prof. Engwer) eine Reihe einfacher Beispielanwendungen bereitgestellt, die von den Projektteilnehmern parallelisiert werden sollen.
Das an der Arbeitsgruppe für parallele und verteilte Systeme (AG Prof. Gorlatch) entwickelte PACXX Framework bietet einen neuartigen, einheitlichen Programmierungsansatz für Beschleunigerarchitekturen. Hauptfunktionalität des PACXX Frameworks ist ein LLVM/Clang basierter Compiler, mit dem beliebiger C++ Code für verschiedene Hardwarearchitekturen übersetzt und parallel zur Ausführung gebracht werden kann. Bei der LLVM-Compilerinfrastruktur handelt es sich um ein international populäres Framework, welches aufgrund vielfältiger Anwendungen im industriellen Umfeld zunehmend Bedeutung erlangt.
Geplante Themengebiete:
(1) Entwurf geeigneter Datenstrukturen zur Repräsentation von Gittern auf GPUs
Die Programmierung von GPUs erfordert oft besondere Datenstrukturen, die die für datenparallele Berechnungen typischen Zugriffsmuster berücksichtigen. Die Teilnehmer sollen daher anhand bestehender Beispielanwendungen aus DUNE die Zugriffsmuster typischer gitterbasierter Algorithmen analysieren und geeignete Datenstrukturen entwickeln, welche auf GPUs effizient eingesetzt werden können. Hierzu sollen unterschiedliche Ansätze experimentell evaluiert werden. Grundlegende Kenntnisse der Programmiersprache C++ werden zwingend vorausgesetzt. Kenntnisse in der parallelen Programmierung, insbesondere der Programmierung von GPUs, sind von Vorteil.
(2) Entwurf paralleler Algorithmen für numerische gitterbasierte Methoden
Neben der Verwendung besonderer Datenstrukturen, erfordern gitterbasierte Methoden unterschiedliche Verarbeitungsschritte, in denen z.B. Zwischenergebnisse vorberechnet und Datenstrukturen generiert werden müssen. Für GPU-basierte Algorithmen sind zudem Trade-offs möglich: anstelle der Erzeugung von Datenstrukturen auf der CPU mit anschließender Datenübertragung zur GPU, können die nötigen Datenstrukturen z.T. auch direkt auf der GPU generiert werden. Die Teilnehmer sollen daher, basierend auf den Konzepten von (1), unterschiedliche Verarbeitungsschritte parallelisieren und im Anschluss eine experimentelle Evaluation der entstehenden Trade-offs vornehmen. Die unterschiedlichen Algorithmen sollen zudem auf allgemeine Muster hin untersucht werden, mit deren Hilfe typische Verarbeitungsschritte durch algorithmische Skelette ausgedrückt werden können. Somit wird die Komposition numerischer Algorithmen erleichtert, wodurch die Vorteile von GPUs bestmöglich ausgenutzt werden können. Als Beispiel und Orientierung dienen bestehende datenparallele Algorithmen aus der linearen Algebra. Grundlegende Kenntnisse der Programmiersprache C++ werden zwingend vorausgesetzt. Kenntnisse in der parallelen Programmierung, insbesondere der Programmierung von GPUs, sind von Vorteil.
(3) Implizites Speichermanagement
Um bestehende Anwendungen mithilfe von GPUs parallelisieren zu können, ist es zwingend erforderlich, die zur Berechnung nötigen Daten zur GPU zu übertragen. Für komplexe Datenstrukturen, welche meist Objekte und Pointer beinhalten, muss daher bisher zusätzlicher technischer Code zur expliziten Verwaltung des Speichers entwickelt werden. Um bestehende Anwendungen leichter parallelisieren zu können, soll das PACXX Framework daher um eine implizite Speicherverwaltung erweitert werden. Diese soll eine Nutzung von C++ Objekten auf der GPU ermöglichen, während die dazu nötigen Speichertransfers transparent durch die Laufzeitumgebung abgewickelt werden. Bestehende Lösungen, wie Unified Memory und globale Addressräume, bieten zwar eine transparente Übertragung von Speicher, besitzen jedoch den Nachteil geringer Performanz und der fehlenden Möglichkeit, vorhandene Klassenmethoden auf der GPU nutzen zu können. Die Teilnehmer sollen eine Modifikation des PACXX Frameworks vornehmen, um mithilfe von LLVM und Clang eine Automatisierung von Datentransfers zwischen CPU und GPU zu realisieren. Vorausgesetzt werden fortgeschrittene C++ Kenntnisse. Erfahrung im Umgang mit LLVM und Clang ist weiterhin von Vorteil.
Ansprechpartner:
Florian Fey - feyf@uni-muenster.de
Vladislav Kucher - kucher@uni-muenster.de
Vorbesprechung:
Freitag den 1. Februar 2019
10 Uhr c.t. in Raum SRII
Veranstalter
Ansprechpartner: Florian Fey und Vladyslav Kucher