Forschungsbericht 2015 - Max-Planck-Institut für Informatik

Verteilte Algorithmen für fehlertolerante Hardware

Autoren
Lenzen, Christoph; Friedrichs, Stephan
Abteilungen
Algorithms and Complexity
Zusammenfassung
Die Forschungsgruppe „Theorie verteilter Systeme” befasst sich mit der Entwicklung von Algorithmen für Systeme, in denen eine große Anzahl von Teilnehmern gemeinsam ein Problem löst, das die Kapazitäten jedes einzelnen übersteigt. Neueste Erkenntnisse zeigen, dass die Methoden und algorithmischen Ideen aus diesem Forschungsfeld für die Entwicklung von hochgradig fehlertoleranter Hardware nutzbringend sind. Langfristiges Ziel dieser Forschungsrichtung ist die Entwicklung robuster und effizienter Computerchips, die auch unter extremen Bedingungen, wie z. B. im Weltraum, funktionsfähig sind.

Einführung

„Verteiltes Rechnen” befasst sich mit Computer- und anderen Systemen, in denen die entscheidende Herausforderung nicht darin besteht, eine Aufgabe mit einer kleinen Anzahl an Rechenschritten zu lösen, sondern die einzelnen Komponenten wirkungsvoll zusammenarbeiten zu lassen. Dies ist sehr allgemein zu verstehen: Das Gebiet befasst sich beispielsweise nicht nur mit dem Internet, sondern auch mit Fragen wie „Wie sollte man in einer Auktion bieten, wenn man nur sehr wenig über die anderen Teilnehmer weiß?”, „Wie können Ameisen am wirkungsvollsten gemeinsam nach Nahrung suchen?”, oder „Wie kann man in Facebook verhindern, dass Scheinbenutzerkonten angelegt und missbraucht werden?”.

Für viele solcher Fragestellungen ist Fehlertoleranz – die Fähigkeit des Gesamtsystems, seine Aufgabe zu erfüllen, wenn einzelne Komponenten oder Teilnehmer versagen – von zentraler Relevanz. Es ist von großer ökonomischer Bedeutung und in sicherheitskritischen Systemen (Flugzeugsteuerung, Medizin, etc.) unabdingbar, dass die verwendeten Computersysteme zuverlässig funktionieren. Aufgrund anhaltend rasanter Entwicklung besteht heutige Hardware allerdings aus so vielen mikroskopisch kleinen Bauteilen, dass es praktisch ausgeschlossen ist, dass alle diese Elemente einwandfrei funktionieren. Dieses Problem verschärft sich ständig, da mit der zunehmenden Anzahl an Elementen pro Chip auch eine größere Anzahl an Fehlern einhergeht. Um mit dieser Entwicklung Schritt zu halten, bedarf es verbesserter Methoden, solche Fehler zu maskieren, d. h. die Aufgabe des Computerchips zu erfüllen, ohne dass die internen Fehler nach außen hin sichtbar werden.

Was hat ein einzelner Computerchip mit einem verteilten System zu tun?

Auf den ersten Blick erscheint es vielleicht absurd, dass ein Computerchip ein „verteiltes” System sein soll. Um dies zu verstehen, muss man betrachten, was die größten Hindernisse für dessen korrekten und effizienten Betrieb sind. Galt vor circa ein bis zwei Jahrzehnten noch, dass man durch Erhöhung der Taktrate, d. h. durch Verringerung der Zeit, die jeder einzelne einer nacheinander ausgeführten Reihe von Rechenschritten bedarf, die Gesamtrechenkapazität erhöhen konnte, stieß dies schließlich an physikalische Grenzen (so erinnern sich viele vielleicht noch an die Zeit, als die Taktrate als das wesentliche Geschwindigkeitsmerkmal von Prozessoren galt). Nichts änderte sich jedoch daran, dass sich die Anzahl der verbauten Transistoren auf einem Chip weiter getreu „Moore's Law” [1] verhält, d. h. sich etwa alle zwei Jahre verdoppelt. Dies äußert sich heutzutage typischerweise in einer Verdopplung der Anzahl der Prozessorkerne eines handelsüblichen Computers.

All das hat zur Folge, dass selbst astronomisch kleine Fehlerraten nicht mehr verhindern können, dass man sich Fehlern während des Betriebs stellen muss. Eine einfache Überschlagsrechnung verdeutlicht dies. Nimmt man an, dass etwa einer von einer Milliarde Transistoren fehlerhaft ist, so bedeutete das bei einem Intel Pentium 4 (herausgekommen im Jahr 2000, 42 Millionen Transistoren) noch, dass etwa 19 von 20 Prozessoren vollständig fehlerfrei waren. Die Xbox One Spielekonsole (Jahr 2013) stellt das mit 5 Milliarden Transistoren in den Schatten; mit obiger Fehlerrate wären weniger als 0,7% der Konsolen fehlerfrei. Die verstärkte Miniaturisierung, die dieser Anstieg in der Transistoranzahl erfordert, erleichtert dabei nicht gerade, die Anzahl fehlerhafter Komponenten klein zu halten!

Selbst ohne Fehler ist ein moderner Computerchip ein „verteiltes” System. Bei Lichtgeschwindigkeit würde sich ein elektrisches Signal zwar in jedem Taktzyklus eines 3 GHz-Chips etwa 10 cm fortbewegen, jedoch ist die tatsächliche Geschwindigkeit aufgrund physikalischer Effekte deutlich niedriger. Folglich ist es nicht möglich, das Ergebnis einer Berechnung innerhalb weniger Taktzyklen an einem entfernten Ort auf dem Chip verfügbar zu machen. Die verschiedenen Teile des Chips müssen daher sorgfältig koordiniert werden, um zu ermöglichen, dass das volle Potenzial des Chips genutzt wird. Der Chip ist ein verteiltes System!

Taktung

original
Original 1508157577
Abb. 1: Schaltplan eines DARTS-Systems [2]. Jede der acht ungefähr quadratischen Blöcke im Zentrum generiert ein Taktsignal. Ein verteilter Algorithmus synchronisiert diese Taktsignale. Selbst wenn zwei der Blöcke beschädigt sind und sich beliebig verhalten, bleiben die verbleibenden sechs Blöcke synchronisiert.
Abb. 1: Schaltplan eines DARTS-Systems [2]. Jede der acht ungefähr quadratischen Blöcke im Zentrum generiert ein Taktsignal. Ein verteilter Algorithmus synchronisiert diese Taktsignale. Selbst wenn zwei der Blöcke beschädigt sind und sich beliebig verhalten, bleiben die verbleibenden sechs Blöcke synchronisiert.

Eines der grundlegenden Probleme, die es beim Entwurf eines Computerchips zu lösen gilt, ist das der Taktgenerierung und -verteilung. Der Takt ist der „Herzschlag” eines Prozessors. Er bestimmt, wann ein Berechnungsschritt erfolgt und wann das Ergebnis einer Berechnung kommuniziert wird. So vermeidet man, dass ein „halb fertiges” oder veraltetes Ergebnis weitergegeben wird, welches zu falschen Resultaten führen würde.

original
Original 1508157577
Abb. 2: Taktverteilung mittels eines Taktbaums. Bei einem Fehler an der rot markierten Verzweigung wird der rot markierte Teil des Baums nicht mehr mit einem korrekten Signal versorgt.
Abb. 2: Taktverteilung mittels eines Taktbaums. Bei einem Fehler an der rot markierten Verzweigung wird der rot markierte Teil des Baums nicht mehr mit einem korrekten Signal versorgt.

Traditionell wird das Taktsignal zentral durch einen Quartzoszillator erzeugt. Abbildung 1 zeigt ein fehlertolerantes System zur Taktgenerierung. Das erzeugte Signal muss im Anschluss über den Chip verteilt werden. Bei handelsüblicher Hardware erfolgt das über einen sogenannten Taktbaum [3] (Abb. 2). Durch sorgfältige Ausbalancierung der Distanzen, die das Signal bis an die Endpunkte des Baumes zurücklegt, wird garantiert, dass es beinahe gleichzeitig an den verschiedenen Punkten, wo es verwendet wird, ankommt. Was aber, wenn in einem solchen Baum ein Fehler auftritt? Der ganze Teil des Chips, der über den Ort des Fehlers mit dem Taktsignal versorgt wird, wird unbrauchbar.

Ein Ansatz, dieses Problem zu vermeiden, findet sich in Abbildung 3. Die grundsätzliche Idee ist, eine gitterartige Struktur zu verwenden, bei der jeder Gitterknoten drei eingehende und ausgehende Taktleitungen besitzt. An jedem Knoten befindet sich ein Bauelement, das auf das zweite eingehende Taktsignal wartet, bevor es selbst den Takt weitergibt. Wenn nun ein Fehler auftritt, spielt es keine Rolle, ob dieser Fehler für verspätete oder verfrühte Ankunft des Signals auf einer Leitung sorgt, oder gar ein komplettes Ausbleiben des Signals. Das lokale Taktsignal wird stets als Antwort auf eines der Signale eines fehlerfreien Gitterknotens erzeugt.

Fehlertypen

original
Original 1508157578
Abb. 3: Ausschnitt eines Gitters für fehlertolerante Taktverteilung. Das Signal wird von unten nach oben weitergeleitet, wobei jeder Gitterknoten auf das zweite empfangene Signal wartet. So geben die gelben Knoten das Signal zum korrekten Zeitpunkt weiter, selbst wenn der rote Knoten oder seine ausgehenden Leitungen fehlerhaft sind.
Abb. 3: Ausschnitt eines Gitters für fehlertolerante Taktverteilung. Das Signal wird von unten nach oben weitergeleitet, wobei jeder Gitterknoten auf das zweite empfangene Signal wartet. So geben die gelben Knoten das Signal zum korrekten Zeitpunkt weiter, selbst wenn der rote Knoten oder seine ausgehenden Leitungen fehlerhaft sind.

Diese Art der Taktverteilung ist ein Beispiel für einen einfachen verteilten Algorithmus. Er garantiert die korrekte Verteilung des Taktsignals auf dem Chip auch dann, wenn einer der Knoten (oder eine der Leitungen) defekt ist [4, 5]. Dabei spielt es keine Rolle, welcher Natur dieser Defekt ist: der Algorithmus toleriert sogenannte byzantinische Fehler(a) [6]. Bei genauerer Betrachtung sieht man, dass auch mehrere Fehler toleriert werden können, solange für jeden Knoten mindestens zwei der eingehenden Leitungen funktionieren und von fehlerfreien Knoten angesteuert werden. Bei einem herkömmlichen Taktbaum wäre ein Szenario mit einer größeren Anzahl fehlerhafter Komponenten fatal.

Neben permanenten Fehlern ist es auch von Bedeutung, sich mit transienten Fehlern [7] zu befassen. Bei einem transienten Fehler liegt keine Beschädigung des Bauteils vor, jedoch verhält es sich vorübergehend nicht gemäß seiner Spezifikation. Eine Quelle transienter Fehler, die besonders im Weltraum verstärkt auftritt, ist Strahlung [8]. Da Computerchips dort nicht durch die Atmosphäre geschützt werden, werden sie regelrecht mit geladenen Teilchen bombardiert. Moderne Computerchips benutzen so kleine Bauteile, dass bereits ein einzelner „Treffer” einen genügenden Strom erzeugt, um auf einer Leitung ein Signal vorzugaukeln; die Leitung selbst bleibt dabei in der Regel unbeschädigt.

Der wesentliche Unterschied zwischen transienten und permanenten Fehlern ist, dass es möglich ist, das betroffene Teil später erneut seinem Nutzen zuzuführen. Dies ermöglicht beispielsweise, dass im obigen Algorithmus benachbarte Gitterknoten zu verschiedenen Zeitpunkten fehlerhaft sein können, ohne dass das System als Ganzes zu irgendeinem Zeitpunkt versagt. Ebenfalls ist es möglich, dass sich das System wieder erholt, selbst wenn ein Großteil oder alle Komponenten gleichzeitig versagen. Diese Eigenschaften erfordern durchdachte Ansätze, da sichergestellt werden muss, dass das System aus einem beliebigen Zustand heraus zurück zu korrekter Operation findet.

Eine besondere Herausforderung ist es, optimale Robustheit zu garantieren, ohne bei der Effizienz (d. h. zum Beispiel Chipfläche oder Energieverbrauch) Abstriche zu machen. Die Schwierigkeit sei mit folgender kruder Analogie, die Politologen verzeihen mögen, teilweise veranschaulicht:

  • Demokratien tolerieren eine Minderheit byzantinischer Fehler. Der Wahlprozess verhindert, dass eine Minorität einen schlechten Anführer ernennt. Dies ist das Prinzip des vorgestellten fehlertoleranten Taktausbreitungsprinzips: „extreme Ansichten” werden ignoriert.
  • Eine Diktatur erholt sich von transienten Fehlern, da alle Bürger den Entscheidungen des Herrschers folgen müssen. Taktbäume erholen sich beispielsweise problemlos von transienten Fehlern, da sie schlichtweg das Signal der Quelle weiterleiten.
  • Eine Diktatur mit einem „byzantinischen” Anführer ist unbedingt zu vermeiden.
  • Missstände in einer Demokratie zu beseitigen kann ein sehr langatmiger und schwieriger Prozess sein, selbst (oder besonders) dann, wenn jeder Bürger eine gute Lösung kennt.

Im Fall des beschriebenen Algorithmus zur Taktausbreitung ist es mit einem sorgfältigen Entwurf der Bauteile an den Gitterknoten möglich, alle zuvor genannten Fehlertoleranzeigenschaften zu vereinen. Dabei ist herauszustellen, dass dies nur mathematisch erwiesen werden kann. Es ist schlichtweg unmöglich, alle denkbaren Arten von Fehlern auf einem Computerchip vorherzusagen, geschweige denn in einer Testumgebung zu erzeugen und zu analysieren.

Ausblick

Neben den Aufgaben, ein Taktsignal zu erzeugen [9, 10] und zu verteilen, gibt es noch viele andere Fragestellungen, die angegangen werden müssen, um robuste Computerchips zu entwickeln. Die zuverlässige Kommunikation von Daten und die Möglichkeit, Berechnungen auf solchen Daten anzustellen, sind wesentliche Grundlagen eines anwendbaren Computersystems. Auch diese Aufgaben müssen fehlertolerant gelöst werden, damit das Gesamtsystem robust ist. Ziel der Forschungsgruppe „Theorie verteilter Systeme” ist es, bestmögliche Lösungen für diese Aufgaben zu entwickeln.


(a) Dieser Begriff entstand aus einer Analogie zu byzantinischen Generälen, die einen Angriff planen. Ein nennenswerter Teil der Generäle ist korrupt und versucht, den Angriff der loyalen Generäle zum Scheitern zu verurteilen.

Literaturhinweise

1.
Van Hoosear, T. et al.
Moore's Law
Wikipedia, retrieved January 2015
2.
Függer, M.; Schmid, U.
Reconciling Fault-Tolerant Distributed Computing and Systems-on-Chip
Distributed Computing 24, 323-355 (2012)
3.
Yeh, C.; Wilke, G.; Chen, H.; Reddy, S.; Nguyen, H.; Miyoshi, T.; Walker, W.; Murgai, R.
Clock Distribution Architectures: a Comparative Study
7th Symposium on Quality Electronic Design (ISQED), 85-91 (2006)
4.
Dolev, D.; Függer, M.; Lenzen, C.; Perner, M.; Schmid, U.
HEX: Scaling Honeycombs is Easier than Scaling Clock Trees
25th Symposium on Parallelism in Algorithms and Architectures (SPAA), 164-175 (2013)
5.
Lenzen, C.; Perner, M.; Sigl, M.; Schmid, U.
Byzantine Self-Stabilizing Clock Distribution with HEX: Implementation, Simulation, Clock Multiplication
6th Conference on Dependability (DEPEND), 6-15 (2013)
6.
Lamport, L.; Shostak, R.; Pease, M.
The Byzantine Generals Problem
ACM Transactions on Programming Languages and Systems 4, 382-401 (1982)
7.
Dijkstra, E.
Self-stabilizing Systems in Spite of Distributed Control
Communications of the ACM 17, 643-644 (1974)
8.
Constantinesco, C.
Trends and Challenges in VLSI Circuit Reliability
IEEE Micro 23, 14-19 (2003)
9.
Dolev, D.; Függer, M.; Lenzen, C.; Schmid, U.
Fault-tolerant Algorithms for Tick-generation in Asynchronous Logic: Robust Pulse Generation
Journal of the ACM 61, 30 (2014)
10.
Dolev, D.; Függer, M.; Lenzen, C.; Posch, M.; Schmid, U.; Steininger, A.
Rigorously Modeling Self-Stabilizing Fault-Tolerant Circuits: An Ultra-Robust Clocking Scheme for Systems-on-Chip
Journal of Computer and System Sciences, 80, 860-900 (2014)
Zur Redakteursansicht