Informatik-Kolloquien
333. Informatik-Kolloquium
Öffentliche Verteidigung im Rahmen des Promotionsverfahrens
Frau Laura Morgenstern, M.Sc.
TU Chemnitz
Fakultät für Informatik
Professur Betriebssysteme
"Eventify Meets Heterogeneity: Enabling Fine-Grained Task-Parallelismon GPUs"
Dienstag, 15.08.2023, 13:00 Uhr, Straße der Nationen 62, Böttcher-Bau, 1/336 (neu: A12.336)
Alle interessierten Personen sind herzlich eingeladen!
Zusammenfassung:
Viele wissenschaftliche Berechnungsalgorithmen bieten kaum ausreichende Datenparallelität, um die massive Parallelität heutiger Prozessoren effizient zu nutzen. Um diese Herausforderung zu bewältigen, wurden verschiedene taskparallele Programmiermodelle entwickelt, die eine flexible Beschreibung von Algorithmen entlang von Task-Graphen ermöglichen. Bei Algorithmen mit dichten Task-Graphen ist es jedoch immer noch schwierig, die Task-Parallelität effizient zu nutzen, da sie programmatisch komplex zu beschreiben ist und durch die hohe Anzahl an Task-Abhängigkeiten hohe Parallelisierungskosten nach sich zieht. Dies wird insbesondere auf GPUs zu einer Herausforderung, da sie nicht für synchronisationsgetriebene Anwendungen ausgelegt sind. Dieser Vortrag stellt ein Ausführungsmodell vor, das feinkörnige Task-Parallelität auf GPUs ermöglicht. Der Vortrag diskutiert das Stream-Interaktionsmodell hinter Flynns Taxonomie als einheitliche Grundlage für Parallelität in Architekturen und Programmiermodellen. Außerdem werden die quantitativen Trends in CPU- und GPU-Architekturen und ihr Einfluss auf Programmiermodelle untersucht. Kernthema des Vortrags ist die Vorstellung eines Ausführungsmodells, das Multi-Threading, effiziente Synchronisierung und Queue-basiertes Task-Scheduling auf GPUs ermöglicht. Abschließend wird die Leistungsfähigkeit dieses Ansatzes am Beispiel des Task-Graphen der Fast Multipole Method untersucht. Die Ergebnisse zeigen, dass feinkörnige Task-Parallelität die Ausführungszeit im Vergleich zur klassischen schleifenbasierten datenparallelen Programmierung für den vorliegenden Anwendungsfall um eine Größenordnung verbessern kann.Abstract:
Many scientific computing algorithms barely provide sufficient data-parallelism to exploit the ever-increasing hardware parallelism of today?s heterogeneous computing environments. To tackle this challenge, diverse task-parallel programming technologies have been introduced that allow for the flexible description of algorithms along task graphs. For algorithms with dense task graphs, however, task-parallelism is still hard to exploit efficiently since it is programmatically complex to describe and imposes high dependency resolution overheads on the execution model. This becomes especially challenging on GPUs which are not designed for synchronization-heavy applications. This talk presents an execution model that enables fine-grained task parallelism on GPUs as proposed in the underlying dissertation. Firstly, it discusses the stream interaction model behind Flynn?s Taxonomy as uniform foundation for concurrency in architectures and programming models. Secondly, it analyzes the quantitative trends in CPU and GPU architectures and examines their influence on programming models. Thirdly, it outlines execution model that enables threading, efficient blocking synchronization and queue-based task scheduling on GPUs and describes its implementation based on the task-parallel programming approach Eventify. Concluding, it examines the performance of this approach with the task graph of a fast multipole method as use case. The results show that fine-grained task parallelism can improve the execution time for this use case by an order of magnitude in comparison to classical loop-based data parallelism.
