Distributed Algorithms for Robust Tick Synchronization

01.10.2005 - 31.03.2010

Research funding project

DARTS is a joint venture of Austrian Aerospace and the Institute of Computer Engineering (Embedded Computing Systems Group) at the Vienna University of Technology with the aim to develop solutions for emerging challenges in clock distribution. Clock distribution has evolved as a crucial issue in high end embedded system designs at all abstraction levels, from VLSI to board-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 for a distributed clock generation solution situated 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 this algorithm is implemented in hardware and hence provides substantially higher precision (a few periods of the local synchronous clock). Every module is equipped with a hardware tick synchronization unit, which interacts with every other module 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 to printed circuit board-based embedded systems. The starting point of the DARTS project is 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). 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 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. Furthermore, an appropriate technique for interfacing common synchronous designs will be developed.

People

Institute

E182 - Institute of Computer Engineering

Grant funds

FFG - Österr. Forschungsförderungs- gesellschaft mbH (National) Austrian Research Promotion Agency (FFG)

Research focus

Computer Engineering: 100%

Keywords

German	English
eingebettete Systeme	embedded systems
Taktgenerierung	clock generation
verteilte Algorithmen	distributed algorithms
Fehlertoleranz	fault tolerance

External partner

Austrian Aerospace

Publications

Publications