English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware

MPS-Authors
/persons/resource/persons123371

Lenzen,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons228416

Wiederhake,  Ben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:2010.01415.pdf
(Preprint), 447KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Lenzen, C., & Wiederhake, B. (2020). TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware. Retrieved from https://arxiv.org/abs/2010.01415.


Cite as: http://hdl.handle.net/21.11116/0000-0007-904F-E
Abstract
The vast majority of hardware architectures use a carefully timed reference signal to clock their computational logic. However, standard distribution solutions are not fault-tolerant. In this work, we present a simple grid structure as a more reliable clock propagation method and study it by means of simulation experiments. Fault-tolerance is achieved by forwarding clock pulses on arrival of the second of three incoming signals from the previous layer. A key question is how well neighboring grid nodes are synchronized, even without faults. Analyzing the clock skew under typical-case conditions is highly challenging. Because the forwarding mechanism involves taking the median, standard probabilistic tools fail, even when modeling link delays just by unbiased coin flips. Our statistical approach provides substantial evidence that this system performs surprisingly well. Specifically, in an "infinitely wide" grid of height~$H$, the delay at a pre-selected node exhibits a standard deviation of $O(H^{1/4})$ ($\approx 2.7$ link delay uncertainties for $H=2000$) and skew between adjacent nodes of $o(\log \log H)$ ($\approx 0.77$ link delay uncertainties for $H=2000$). We conclude that the proposed system is a very promising clock distribution method. This leads to the open problem of a stochastic explanation of the tight concentration of delays and skews. More generally, we believe that understanding our very simple abstraction of the system is of mathematical interest in its own right.