Detailansicht
Tolerating node failures in communication-avoiding conjugate gradient methods
Viktoria Mayer
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Informatik
Betreuer*in
Wilfried Gansterer
DOI
10.25365/thesis.71154
URN
urn:nbn:at:at-ubw:1-19845.73935.337632-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die wachsende Anzahl von Knoten bei parallelen Großrechnern wirft zwei Herausforderungen auf. Zum einen wird die globale Kommunikation zu einem schwerwiegenden Leistungsengpass. Zum anderen steigt die Wahrscheinlichkeit für Knotenausfälle mit der Knotenanzahl.
Das Verfahren der Konjugierten Gradienten mit Vorkonditionierung (PCG-Verfahren) ist ein iteratives Verfahren zur Lösung von großen dünn besetzten linearen Gleichungssystemen, das mit diesen beiden Herausforderungen konfrontiert ist.
Ein häufig verwendeter Ansatz, um einen Algorithmus gegen Knotenausfälle zu schützen, ist Checkpoint-Restart, bei dem der derzeitige Zustand des Verfahrens periodisch gesichert wird. Um den oft erheblichen Zusatzaufwand von Checkpoint-Restart zu vermeiden, können algorithmus-spezifische Eigenschaften verwendet werden. Die Methode "Exact State Reconstruction" (ESR) für das PCG-Verfahren stellt die verlorenen Teile des Zustands zum Zeitpunkt der Knotenausfälle wieder her, nachdem redundant gespeicherte Daten von einem Nachbarknoten erhalten wurden. Diese redundant gespeicherten Daten können während der Ausführung des resilienten PCG-Verfahrens mit sehr wenig Zusatzaufwand kommuniziert werden, indem die dem Algorithmus inhärente Datenredundanz ausgenutzt wird.
Auf parallelen Großrechnern wird die globale Kommunikation zu einem schwerwiegenden Leistungsengpass im PCG-Verfahren. Die parallelen Matrix-Vektor-Produkte benötigen oft nur Kommunikation mit lokalen Nachbarknoten. Die Skalarprodukte hingegen benötigen globale Reduktionsoperationen, in die alle Knoten involviert sind und die daher zu Synchronisationsschritten in jeder Iteration führen. Kommunikationsvermeidende s-step-Verfahren reduzieren die Anzahl der globalen Synchronisationsschritte um den Faktor O(s), indem die PCG-Iterationen in Blöcken on s berechnet werden.
Wir erweitern zwei kommunikationsvermeidende s-step-Verfahren, sodass diese resilient gegen Knotenausfälle sind. Dabei verwenden wir ähnliche Ansätze wie bei ESR für das Standard-PCG-Verfahren. Theoretische und experimentelle Evaluierungen zeigen, dass unsere neuen Algorithmen imstande sind, Resilienz mit wenig Zusatzaufwand im Vergleich zu den nicht resilienten Methoden zu erreichen, sowohl im fehlerfreien Fall als auch im Fall von Knotenausfällen. Dabei bleiben die kommunikationsvermeidenden Eigenschaften und daher die Skalierbarkeit dieser Verfahren erhalten.
Abstract
(Englisch)
Today's growing number of nodes in large-scale parallel computers raise two challenges. Firstly, global communication becomes a major bottleneck. Secondly, the likelihood of node failures increases with the number of nodes. The Preconditioned Conjugate Gradient (PCG) method is an iterative solver for large sparse linear systems facing these challenges.
A commonly used approach to make an algorithm fault-tolerant is Checkpoint-Restart, which periodically saves the state of a solver. To avoid the often considerable overhead of Checkpoint-Restart, algorithm-specific properties can be exploited.
The Exact State Reconstruction (ESR) method for the PCG algorithm recovers the lost parts of the state in case of node failures after retrieving redundantly stored data from neighbour nodes.
This data is communicated during the execution of resilient PCG with very little overhead by exploiting the inherent data redundancy of the solver.
On large-scale parallel computers, communication becomes a major bottleneck in the PCG method. The parallel matrix-vector products typically only involve communication between local neighbour nodes. However, the scalar products require global reduction operations involving all nodes, resulting in synchronization steps in each iteration.
Communication-avoiding s-step methods reduce the number of global synchronizations by a factor of O(s) by computing the iterations of PCG in blocks of s.
We extend two communication-avoiding s-step methods to make them resilient against node failures using similar ideas as the ESR strategy for the standard PCG method. Theoretical and experimental evaluations show that our new approach is able to achieve resilience with low overhead compared to the non-resilient methods both in the failure-free case and when node failures occur while preserving communication-avoiding properties and therefore scalability of the algorithms.
Schlagwörter
Schlagwörter
(Deutsch)
kommunikationsvermeidende Algorithmen Iterative Gleichungslöser Krylov-Unterraum-Verfahren Verfahren der konjugierten Gradienten algorithmus-basierte Fehlertoleranz
Schlagwörter
(Englisch)
communication-avoiding algorithms iterative solvers Krylov subspace methods Conjugate Gradient methods algorithm-based fault-tolerance
Autor*innen
Viktoria Mayer
Haupttitel (Englisch)
Tolerating node failures in communication-avoiding conjugate gradient methods
Paralleltitel (Deutsch)
Tolerieren von Knotenausfällen in kommunikationsvermeidenden konjugierten Gradientenverfahren
Publikationsjahr
2022
Umfangsangabe
xiii, 77 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Wilfried Gansterer
AC Nummer
AC16539471
Utheses ID
63202
Studienkennzahl
UA | 066 | 921 | |