Fault-Tolerant Coarse-Grained Data-Flow Execution

The progress of the semiconductor technology and the resulting increase of the transistor integration density has driven the development of ever more powerful multi-core processors. The reduction of the feature sizes in the direction of the physical limits increases the probabilities of transient, intermittent, and permanent faults in the chips and demands efficient fault-tolerance mechanisms also for future general-purpose multi-core processors. However, the use of redundant execution mechanisms, as they have been implemented in safety-critical and high-availability lockstep systems for a long time, can be expensive in general-purpose processors, since they require changes to the microarchitecture, which can limit the scalability of the systems. Additionally, lockstep execution complicates the use of modern power management mechanisms as well as the execution of parallel applications. This thesis describes the integration of flexible fault-tolerance mechanisms in a coarse-grained data-flow execution model, which are able to preserve the scalable execution of parallel applications in a multi-core system. For fault detection, we present double execution, the decoupled redundant execution of data-flow threads, which supports fault recovery by the restart of data-flow threads. In this context, necessary adaptions to the data-flow execution model and the hardware architecture as well as techniques for input replication, thread synchronisation, and output comparison are described. Based on the redundant thread execution, a method to diagnose permanent and intermittent faults is developed, which enables the adaption of the system in case of these faults. To further increase the parallelism of double execution, optimistic double execution is proposed, which is able to speculatively start subsequent data-flow threads before result verification. In order to recover from errors detected with optimistic double execution, a data-flow based global checkpointing mechanism is presented. The data-flow based fault-tolerance mechanisms were studied with the open-source multi-core simulator COTSon. The evaluation shows that double execution introduces small run time overhead compared to an ideal lockstep machine and can even achieve a speedup in certain cases. Furthermore, the execution speed of double execution can be gradually reduced, when permanent faults in the processing elements occur. In case of transient faults, the restart of data-flow threads has only a small impact on the execution speed, while optimistic double execution can exploit underutilised system resources to speed up the redundant execution of applications with low parallelism.Das Fortschreiten der Halbleitertechnologie und die damit verbundene Steigerung der Transistorintegrationsdichte hat die Entwicklung immer leistungsfähigerer Multicore-Prozessoren maßgeblich vorangetrieben. Bedingt durch die stetige Verkleinerung der Strukturgrößen in Richtung der physikalischen Grenzen steigen aber auch die Wahrscheinlichkeiten von transienten, intermittierenden und permanenten Fehlern in den Prozessor-Chips. Diese Entwicklung macht effiziente Fehlertoleranzmechanismen in Zukunft auch für universale Multicore-Prozessoren notwendig. Allerdings ist die redundante Programmausführung, wie sie in sicherheitskritischen und hochverfügbaren Lockstep-Systemen seit langer Zeit verwendet wird, für gegenwärtige Universalprozessoren aufwendig, da Änderungen an der Mikroarchitektur benötigt werden, welche die Skalierbarkeit der Systeme einschränken können. Zusätzlich wird die Verwendung moderner Energiesparmaßnahmen und die Ausführung paralleler Anwendungen durch die Lockstep-Implementierung erschwert. Die vorliegende Dissertation beschreibt die Integration von flexiblen Fehlertoleranzmechanismen in ein grobkörniges Datenflussausführungsmodell, welche insbesondere die skalierbare Ausführung von parallelen Anwendungen in einem Multicore-Prozessor erhalten sollen. Zur Fehlererkennung wird die entkoppelte redundante Ausführung von Datenfluss-Threads (Double Execution) vorgestellt, welche die Korrektur von Fehlern durch Thread-Neustarts unterstützt. Dabei werden notwendige Anpassungen am Datenflussausführungsmodell und der Hardware-Architektur sowie Techniken zur Eingabereplikation, zur Thread-Synchronisierung und zum Ausgabevergleich beschrieben. Basierend auf der redundanten Ausführung von Datenfluss-Threads wird eine Methode zur Diagnose von permanenten und intermittierenden Fehlern vorgeschlagen, die im Fehlerfall eine Anpassung des Systems ermöglicht. Um die Parallelität der redundanten Datenflussausführung zu erhöhen, wird die optimistische redundante Ausführung von Datenfluss-Threads (Optimistic Double Execution) vorgestellt, welche nachfolgende Datenfluss-Threads spekulativ starten kann, noch bevor die Korrektheit der Berechnungsergebnisse verifiziert werden konnte. Um die Fehlerkorrektur auch für die optimistische redundante Ausführung zu ermöglichen, wird ein datenflussbasierter globaler Wiederherstellungsmechanismus vorgestellt. Die datenflussbasierten Fehlertoleranzmechanismen wurden mit Hilfe des Open-Source-Multicore-Simulators COTSon untersucht. Dabei zeigte sich, dass die redundante Thread-Ausführung nur geringe zusätzliche Laufzeitkosten gegenüber einer optimalen Lockstep-Maschine aufweist und in bestimmten Fällen sogar Laufzeitvorteile bieten kann. Im Falle von permanenten Fehlern in den Prozessorkernen zeigte sich, dass die Ausführungsgeschwindigkeit des Systems schrittweise angepasst werden kann. Des Weiteren können transiente Fehler durch den Neustart von Datenfluss-Threads mit geringen Kosten korrigiert werden. Für die optimistische redundante Ausführung zeigte sich, dass Anwendungen mit geringer Parallelität ungenutzte Systemressourcen zur Beschleunigung der redundanten Ausführung nutzen können