36/2011 : Reconciling fault-tolerant distributed computing and systems-on-chip

RR Number

36/2011

Conference

Distributed Computing 24(6):323-355, 2012

Author(s)

Matthias Fuegger, Ulrich Schmid

Abstract

Classic distributed computing abstractions do not match well the reality of digital logic gates, which are the elementary building blocks of Systems-on-Chip (SoCs) and other Very Large Scale Integrated (VLSI) circuits: Massively concurrent, continuous computations undermine the concept of sequential processes executing sequences of atomic zero-time computing steps, and very limited computational resources at gate-level make even simple operations prohibitively costly. In this paper, we introduce a modeling and analysis framework based on continuous computations and zero-bit message channels, and employ this framework for the correctness & performance analysis of a distributed fault-tolerant clocking approach for Systems-on-Chip (SoCs). Starting out from a “classic” distributed Byzantine fault-tolerant tick generation algorithm, we show how to adapt it for direct implementation in clockless digital logic, and rigorously prove its correctness and derive analytic expressions for worst case performance metrics like synchronization precision and clock frequency. Rather than on absolute delay values, both the algorithm’s correctness and the achievable synchronization precision depend solely on the ratio of certain path delays. Since these ratios can be mapped directly to placement & routing constraints, there is typically no need for changing the algorithm when migrating to a faster implementation technology and/or when using a slightly different layout in an SoC.

Bibtex

@article{FS12:DC,
year={2012},
issn={0178-2770},
journal={Distributed Computing},
volume={24},
issue={6},
doi={10.1007/s00446-011-0151-7},
title={Reconciling fault-tolerant distributed computing and systems-on-chip},
url={http://www.springer.com/alert/urltracking.do?id=L4fc2b9M93e09eSaf96e87},
publisher={Springer-Verlag},
keywords={Clock synchronization; Fault-tolerant distributed systems; Modeling approaches; VLSI},
author={Függer, Matthias and Schmid, Ulrich},
pages={323-355},
language={English}
}

Download