Understanding the formation of wait states in one-sided communication

Hermanns, Marc-André; Wolf, Felix Gerd Eugen; Müller, Matthias Stefan

doi:36974

Understanding the formation of wait states in one-sided communication

2018

VerantwortlichkeitsangabeMarc-André Hermanns ; Forschungszentrum Jülich GmbH, Institute for Advanced Simulation (IAS), Jülich Supercomputing Centre (JSC)

ImpressumJülich : Forschungszentrum Jülich GmbH Zentralbibliothek, Verlag 2018

Umfang1 Online-Ressource (xiv, 144 Seiten) : Diagramme

ReiheIAS Series ; 35

Dissertation, RWTH Aachen University, 2017

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

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Müller, Matthias Stefan (Thesis advisor)^RWTH* ; Wolf, Felix Gerd Eugen (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2017-12-04

Online
DOI: 10.18154/RWTH-2018-222635
URL: http://publications.rwth-aachen.de/record/720165/files/720165.pdf
URL: https://juser.fz-juelich.de/record/844062

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
message passing (frei) ; one-sided communication (frei) ; performance analysis (frei) ; root cause analysis (frei) ; wait state formation model (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

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.

Due to the available concurrency in modern-day supercomputers, the complexity of developing efficient parallel applications for these platforms has grown rapidly in the last years. Many applications use message passing for parallelization, offering three main communication paradigms: point-to-point, collective and one-sided communication. Each paradigm fits certain domains of algorithms and communication patterns best. The one-sided paradigm decouples communication and synchronization and allows a single process to define a complete communication. These are important features for runtime systems of new programming paradigms and state-of-the-art dynamic load-balancing strategies. In any process interaction, wait states can occur, where a process is waiting for another---idling---before it proceeds with its local computation. To eliminate such wait states, runtime and application developers alike need support in detecting and quantifying them and their root causes. However, tool support for identifying complex wait states in one-sided communication is scarce. This thesis contributes novel methods for the scalable detection and quantification of wait states in one-sided communication, the automatic identification of their root causes, and the assessment of optimization potential. The methods for wait-state detection and quantification, as introduced by Böhme et al. and extended by this thesis, build upon a parallel post-mortem traversal of process-local event traces, modeling an application's runtime behavior. Performance-relevant data is exchanged just in time on the recorded communication paths. Through the nature of one-sided communication, information on such communication paths is not available on all processes involved, impeding the use of this original approach for one-sided communication. The use of a novel high-level messaging framework enables the exchange of messages on the implicit communication paths of one-sided communication, while retaining the scalability of the original approach. This enables the identification of previously unstudied types of wait states unique to one-sided communication: lack of remote progress and resource contention. Beyond simple accounting of waiting time, other contributed methods allow pinpointing root causes of such wait states and identifying optimization potential in one-sided applications. Furthermore, they distinguish two fundamentally different classes of wait-state root causes: delays for direct process synchronization (similar to point-to-point and collective communication) and contention in case of lock-based process synchronization, whose resolution strategies are diametrically opposed to each other. Finally, the contributed methods enable the identification of the longest wait-state-free execution path (i.e., critical path) in parallel applications using one-sided communication. As only optimization of functions on the critical path will yield performance improvements, its identification is key to choosing promising optimization targets. All of these methods are integrated into the Scalasca performance toolset. Their scalability and effectiveness are demonstrated by evaluating a variety of applications using one-sided communication interfaces running in configurations with up to 65,536 processes.

OpenAccess:
Download fulltext PDF
(additional files)
External link:
Fulltext