Selbststabilisierende Byzantin. Fehlertol. Verteilte Algorithmen für Integrierte Schaltungen

Dieses Projekt ist der Verwendung von selbststabilisierenden Byzantinisch fehlertoleranten verteilten Algorithmen zur Realisierung von robusten very-large scale integrierten (VLSI) Schaltungen gewidmet. Konkreter Gegenstand ist die Entwicklung der Grundlagen eines Frameworks für die Modellierung und Analyse solcher Algorithmen und deren Anwendung auf einige repräsentative Problemstellungen in VLSI-Schaltungen. Neben permanenten Fehlern etwa durch Fertigungsdefekte und Elektromigration sind es vor allem transiente Fehler, wie sie z.B. durch ionisierende Teilchen, elektromagnetische Einstreuungen oder zeitweilig illegale Betriebsbedingungen verursacht werden, die die Zuverlässigkeit moderner integrierter Schaltungen insbesondere im Aerospace-Bereich beeinträchtigen. Anders als klassische Fehlertoleranzmechanismen wie triple modular reduncancy sind selbststabilisierende Algorithmen in der Lage, sich von einer beliebigen Anzahl von transienten Fehlern zu erholen; Byzantinisch fehlertolerante selbststabilisierende Algorithmen erlauben dies sogar in Anwesenheit von permanenten Fehlern. Byzantinisch fehlertolerante selbststabilisierende Algorithmen, die in VLSI-Schaltungen eingesetzt werden sollen, stehen vor besonderen Herausforderungen, die von existierenden Lösungen in keinster Weise berücksichtigt wurden. Zunächst einmal sind Millionen von einfachen logischen Gattern, die kontinuierlich den Wert ihrer Ausgangssignale in Abhängigkeit vom (früheren) Wert ihrer Eingangssignale berechnen, nicht mit den klassischen diskreten Automaten modellierbar, wie sie für verteilte Algorithmen verwendet werden. Darüberhinaus stellen integrierte Schaltungen nur sehr einfache elementare Operationen und Kommunikationsmechanismen zur Verfügung. Existierende selbststabilisierende Algorithmen und existierende Modellierungs- und Analyse- Frameworks können daher ohne grundlegende Modifikationen nicht im VLSI-Kontext verwendet werden. Nichts desto trotz zeigt ein kürzlich von uns (gemeinsam mit Danny Dolev/Hebrew University and Christoph Lenzen/Weizmann Institute) entwickeltes Verfahren für die Byzantinisch fehlertolerante selbststabilisierende Taktgenerierung in VLSI-Schaltungen, daß dies grundsätzlich möglich ist. Das konkrete Ziel von SIC ist die Entwicklung der Grundlagen eines Frameworks für die Modellierung und Analyse von Byzantinisch fehlertolerante selbststabilisierende Algorithmen für VLSI-Schaltungen. Die in SIC geplanten Forschungsarbeiten umfassen grundlegende Forschungsfragen im Bereich wohldefinierter und vollständiger mathematischer Beschreibungen des Stabilisierungsprozesses und digitaler Modelle für die Generierung und Ausbreitung von Metastabilität, die im Falle selbststabilisierender Algorithmen nicht mehr allein mit Engineering-Methoden adäquat behandelt werden können. Diese Arbeiten werden ergänzt durch die Entwicklung von Byzantinisch fehlertoleranten selbststabilisierenden Algorithmen für einige repräsentative Probleme in VLSI-Schaltungen, wie verteilte Taktgenerierung und reliable broadcast. Unter Verwendung des vorgestellten Frameworks werden Korrektheitsbeweise und Performance-Analysen dieser Algorithmen unter adäquaten Fehlermodellen erstellt; die praktische Implementierbarkeit der Algorithmen wird mit Hilfe von Simulationen und FPGA Prototyp-Entwicklungen demonstriert, die auch eine experimentelle Evaluation erlauben.

Im Projekt SIC wurden algorithmische Wege zur Verbesserung der Robustheit von Schaltungen untersucht. Motivation. Während es zahlreiche Studien zur Verbesserung von Fehleranfälligkeit auf Schaltkreisebene (Wahl der Materialien etc.) und auf Softwareebene gibt, sind algorithmische Techniken weniger untersucht. Ansatz. Interessanterweise können VLSI Schaltungen auf mehreren Abstraktionsebenen alsverteilte Systeme modelliert werden: von den Gattern die untereinander binär kommunizieren, bis zu Modulen eines Network on Chip (NoC). Die Idee in SIC war Techniken aus dem Bereich der verteilten Algorithmen zu verwenden um die Robustheit von VLSI Schaltungen zu steigern. Typischerweise, und im Gegensatz zu klassischen verteilten Systemen, sind die einzelnen Prozesse eines solchen Systems wesentlich eingeschränkt in ihrer Art zu Kommunizieren und zu Berechnen. Ein Fokus von SIC wurde auf selbststabilisierende Algorithmen gelegt: ein System löst ein Problem selbststabilisierend, wenn es aus jedem beliebigen Zustand des Systems das Problem löst. Selbststabilisierende Algorithmen sind in Missionen in denen korrumpierte Zustände nicht leicht behoben werden können (z.B. in der Raumfahrt) von Interesse. Resultate. Wir versuchten den obigen Herausforderungen mit unterschiedlichen Herangehensweisen zu begegnen. (i) Wir schlugen ein Modell der verteilten Algorithmen vor, welches für eine formale Analyse von Algorithmen für VLSI Schaltungen geeignet ist. Im Speziellen designten wir einen fehlertoleranten, selbststabilisierenden und verteilten Taktgenerierungs Algorithmus und bewiesen seine Korrektheit. (ii) Wir zeigten ein Problem in bestehenden binären Schaltkreismodellen auf. In nachfolgenden Publikationen präsentierten wir Modelle die dieses Problem umgingen. (iii) Metastabilität ist ein unerlässlicher dritter Zustand in dem jedes bistabile Gatter, z.B. ein Flip-op, unbegränzt lange verweilen kann. Elemente die metastabil werden, können zu Fehlern in nachfolgenden Gattern führen wenn sie von diesen während der Metastabilität gelesen werden. Klassisch wird dies durch Warten vermieden, da Metastabilität nur kurzlebig ist. Wir demonstrierten, dass Warten nicht notwendig ist und dass mit Metastabilität gerechnet werden kann. Im Weiteren untersuchten wir das genauere Verhalten von metastabilen Gattern. (iv) Wir kombinierten die obigen Techniken zu neuen robusten on-chip Services: robuste verteilte Takt Generierung, Takt Verteilung,TaktFrequenzadaption beiAuftreten vonSpannungseinbrüchen, Kommunikationsinfrastruktur auf einem Chip, anhaltbarer Takt, etc. (v) Wir studierten Algorithmen für Consensus-ähnliche Probleme. Der Fokus war hierbei auf dynamischen Netzen.