G. Fuchs, U. Schmid, A. Steininger:
"DARTS - Distributed Algorithms for Robust Tick Synchronization";
Report for Research Report 72/2004, Technische Universität Wien, Institut für Technische Informatik, Treitlstraße 3, A-1040 Vienna, Austria;
Clock distribution has evolved as a crucial issue in high end embedded system designs at all levels, from VLSI to system-level. Enormous efforts are being made to distribute the clock signal throughout the complete system with minimum delay and minimum skew. However, as the clock rates continue to increase, it becomes more and more difficult to maintain the illusion of a globally synchronous clock. The DARTS project aims at a distributed clock generation solution in between the synchronous and the globally asynchronous locally synchronous (GALS) approach: As with GALS, the system is partitioned into modules within which the synchronous model can reasonably be applied. The interaction between the modules, however, is based on a relaxed but still synchronous timing model. Similar to distributed systems, a fault-tolerant distributed algorithm is employed for synchronizing - in fact, generating - the modules' local clock signals. In the DARTS approach, however, this algorithm is implemented in hardware and hence provides a substantially better precision (a few periods of the local synchronous clock). Every module is equipped with a hardware tick synchronization unit, which interact with each other in order to generate the clock signals - no external quartz oscillator is necessary here. Among the benefits of the DARTS approach are its scalable fault tolerance and its adaptability with respect to delay variations in the gates and the clock distribution net: The clock always runs as fast as the conditions allow. As a generic solution, our approach can be employed in a wide variety of applications, ranging from VLSI chips over printed circuit board-based embedded systems up to system-level products. Given the ambition and the risk of failure of fully developing and evaluating the DARTS approach, we will pursue a two-step approach here: An exploration project (this proposal) devoted to the proof of concept, and a (separate) subsequent evaluation project where our approach shall be applied and evaluated in some cutting-edge Systems-on-a-Chip. The exploration project will start from some of our recent theoretical results in the area of fault-tolerant distributed algorithms (partially obtained in the context of the FIT-IT Embedded Systems Dissertationsstipendium DCBA, proj. no. 808198). Its tangible output will be an implementation of a suitable tick generation algorithm in a custom VLSI chip, and a demonstrator system comprising a set of modules on a PCB, each equipped with our tick synchronization unit. The latter serves as a proof of concept and will allow us to assess some key properties of our solution. Among the main research challenges in the project are the development of an algorithm that can efficiently be implemented in hardware, and the actual implementation of the tick synchronization unit VLSI chip, which must be based on asynchronous design paradigms.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.