A Probabilistic Model for Clock Skew

Abstract:

A probabilistic model for the accumulation of clock skew in synchronous systems is presented. Using this model, we derive upper bounds for expected skew, and its variance, in tree distribution systems with N synchronously clocked processing elements. We apply these results to two specific models for clock
distribution. In the first, which we call metric-free, the skew in a buffer stage is Gaussian with a variance independent of wire length. In this case the upper bound on skew grows as theta(log N) for a system with N processing elements. The second, metric, model, is intended to reflect VLSI constraints: the clock skew in a stage is Gaussian with a variance proportional to wire length, and the distribution tree is an H-tree embedded in the plane. In this case the upper bound on expected skew is theta(sqrt N log N) for a system with
N processors. Thus the probabilistic model is more optimistic than the deterministic summation model of Fisher and Kung, which predicts a clock skew
theta(N) in this case, and is also consistent with their lower bound of omega
(sqrt n) for planar embeddings. We have estimates of the constants of proportionality, as well as the asymptotic behavior, and we have verified the accuracy of our estimates by simulation.