Fault-tolerant distributed algorithms for on-chip tick generation: concepts, implementations and evaluations

Abstract

Im Zuge dieser Dissertation wird ein neuartiger Ansatz zur On-Chip Generierung eines fehlertoleranten Taktes entwickelt und im Detail vorgestellt. Die Relevanz der Forschungsarbeiten wird dabei mit den immer kleiner werdenden Strukturgrößen im Chip-Design und dem damit einhergehenden Anstieg der Fehlerraten motiviert. Um zukünftige Schaltungen ausreichend robust gestalten zu können, muss in Anbetracht der erhöhten Fehlerraten unter anderem auch das Taktsignal, welches einen kritischen "single point of failure" von synchronen Schaltungen darstellt, durch Fehlertoleranz-Mechanismen geschützt oder durch fehlertolerante Alternativen ersetzt werden. In der vorliegenden Arbeit wird daher eine solche Alternative zu herkömmlichen zentral getakteten Schaltungen erarbeitet.<br />Der in dieser Arbeit vorgestellte Taktgenerierungsansatz basiert auf der Hardware-Implementierung eines bekannten verteilten Algorithmus. Das Besondere an dieser Implementierung ist, dass in einem System von n >=3f + 2 Knoten f dieser Einheiten beliebig (byzantinisch) fehlerhaft sein dürfen. Einen weiteren wichtigen Vorteil stellt die Tatsache dar, dass im Gegensatz zu herkömmlichen Verfahren keine Taktquellen (Oszillatoren) benötigt werden. Die asynchrone Implementierung des präsentierten Ansatzes ermöglicht es, die Taktsignale synchron zu generieren statt auf die Synchronisation von exisitierenden Taktquellen zurückzugreifen. Desweiteren, und noch viel wichtiger, werden durch die vorgeschlagene Architektur Metastabilitätsprobleme an den Schnittstellen zwischen verschiedenen Taktdomänen gänzlich vermieden.<br />Die Transformation des im Bereich der Software angesiedelten Algorithmus in die Welt des asynchronen Schaltungsentwurfs stellte sich als nicht trivialer Prozess heraus und repräsentiert einen wichtigen Teil der durchgeführten Arbeiten. Um den aus den zuvor erwähnten Transformationen schlußendlich hervorgehenden VLSI (Very Large Scale Integration) Chip und die darauf aufbauende fehlertolerante Taktgenerierungsarchitektur charakterisieren zu können, wurden umfangreiche Messreihen durchgeführt und ausgewertet.<br />Die Evaluierungen umfassen dabei sowohl die Validierung der aus formalen Modellen des Ansatzes hervorgehenden Verhaltensweisen unter möglichst ungünstigen Randbedingungen (worst-case Szenarien), als auch die detailierte Charakterisierung unter Normalbedingungen. Die durchgeführten Messreihen wurden zusätzlich durch Simulationen unterstützt, um einzelne Betriebsmodi genauer zu analysieren.<br />Im abschließenden Teil dieser Arbeit werden vorliegende Forschungsergebnisse kurz zusammengefasst. Desweiteren werden Limitierungen des Ansatzes aufgezeigt und mögliche Verbesserungen erwähnt.<br />

In the course of this thesis a novel approach for the on-chip generation of a fault-tolerant clock is developed. At first this is motivated by the fact that with shrinking feature sizes and the accompanying increase of transient failure rates it is more and more desirable to provide VLSI (Very Large Scale Integration) circuits that incorporate mechanisms for fault tolerance. In particular, the conducted research concentrates on the most prominent single point of failure of modern chip design, namely, the clock signal of synchronous circuits. After surveying alternative design approaches and existing schemes for achieving fault tolerance a novel fault-tolerant clocking scheme is introduced.<br />The proposed clock generation method is based on the hardware implementation of a well known distributed clock synchronization algorithm. Most notably, it provides scalable fault tolerance for up to f arbitrary (Byzantine) failures in a system of n >=3f + 2 tick generation nodes. Additionally, the clocking scheme's operation does not rely on the synchronization of clock sources, like quartz oscillators; in fact, the distributed clock signals are generated in a synchronized way. This unique property relieves the design from metastability issues at clock boundaries.<br />The transformation of the original software-based algorithm to the peculiarities of chip design proved to be an intricate task. Therefore, the major part of the work deals with the design and development process of the algorithm's hardware equivalent finally resulting in a fully operational VLSI chip design. To assess the properties of the novel fault-tolerant clocking approach and to show its feasibility exhaustive evaluations have been performed.<br />The presented assessments aim at a thorough characterization of (i) the developed chip design and (ii) the distributed clock generation scheme on which these chips are based. Additionally, the conducted measurements allowed to validate worst-case measures which were derived in advance from the formal analysis of the clocking approach. In order to attain a more comprehensive characterization of the design, the presented worst-case evaluations have been supported by measurements and simulations for typical operating scenarios.<br />The presented work concludes with a short summary and a brief treatment of the most notable topics for ongoing and future research.