Characterizing load and communication imbalance in parallel applications

Böhme, David; Wolf, Felix Gerd Eugen

doi:urn:nbn:de:hbz:82-opus-49861

Characterizing load and communication imbalance in parallel applications = Charakterisierung von Last- und Kommunikationsungleichgewichten in parallelen Programmen

Böhme, David (Author)

2014

VerantwortlichkeitsangabeDavid Böhme

ImpressumJülich : Forschungszentrum Jülich, Zentralbibliothek 2014

UmfangXV, 111 S. : Ill., graph. Darst.

ReiheSchriften des Forschungszentrums Jülich : IAS series ; 23

Zugl.: Aachen, Techn. Hochsch., Diss., 2013

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Wolf, Felix Gerd Eugen (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2013-06-07

Online
URN: urn:nbn:de:hbz:82-opus-49861
URL: https://publications.rwth-aachen.de/record/229075/files/4986.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Leistungsbewertung (Genormte SW) ; Parallelverarbeitung (Genormte SW) ; Supercomputer (Genormte SW) ; Informatik (frei) ; performance analysis (frei) ; parallel programming (frei) ; MPI (frei) ; trace analysis (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Der Grad der Parallelverarbeitung in modernen Supercomputern wächst von Generation zu Generation, und wird in naher Zukunft Grössenordnungen von mehreren Millionen Prozessorkernen erreichen. Die Performanz der Anwendungen hängt dadurch immer stärker von der Fähigkeit der Software ab, diesen Parallelismus effizient zu steuern: insbesondere muss der Datenaustausch zwischen den Prozessen effizient organisiert und die Arbeitslast optimal auf die Prozessoren verteilt werden. Leistungsanalysewerkzeuge helfen den Anwendungsentwicklern dabei, die parallele Effizienz ihrer Anwendungen zu evaluieren und Engpässe aufzuspüren. Bisher verfügbare Werkzeuge sind allerdings in der Regel nicht in der Lage, komplexe Formen von Lastimbalancen zu identifizieren und ihre Auswirkungen auf die Leistung zuverlässig zu quantifizieren. Diese Dissertation stellt daher zwei neue Verfahren vor, um in Ereignisspuren von parallelen Programmen automatisch Lastverteilungs-Probleme zu identifizieren und so den Anwendungsentwickler zu den Schwachstellen mit dem größten Optimierungspotential zu leiten. Das erste Verfahren, die Delay-Analyse, identifiziert die Ursachen von Wartezuständen. Ein Delay (Verzögerung) tritt auf, wenn eine Programmaktivität auf einem Prozess länger dauert als auf einem anderen und so an einem folgenden Synchronisationspunkt einen Wartezustand auslöst. Solche Wartezustände, bei denen Prozessorkapazität brach liegt, sind das Hauptsymptom von Ungleichgewichten in der Lastverteilung. Während Wartezustände an sich einfach zu erkennen sind, gestaltet sich die Identifikation der Ursachen aufgrund der potentiell grossen Distanz zwischen einem Wartezustand und dem verursachenden Delay oft schwierig. Die Delay-Analyse schließt diese Lücke. Dazu definiert die Dissertation erstens eine Terminologie und ein Kostenmodell zur Charakterisierung von Delays, und stellt zweitens einen skalierbaren Algorithmus zur Identifikation der Delays und der Berechnung ihrer Kosten vor. Die zweite neue Analysemethode basiert auf der Extraktion des kritischen Pfades. Im Gegensatz zur Delay-Analyse, die die Entstehung von Wartezuständen beschreibt, lassen sich durch die Analyse des kritischen Pfades die Auswirkungen von Imbalancen auf die Programmlaufzeit charakterisieren. Der kritische Pfad ist der längste Ausführungspfad in einem parallelen Programm ohne Wartezustände: daher kann nur die Optimierung von Aktivitäten auf dem kritischen Pfad die Programmlaufzeit verkürzen. Darüber hinaus lassen sich durch den Vergleich der Dauer von Aktivitäten auf dem kritischen Pfad mit der durchschnittlichen Ausführungsdauer dieser Aktivitäten auf jedem Prozess kompakte Leistungsindikatoren ableiten, mit denen komplexe Leistungsprobleme intuitiv hervorgehoben werden können. Insbesondere können Lastverteilungsprobleme schnell erkannt und ihr Einfluss auf die Performanz quantifiziert werden. Anders als bisherige, statistik-basierte Ansätze lassen sich die Leistungsindikatoren sowohl für SPMD als auch für MPMD-Programme anwenden. Beide Verfahren bauen auf der hochskalierbaren Ereignisspur-Analysetechnik des Scalasca-Toolkits auf: durch die parallele Verarbeitung der Ereignisspuren aller Prozesse können die Rechenresourcen und der verteilte Speicher der Zielplattform für die Suche nach Leistungsengpässen selbst herangezogen werden, wodurch die Analyse hochskalierender Programmläufe ermöglicht wird. Der Erkenntnisgewinn durch die neuen Analyseverfahren und ihre Skalierbarkeit werden anhand von Fallstudien mit einer Vielzahl realer HPC-Anwendungen in Konfigurationen mit bis zu 262.144 Prozessen untersucht.

The amount of parallelism in modern supercomputers currently grows from generation to generation, and is expected to reach orders of millions of processor cores in a single system in the near future. Further application performance improvements therefore depend to a large extend on software-managed parallelism: in particular, the software must organize data exchange between processing elements efficiently and optimally distribute the workload between them. Performance analysis tools help developers of parallel applications to evaluate and optimize the parallel efficiency of their programs by pinpointing specific performance bottlenecks. However, existing tools are often incapable of identifying complex imbalance patterns and determining their performance impact reliably. This dissertation presents two novel methods to automatically extract imbalance-related performance problems from event traces generated by MPI programs and intuitively guide the performance analyst to inefficiencies whose optimization promise the highest benefit. The first method, the delay analysis, identifies the root causes of wait states. A delay occurs when a program activity needs more time on one process than on another, which leads to the formation of wait states at a subsequent synchronization point. Wait states, which are intervals through which a process is idle while waiting for the delayed process, are the primary symptom of load imbalance in parallel programs. While wait states themselves are easy to detect, the potentially large temporal and spatial distance between wait states and the delays causing them complicates the identification of wait-state root causes. The delay analysis closes this gap, accounting for both short-term and long-term effects. To this end, the delay analysis comprises two contributions of this dissertation: (1) a cost model and terminology to describe the severity of a delay in terms of the overall waiting time it causes; and (2) a scalable algorithm to identify the locations of delays and determine their cost. The second new analysis method is based on the detection of the critical path. In contrast to the delay analysis, which characterizes the formation of wait states, this critical-path analysis determines the effect of imbalance on program runtime. The critical path is the longest execution path in a parallel program without wait states: optimizing an activity on the critical path will reduce the program’s run time. Comparing the duration of activities on the critical path with their duration on each process yields a set of novel, compact performance indicators. These indicators allow users to evaluate load balance, identify performance bottlenecks, and determine the performance impact of load imbalance at first glance by providing an intuitive understanding of complex performance phenomena. Unlike existing statistics-based load balance metrics, these indicators are applicable to both SPMD and MPMD-style programs. Both analysis methods leverage the scalable event-trace analysis technique employed by the Scalasca toolset: by replaying event traces in parallel, the bottleneck search algorithms can harness the distributed memory and computational resources of the target system for the analysis, allowing them to process even large-scale program runs. The scalability and performance insight that the novel analysis approaches provide are demonstrated by evaluating a variety of real-world HPC codes in configurations with up to 262,144 processor cores.

Fulltext:
PDF