TP 1: Selbstadaptierung für parallele irreguläre Algorithmen
Final Report Abstract
Ziel des Projekts war die Entwicklung, Untersuchung und Realisierung von Softwarekonzepten zur Selbstadaptierung und -Optimierung für irreguläre Algorithmen auf parallelen, heterogenen Plattformen. Irreguläre Algorithmen umfassen dabei Algorithmen insbesondere des wissenschaftlichen Rechnens, die ein eingabeabhängiges oder dynamisches Verhalten von Berechnungen und Daten aufweisen. Effiziente parallele Realisierungen solcher Algorithmen benötigen aufgrund des kaum vorhersagbaren Wachstums der Datenmengen geeignete Lastbalancierungsverfahren und variable Kommunikationsmechanismen. Aktuelle heterogene parallele Plattformen und komplexe Prozessor- und Speicherstrukturen führen jedoch dazu, dass diese Verfahren und Mechanismen nicht ohne Weiteres die gewünschte Effizienz und Skalierbarkeit aufweisen. Im Projekt wurden Verfahren der Selbstadaptierung entwickelt, die dynamisch effizienzsteigernde Anpassungen an eine Hardwareplattform erreichen können. Dazu wurden Verfahren der meist dynamischen Lastbalancierung mit Verfahren der Selbstadaptierung oder des automatischen Tunings kombiniert. Es wurden Methoden, Techniken und Softwareentwicklungskonzepte zur Selbstadaptierung irregulärer Algorithmen untersucht und entwickelt. Selbstadaptierende Softwarekomponenten und -entwicklungsunterstützungen wurden realisiert und zur Entwicklung effizienter, paralleler Software für irreguläre Algorithmen eingesetzt. Die untersuchten Anwendungen umfassen: eine adaptive Finite-Elemente-Methode (FEM), eine Simulation von Diffusionsprozessen auf Sierpiriski-Teppichen, ein hierarchisches Radiosity-Verfahren sowie eine Implementierung der Schnellen Multipolmethode (FMM). Alle genannten Anwendungen weisen stark irreguläre Charakteristika auf, stellen aber aufgrund spezieller Ausprägungen unterschiedliche Anforderungen an eine parallele Umsetzung hinsichtlich der Lastimbalancen, des Kommunikationsverhaltens und der Datenzugriffsmuster. Anhand der untersuchten Anwendungen wurden verschiedene Konzepte und Lösungen für eine effiziente Ausführung irregulärer Algorithmen auf homogenen und heterogenen Rechnerarchitekturen entwickelt. Konkret wurden die folgenden Ergebnisse erzielt: • Das Task-Pool-Konzept zur Verwaltung parallel abzuarbeitender Teilaufgaben wurde weiterentwickelt, wodurch ein dynamischer, fließender Übergang zwischen zentraler und dezentraler Taskverwaltung ermöglicht wird, was für irreguläre Anwendungen unerlässlich ist. • Es sind Verfahren zum automatischen Tuning entstanden, die die Eingabedaten bei der Auswahl der effizientesten Verarbeitungsmöglichkelten berücksichtigen. Das beinhaltet auch ein Verfahren zur dynamischen Verteilung der Rechenlast zwischen CPU und Grafikprozessor. • Es wurde eine Bibliothek zum parallelen Sortieren entwickelt, die die Auswahl verschiedener paralleler Sortieralgorithmen, das Zusammensetzen neuer Algorithmen aus vorhandenen Algorithmenfragmenten sowie die Anpassung der Datenverteilung an die Anforderungen der Anwendung und die Gegebenheiten des Parallelrechners zum Zwecke der Lastverteilung ermöglicht. • Für die Kommunikation in Parallelrechnern, die bei irregulären Anwendungen oft schwer vorhersehbar ist, wurden effiziente Operationen entwickelt, u. a. für die Reduktions- und die All-to-all-Operation. • In Verallgemeinerung der Ergebnisse wurde ein Verfahren zur Entwicklung von Autotuning-Systemen für irreguläre Anwendung unter Berücksichtigung von Eingabedaten entworfen.
Publications
- Library Support for Parallel Sorting in Scientific Computations. In: Proc. of the 13th Int Euro-Par Conf, Band 4641 der Reihe LNCS, Seiten 695-704. Springer, 2007
Dachsel, Holger, Michael Hofmann und Gudula Rünger
- Fine-grained Data Distribution Operations for Particle Codes. In: Ropo, M., J. Westerholm und J. Dongarra (Herausgeber): Recent Advances in Parallel Virtual Machine and Message Passing Interface, 16th European PVM/MPI Users Group Meeting, Band 5759 der Reihe LNCS, Seiten 54-63. Springer, 2009
Hofmann, Michael und Gudula Rünger
- A Partitioning Algorithm for Parallel Sorting on Distributed Memory Systems. In: Proc. of the IEEE 13th Int. Conf on High Performance Computing and Communications (HPCC2011), Seiten 402-411. IEEE, 2011
Hofmann, Michael und Gudula Rünger
- Accelerating Physical Simulations Using Graphics Processing Units, it - Information Technology, 53(2):49-59, 2011
Hoffmann, Karl Heinz, Michael Hofmann, Jens Lang, Gudula Rünger und Steffen Seeger
- Automatic Tuning of the Fast Multipole Method Based on Integrated Performance Prediction. In: Proc. of the 14th IEEE Int. Conf. on High Performance Computing and Communications (l-IPCC-2012), 2012
Dachsel, Holger, Michael Hofmann, Jens Lang und Gudula Rünger
- Array-based reduction operations for a parallel adaptive FEM. In: Keller, Rainer, David Kramer und Jan-Phllipp Weiß (Herausgeber): Facing the Multicore Challenge III, Band 7686 der Reihe Lecture Notes in Computer Science, Seiten 25-36. Springer, 2013
Balg, Martina, Jens Lang, Arnd Meyer und Gudula Rünger
- Dynamic Distribution of Workload Between CPU and GPU for a Parallel Conjugate Gradient Method in an Adaptive FEM. Procedia Computer Science, 18:299-308, 2013
Lang, Jens und Gudula Rünger
(See online at https://doi.org/10.1016/j.procs.2013.05.193) - An execution time and energy model for an energy-aware execution of a conjugate gradient method with CPU/GPU collaboration. Journal of Parallel and Distributed Computing, 74{9):2884 - 2897, 2014
Lang, Jens und Gudula Rünger
(See online at https://doi.org/10.1016/j.jpdc.2014.06.001)
