Detailansicht

Exact state reconstruction to recover from node failures in certain iterative linear algebra algorithms

Carlos Andres Pachajoa Mejia

Art der Arbeit

Dissertation

Universität

Universität Wien

Fakultät

Fakultät für Informatik

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Dr.-Studium der technischen Wissenschaften (DissG: Informatik)

Betreuer*innen

Wilfried Gansterer ,

Jesper Larsson Träff

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.71184

URN

urn:nbn:at:at-ubw:1-12968.32443.581439-1

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Die Verbindung von einzelnen Rechenkomponenten erlaubt die Anwendung großerer Rechenkapazitäten, zu einem Zeitpunkt der Geschichte, in dem die Rechenleistung eines einzelnen Kerns aufgrund von physikalischen Grenzen nicht mehr gesteigert werden kann. Die Zuverlässigkeit der einzelnen Komponenten bleibt allerdings ungefähr konstant, daher nimmt die Zeit zwischen Fehlern der Ansammlung ab. Um diesem Problem in zukünftigen, extrem großen Computerclusters vorzubeugen ist Forschung in Resilienzmethoden erförderlich. Diese Doktorarbeit befasst sich mit Resilienzmethoden gegen Knotenausfälle für bestimmte iterative Algorithmen der linearen Algebra, die auf der Rekursion von einer endlichen Anzahl von Termen basieren, insbesondere mit dem Verfahren der konjugierten Gradienten. Der zugrundeliegende Gedanke ist die Rekonstruktion des Zustands des Algorithmus –Unter Zustand versteht man die relevanten Variablen der Iterationen– damit er weiter arbeiten kann, als wäre er unbeeinträchtigt. Wir zeigen die Vorteile von einer exakten Rekonstruktion des Zustands (ESR von engl. exact state reconstruction) eines Algorithmus gegenüber eine annäherende oder partielle Rekonstruktion des Zustands auf. In unseren Experimenten führt ESR zu einer schnelleren Konvergenz nach einem Knotenausfall. Wir bauen auf dem ESR-Ansatz, der von Zizhong Chen eingeführt wurde, auf. Bei diesem Ansatz wird das Matrix-Vektor Produkt erweitert, so dass die Knoten zusätliche redundante Information mit einem geringen Overhead übertragen, die die Rekonstruktion im Falle eines Knotenausfalls ermöglichen. Ein Ersatzknoten kann danach die gespeicherte redundante Information nutzen, um all die sachdienlichen Variablen zu Rekonstruieren, möglicherweiße durch das Lösen eines kleinen, lokalen, linearen Systems. Wir präsentieren drei Erweiterungen für den ESR-Ansatz. Die erste Erweiterung ermöglicht die Wiederherstellung simultan ausfällender Knoten. Zweitens, wir erweitern den Ansatz, so dass die Rekonstruktion auch ohne Ersatzknoten möglich ist. Drittens beschreiben wir die notwendigen Änderungen, um die Speicherfrequenz redundanter Information zu reduzieren. Abschließend stellen wir ein Meta-Algorithmus vor, der automatisch mittels der Durchquerung des Abhängigkeitsgraphs ESR-Strategien herstellt. Wir zeigen die Verwendung dieses Meta-Algorithmus mit drei linearen Algebra Algorithmen: das Verfahren der konjugierten Gradienten, das BiCGStab Verfahren und den Lanczos Algorithmus. Wir schlagen darüber hinaus eine Herangehensweise vor, um die Kondition des lokalen, während der Rekonstruktion zu lösenden linearen Systems zu verbessern.

Abstract

(Englisch)

Connecting more individual computing components together enables the use of more processing power on a given task at a point in history when a single core cannot be made faster due to physical limitations. However, since the reliability of the individual components tends to remain constant, the mean time between failures for the ensemble decreases. Mitigating this problem in future, extreme-scale clusters requires research in resilience techniques. We focus on resilience strategies against node failures for certain iterative linear algebra algorithms based on finite-term recurrences, most prominently the preconditioned conjugate gradients method. The main idea is the reconstruction of the state of the algorithm, comprising the relevant variables involved in the iteration, such that the algorithm can continue operating as if unaffected. We illustrate advantages of the exact state reconstruction (ESR) instead of performing an approximate or partial state reconstruction. In our experiments, ESR leads to a faster convergence after a node failure. The ESR approach was first presented by Zizhong Chen and, in this thesis, we build upon it. In this approach, the matrix-vector product is augmented such that nodes additionally communicate, with a small overhead, redundant information that enables reconstruction in the event of a node failure taking place, after which a replacement node can use the stored redundant information to reconstruct all relevant variables, possibly by solving a small local linear system. We introduce three extensions to the ESR approach. The first extension enables recovery from multiple, simultaneous node failures. The second extension is the ability to recover from node failures without the use of spare nodes. For the third extension, we discuss the necessary modifications to reduce the frequency at which redundant information is stored. Finally, we present a meta-algorithm to automatically produce ESR strategies by traversing the dependency graph of the target algorithm. We illustrate how to use this meta-algorithm with three different target algorithms: the conjugate gradients method, the BICGStab method and the Lanczos algorithm. Additionally, we propose a way to improve the condition of the local linear system to be solved during the reconstruction phase.

Autor*innen

Carlos Andres Pachajoa Mejia

Haupttitel (Englisch)

Exact state reconstruction to recover from node failures in certain iterative linear algebra algorithms

Paralleltitel (Deutsch)

Exakte Rekonstruktion des Zustands bestimmter Algorithmen der linearen Algebra zur Erhohlung von Knotenausfällen

Publikationsjahr

2021

Umfangsangabe

xiv, 135 Seiten : Illustrationen

Sprache

Englisch

Beurteiler*innen

Dominik Göddeke ,

Julien Langou

Klassifikationen

54 Informatik > 54.25 Parallele Datenverarbeitung ,

54 Informatik > 54.99 Informatik: Sonstiges

AC Nummer

AC16541513

Utheses ID

61525

Studienkennzahl

UA | 786 | 880 | |

Detailansicht

Abstracts

Schlagwörter