Verteilte Algorithmen für fehlertolerante Hardware

Christoph Lenzen

Verteilte Algorithmen für fehlertolerante Hardware

Verteiltes Rechnen ist ein Teilgebiet der Informatik, welches sich mit Systemen befasst, in denen die Kommunikation anstelle von Berechnungen die für eine schnelle Lösung relevante kritische Ressource darstellt. Darüber hinaus beschäftigt sich dieses Gebiet mit Fehlertoleranz, d. h. der Fähigkeit von Systemen, das gewünschte Verhalten selbst dann zu zeigen, wenn Teilkomponenten versagen. Da „Moore‘s Law“, welches besagt, dass sich die Anzahl der elementaren Bausteine handelsüblicher Prozessoren etwa alle 18 Monate verdoppelt, in der Praxis weiterhin gilt, gewinnen beide Aspekte zunehmend an Bedeutung. Dies bedeutet, dass heutzutage z. B. ein Prozessor mit mehreren Kernen ein verteiltes System darstellt.
Falls Ihnen diese Behauptung merkwürdig erscheint, ziehen Sie Folgendes in Betracht:

1. Bei den heutigen Taktfrequenzen von über einem Gigahertz kann ein elektrisches Signal nicht in einem Taktzyklus von einem Ende eines Prozessors zum anderen gelangen.

2. Typische Prozessoren haben inzwischen Milliarden von Transistoren, was es praktisch unmöglich macht, sicherzustellen, dass jeder einzelne davon korrekt arbeitet.

3. Die kleinsten verbauten Elemente auf Computerchips haben inzwischen eine Größe von 10 – 20 Nanometern (Millionstel Millimeter!). Auf dieser Größenskala erfordern es physikalische Effekte, sich mit transienten Fehlern auseinanderzusetzen, bei welchen sich Komponenten vorübergehend unvorhersehbar verhalten.

Abbildung 1: Taktbaum. Im Falle eines Fehlers an der rot markierten Verzweigung versagt der gesamte rot markierte Teil des Baums.

Eine der grundlegendsten Herausforderungen bei der Entwicklung von Computerhardware ist die Verteilung des Taktsignals. Bis zu einer gewissen Grenze kann dies durch so genannte Taktbäume [ siehe Abbildung 1 ] erfolgen. Ein Taktbaum ist dazu ausgelegt, das durch einen einzelnen Quarzoszillator erzeugte Taktsignal so zu verteilen, dass benachbarte Komponenten jeden Takt (beinahe) gleichzeitig empfangen. Hierdurch wird es möglich, Berechnungen synchron durchzuführen: Ein Berechnungsschritt wird ausgeführt, dann werden die Resultate „fixiert“ und weitergegeben und schließlich werden die empfangenen Werte als Eingabe für den nächsten Berechnungsschritt verwendet. Solch eine synchrone Taktung hat viele Vorteile und ist daher das Mittel der Wahl – bis zu dem Punkt, an dem die Größe des Systems dies unpraktikabel werden lässt.

Abbildung 2: Teil eines Taktverteilungsgitters. Jeder Knoten wartet auf das zweite empfangene Taktsignal, bevor er das Taktsignal über seine ausgehenden Verbindungen weitergibt. Die gelben Knoten arbeiten folglich selbst dann korrekt, wenn der rote Knoten oder seine ausgehenden Verbindungen versagen.

 

Wir vertreten die Hypothese, dass die Anwendung verteilter Algorithmen es ermöglicht, ein hochqualitatives Taktsignal effizient und verlässlich in wesentlich größeren Systemen bereitzustellen, als dies mit einem einzelnen Taktbaum möglich wäre. Abbildung 2 veranschaulicht vereinfacht ein Prinzip zur Taktverteilung, was hierfür zur Anwendung kommen könnte. Im Gegensatz zu einem Taktbaum wird das Taktsignal dabei stets auf mehreren Wegen weitergegeben, was das „Umgehen“ von fehlerhaften Knoten ermöglicht. Unsere Gruppe arbeitet an der Realisierung von diesem und ähnlichen Ansätzen, mit dem Ziel, größere und dennoch verlässlichere Computersysteme zu entwickeln.

 

Christoph Lenzen

 

DEPT. 1 Algorithms and Complexity
Phone +49 681 9325-1008
Email:clenzen@mpi-inf.mpg.de