[Back]

M. Perner:
"Fault-Tolerant Clock Distribution in Grid-Like Networks";
Supervisor, Reviewer: U. Schmid, A. Jantsch, M. Krstic; Institut für Computer Engineering (E191-02), 2019; oral examination: 2019-10-16.

This thesis investigates how to design a system to distribute and use a clock signal in a grid-like network, as employed in, e.g., SoCs and NoCs.
Ideally, the clock is generated by multiple components and has self-stabilization and fault-tolerance properties, i.e., recovers from transient faults even under permanent faults. These clock generation components can be distributed over the whole chip to provide a clock signal for every part of the chip. This, however, comes at a price: The increase in wire length between the components increases the skew between the generating components, and hence the clock skew at the clock boundaries between the components. Furthermore, such clock generation systems are expensive in terms of chip area, and usually require a fully-connected topology. Hence, putting the clock generating components in close proximity is favorable. However, just generating such a clock somewhere in a chip is not enough: After all, the clock signal needs to be distributed to all components that need it.
The challenge for clock distribution is to not diminish or even remove the self-stabilization and fault-tolerance properties of the generated clock during distribution. To this end, we present a clock distribution system, HEX, that allows recovery from transient faults under permanent faults.
Since HEX, which is based on a hexagonal grid, shows a large spread in the node-to-node skew under faults, we explored alternative interconnection topologies. Under the assumption that a suitable clock generation is able to provide a skew bounded by the difference in the wire delay between its components, the TRIX topology has been identified as the best trade-off between performance and implementation efficiency. For TRIX, a transistor cell model of the clock distribution node has been constructed as well.
Given that the distributed clock propagates like a wave through the grid, it provides a synchronization source for the nodes of the grid already. However, the achievable degree of synchrony is not enough to be able to utilize the synchronous design paradigm for communication between the nodes of the grid. We show that high-speed communication is nevertheless feasible in such multi-synchronous GALS architectures,
however, by using a FIFO buffer for mitigating the clock skew and thus allowing data transmission in every clock cycle. Using a special buffer management approach, our communication scheme can be guaranteed to be self-stabilizing when the underlying clocking system is. Hence, our communication scheme is fully compatible with, but not limited to, HEX and TRIX.

Diese Arbeit beschäftigt sich mit der Frage, wie man ein Taktsignal in gird-artigen Netzwerken -wie sie in SoCs und NoCs verwendet werden- auf einem Chip verteilen und nutzen kann.
Idealerweise wird dieses Taktsignal von mehreren Komponenten im Verbund erzeugt und besitzt dadurch sowohl selbst-stabilisierende als auch fehlertolerante Eigenschaften. Das bedeutet, dass sich die Komponenten von transienten Fehlern erholen können, selbst wenn einige Komponenten permanent fehlerhaft sind.
Die Komponenten des Verbunds können dabei über den ganzen Chip verteilt sein. Da das erzeugte Taktsignal zu jeder Funktionseinheit des Chips gebracht werden muss, ist dies vorteilhaft. Allerdings hat diese Verteilung auch Nachteile: Durch die langen Leitungen zwischen den Komponenten vergrößert sich der zeitliche Versatz des erzeugten Taktsignals. Dies führt in weiterer Folge zu einem zeitlichen Versatz zwischen benachbarten Funktionseinheiten des Chips, wenn diese von verschiedenen Komponenten ihr Taktsignal beziehen. Da die Komponenten üblicherweise auch vollständig untereinander verbunden sein müssen, benötigten sie viel Fläche am Chip. All das spricht dafür, die Komponenten des Verbundes nahe beieinander zu platzieren. Allerdings müssen die Taktsignale weiterhin allen Funktionseinheiten des Chips zugänglich gemacht werden.
Die Herausforderung bei der Taktverteilung ist es, die selbst-stabilisierenden und fehlertoleranten Eigenschaften des erzeugten Taktes aufrecht zu erhalten. Dazu stellen wir das Taktverteilungssystem HEX vor, welches an den Knoten des Grids Zellen hat, über die nahegelegene Funktionseinheiten mit einem Taktsignal versorgt werden. HEX ist in der Lage, sich von transienten Fehlern selbst unter bestehenden permanenten Fehlern zu erholen. Da HEX, welches auf einem hexagonalen Raster basiert, jedoch im Fehlerfall einen hohen zeitlichen Versatz zwischen seinen Knotenzellen aufweisen kann, werden alternative Verbindungstopologien untersucht. Unter der Annahme, dass der Takterzeugungsverbund einen Takt mit einem maximalen zeitlichen Versatz in der Größenordnung der Signallaufzeiten zwischen seinen Komponenten erzeugen kann, wurde die TRIX Topologie ausgewählt. TRIX ist ein Optimum zwischen der Qualität der Taktverteilung und des Flächenbedarfs am Chip. Für TRIX wurde auch ein Transistormodell der Knotenzelle entwickelt.
Da sich ein so verteiltes Taktsignal wie eine Welle durch das Grid ausbreitet, stellt es auch eine Synchronisationsquelle für die Knotenzellen dar. Jedoch ist der erreichbare Grad der Synchronisierung nicht ausreichend, um das synchrone Design-Paradigma für die Kommunikation zwischen den Funktionseinheiten, die von benachbarten Knotenzellen versorgt werden, zu ermöglichen. In dieser Arbeit wird gezeigt, dass dennoch schnelle Kommunikation in derartigen multi-synchronen GALS-Architekturen möglich ist. Dabei wird ein FIFO-Puffer verwendet, um den zeitlichen Versatz zu kompensieren und dadurch Datentransfers mit jeder Taktflanke zu ermöglichen. Durch die Verwendung einer speziellen Pufferverwaltung ist das Verfahren garantiert selbst-stabilisierend, wenn die Takterzeugung und -verteilung dies auch sind. Unser Kommunikationsschema ist daher voll kompatible mit HEX und TRIX, aber natürlich nicht nur darauf beschränkt.

Multi-synchronous GALS, Clock distribution, Metastability-free communication, Byzantine fault-tolerance, Self-stabilization

https://publik.tuwien.ac.at/files/publik_285692.pdf