Understanding the formation of wait states in one-sided communication

Jülich / Forschungszentrum Jülich GmbH Zentralbibliothek, Verlag (2017, 2018) [Buch, Doktorarbeit]

Seite(n): 1 Online-Ressource (xiv, 144 Seiten) : Diagramme

Kurzfassung

Aufgrund der Nebenläufigkeit in modernen Supercomputern hat die Komplexität effiziente parallele Programme zu entwickeln, in den letzten Jahren rapide zugenommen. Eine Vielzahl von Programmen nutzt „Message Passing“ zur Parallelisierung, welches drei Kommunikationsparadigmen bereitstellt: Punkt-zu-Punkt, kollektive und einseitige Kommunikation. Jedes dieser Paradigmen eignet sich für eine spezifische Klasse von Algorithmen. Einseitige Kommunikation entkoppelt die Kommunikation von ihrer Synchronisation und erlaubt es, alle Kommunikationparameter auf einem Prozess zu definieren. Dies ist essenziell für Laufzeitumgebungen neuer Programmierparadigmen und bestimmte Strategien zum dynamischen Lastausgleich. In jeder Interaktion zwischen Prozessen können potentiell Wartezeiten entstehen, wo ein Prozess auf einen anderen wartet bevor er seine Berechnungen fortführen kann. Um solche Wartezeiten zu eliminieren, benötigen Entwickler von Laufzeitumgebungen und Simulationen Unterstützung bei der Erkennung und Quantifizierung der Wartezeiten und ihrer Ursachen. Die bestehende Unterstützung von einseitiger Kommunikation in Werkzeugen zur Leistungsanalyse ist nicht ausreichend. Diese Dissertation beschreibt neue Methoden zur skalierbaren Erkennung und Quantifizierung von Wartezeiten in einseitiger Kommunikation und ihrer Ursachen sowie des Optimierungspotentials. Die beschriebenen Methoden bauen auf eine nach der Messung durchgeführte, parallele Traversierung von Prozess-lokalen Ereignisspuren auf, die das Laufzeitverhalten des Programms modellieren. Leistungsrelevante Daten werden bedarfsorientiert auf den aufgezeichneten Kommunikationspfaden ausgetauscht. Durch die inhärenten Eigenschaften einseitiger Kommunikation steht die Information über die Kommunikationspfade nach der Messung nicht auf allen beteiligten Prozessen zur Verfügung, was die direkte Verwendung des ursprünglichen Ansatzes für die Analyse von einseitiger Kommunikation erschwert. Eine neue, komplementäre Kommunikations-Infrastruktur ermöglicht den Austausch von Nachrichten auf impliziten Kommunikationswegen, während die Skalierbarkeit des ursprünglichen Ansatzes bewahrt bleibt. Dies ermöglicht die Identifikation bisher nicht untersuchter Typen von Wartezeiten wie sie in einseitiger Kommunikation auftreten: Fehlender Kommunikationsfortschritt und Konflikte beim Resourcenzugriff. Jenseits reiner Berechnung von Wartezeiten erweitern die beschriebene Methoden die Ortung von Ursachen der Wartezeiten und die Abschätzung des Optimierungspotentials für Programme mit einseitiger Kommunikation. Dabei wird zwischen zwei fundamental unterschiedlichen Klassen von Ursachen für Wartezeiten unterschieden: Verzögerungen bei direkter Prozesssynchronization, wie sie in der Punkt-zu-Punkt und kollektiven Kommunikation auftreten, und Zugriffskonflikte, wie sie in Lock-basierter Prozesssynchronization auftreten. Die Strategien zur Auflösung dieser beiden Klassen sind genau entgegengesetzt. Des weiteren ermöglichen die beschriebenen Methoden die Identifikation des kritischen Pfades in parallelen Programmen mit einseitiger Kommunikation. Die Identifizierung von Funktionen auf dem kritischen Pfad ist eine Grundvoraussetzung für die Wahl geeigneter Optimierungskandidaten. Alle Methoden wurden im Scalasca Trace Analyzer implementiert. Ihre Skalierbarkeit und Effektivität wird Anhand von verschiedenen parallelen Programmen mit einseitiger Kommunikation auf bis zu 65,536 Prozessoren demonstriert.

Autorinnen und Autoren

Autorinnen und Autoren

Hermanns, Marc-André

Gutachterinnen und Gutachter

Müller, Matthias Stefan
Wolf, Felix Gerd Eugen

Identifikationsnummern

  • REPORT NUMBER: RWTH-2018-222635

Downloads