Resilience versus Performance in Numerical Linear Algebra

Konzepte für Fehlertoleranz werden in vielen Anwendungsbereichen von Computersystemen immer wichtiger, da verschiedene Faktoren (unter anderem die rasch wachsende Komplexität dieser Systeme sowie Bemühungen, deren Energieeffizienz zu verbessern) die Häufigkeit verschiedener Arten von Fehlern, Defekten und Störungen ansteigen lässt. Dieses Phänomen ist von diversen Netzwerksystemen wie "smart grids" oder "smart metering" über das "Internet of things" bis zum Hochleistungsrechnen (HPC) zu beobachten. Während Konzepte für Fehlertoleranz auf Systemebene schon eine lange Tradition haben, ist es Gegenstand aktueller Forschung, ob und in welchem Ausmaß es möglich ist, auf der Ebene der Algorithmen Widerstandsfähigkeit gegenüber Fehlern und Systemstörungen zu erreichen und welchen Mehraufwand beziehungsweise welche Leistungseinbußen das verursacht.

Im Verlauf des REPEAL-Projektes haben wir neue fehlertolerante Algorithmen für ausgewählte Probleme der numerischen linearen Algebra entwickelt, analysiert und evaluiert, die trotz Auftreten von unbemerkten Störungen im System genaue Ergebnisse liefern. Insbesondere untersuchten wir die Matrizenmultiplikation, die Summation und Durchschnittbildung in parallelen oder verteilten Systemen, Algorithmen für die Lösung von Ausgleichsproblemen und Algorithmen für die Lösung großer schwachbesetzter Gleichungssysteme. Diese betrachteten Probleme stellen zentrale Bausteine für numerische Simulationen in vielen Anwendungsbereichen dar, von klassischen Modellen basierend auf Differentialgleichungen bis zu modernen datenbasierten Modellen.

Die Fehler und Störungen, die die Abarbeitung eines Algorithmus beeinflussen, können sehr vielfältig sein. Das reicht von Ausfällen von Hardwarekomponenten über unzuverlässige Kommunikation in parallelen oder verteilten Systemen (zum Beispiel Störung oder Verlust von Nachrichten) bis zu spontanen und unbemerkten Datenfehlern (sogenannten “bit flips”) in den Speicherbausteinen. Wir haben uns im Verlauf des Projektes vor allem auf zwei Arten von Fehlern konzentriert: Im ersten Teil des Projekts standen Ansätze im Vordergrund, Algorithmen widerstandfähig gegen unbemerkte Datenfehler zu machen. Im zweiten Teil des Projekts standen Ansätze im Vordergrund, parallele Algorithmen widerstandsfähig gegen den unvorhergesehenen Ausfall von Knoten zu machen.

Es gelang dem Projektteam nicht nur, für die ausgewählten Problemstellungen widerstandsfähige Algorithmen zu entwickeln, sondern es wurden auch prototypische Implementierungen entwickelt und evaluiert. Experimentell konnte nachgewiesen werden, dass die neuen Algorithmen deutlich widerstandsfähiger als existierende Algorithmen sind, dass der Mehraufwand für die erreichte Widerstandsfähigkeit aber sehr gering ist.