Fault tolerant linear least squares solvers and matrix multiplication in parallel and distributed environments

Autor: Prikopa, Karl E.
Jazyk: angličtina
Rok vydání: 2021
DOI: 10.25365/thesis.70289
Popis: In der Welt des Computers sind Fehler allgegenwärtig, ihr mögliches Auftreten wird aber im Allgemeinen vernachlässigt. Mit dem Aufstieg der Supercomputer in den exascale Bereich und darüber hinaus, gewinnt die Fehlerbehandlung bei lang-laufenden Berechnungen immer mehr an Bedeutung. In dieser Dissertation liegt der Fokus auf die Erkennung und Behebung von Bit-Flips, ohne dabei die hohe Leistungsfähigkeit der Algorithmen und die hohe Genauigkeit der Ergebnisse jemals aus den Augen zu lassen. Dabei wenden wir verschiedene Methoden der Fehlertoleranz an und demonstrieren, dass Fehlerbehandlung nicht auf Kosten der Leistung oder der Genauigkeit erzielt werden muss. Eine zentrale Komponente dieser Dissertation ist die Verwendung von Arithmetik in variabler Genauigkeit und der Methode iterativer Verbesserung. Wir sind besonders daran interessiert, Genauigkeiten zu verwenden, die signifikant niedriger sind als IEEE Single Precision, um die Performance des Algorithmus zu verbessern, gleichzeitig aber die Zielgenauigkeit von IEEE Double Precision weiterhin zu erreichen. Basierend auf einem für FPGAs entwickelten analytischen Performancemodells und einer Softwareemulation konnten signifikante Leistungsverbesserungen im Vergleich zur Verwendung von IEEE Standardpräzisionen erzielt werden. Iterative Refinement ist ein selbst-heilender Algorithmus und eignet sich daher auch ideal, um Bit-Flips zu korrigieren. Ein weiteres Ergebnis dieser Forschungsarbeit ist ein verteilter, fehlertoleranter Algorithmus für das lineare Ausgleichungsproblem für drahtlose Sensornetzwerke und hochperformante Systeme, der auf den epidemiologischen Algorithmen namens "Gossiping" basiert. In der Literatur gibt es sehr wenige LLS Algorithmen dessen Kommunikation nur mit ihren direkten Nachbarn stattfindet. Unser Zugang bedient sich der Semi-Normalgleichungen in Kombination mit Iterative Refinement, welches die ansonsten numerisch instabile Methode stabilisiert. Durch die Verwendung von variabler Genauigkeit wird die Menge an benötigter Kommunikation zwischen den Knoten reduziert, wodurch die Performance des Algorithmus steigt und weiterhin die hohe Zielgenauigkeit erreicht wird, während die Berechnung gleichzeitig vor Datenkorruption durch Bit-Flips oder Nachrichtenverlust geschützt wird. Diese Forschungserkenntnisse führten zur Entwicklung unserer fehlertoleranten 2.5D Matrixmultiplikation. Wir haben eine verbesserte Version des bekannten, fehlertoleranten Algorithmus ABFT ("algorithm-based fault tolerance") entwickelt, welche, im Gegensatz zum klassischen Algorithmus, Bit-Flips an jeder Position einer Gleitkommazahl beheben kann. In Kombination mit der hochperformanten 2.5D Matrixmultiplikation haben wir bewiesen, dass der Overhead unserer fehlertoleranten Variante des Algorithmus weniger als ein Prozent ausmacht.
Faults are a ubiquitous companion in the world of computing, but generally the possibility of faults occurring is neglected. The rise of exascale and future extreme-scale supercomputers has increased the importance of handling faults during long-running computations. In this thesis the battle against bit-flips is handled at the algorithmic level, while never losing sight of high performance and high accuracy. We apply fault tolerance to two different linear algebra algorithms in two very different environments, while proving that fault handling does not have to come at the cost of high performance or high accuracy. A core concept employed throughout this thesis is arbitrary precision arithmetic and iterative refinement. In particular, we are interested in using significantly lower working precisions to improve the overall performance of the algorithm while still achieving double precision accuracy in the result. Based on a performance model developed for FPGAs and a software emulated implementation, we demonstrate the feasibility of low working precisions, showing significant performance gains compared to iterative refinement using standard precision levels. Iterative refinement is a naturally self-healing algorithm and therefore can be used to correct bit-flips. Another result of this research is a truly distributed and fault tolerant linear least squares (LLS) solver for wireless sensor networks and high-performance systems based on epidemic algorithms known as gossiping. Very few LLS solvers have considered a truly distributed approach, where nodes only communicate with their direct neighbourhood. Our approach is based on the semi-normal equations in combination with iterative refinement, which stabilises the otherwise numerically unstable method. The use of arbitrary precision reduces the amount of communication while still achieving high precision accuracy and increasing the performance, while at the same time protecting the computation from silent data corruption. The research results led to the development of a fault tolerant communication-optimal 2.5D matrix multiplication. We developed an improved version of the well-known algorithm-based fault tolerance method which, unlike the classical algorithm, can handle bit-flips at any position of a floating-point number. By integrating our algorithm into the high-performance 2.5D matrix multiplication we demonstrate that the overhead of our fault tolerant variant is less than one percent.
Databáze: OpenAIRE
Externí odkaz: