09.06.2022, 11:30 Uhr
Universität Wien
Seminarraum 11
Währinger Str. 29
1090 Wien
Titel: „Tolerating Node Failures in Communication-avoiding
Conjugate Gradient Methods“
Kurzfassung:
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 (PCGVerfahren)
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.
v