Statistical static timing analysis (SSTA) involves computation of maximum (max) and minimum (min) of Gaussian random variables. Typically, the max or min of a set of Gaussians is performed iteratively in a pair-wise fashion, wherein the result of each pair-wise max or min operation is approximated to a Gaussian by matching moments of the true result obtained using Clark's approach [1]. The approximation error in the final result is thus a function of the order in which the pair-wise operations are performed.

Variability in digital integrated circuits makes timing verification an extremely challenging task. In this paper, a canonical first-order delay model that takes into account both correlated and independent randomness is proposed. A novel linear-time block-based statistical timing algorithm is employed to propagate timing quantities like arrival times and required arrival times through the timing graph in this canonical form. At the end of the statistical timing, the sensitivity of all timing quantities to each of the sources of variation is available. Excessive sensitivities can then be targeted by manual or automatic optimization methods to improve the robustness of the design. This paper also reports the first incremental statistical timer in the literature, which is suitable for use in the inner loop of physical synthesis or other optimization programs. The third novel contribution of this paper is the computation of local and global criticality probabilities. For a very small cost in computer time, the probability of each edge or node of the timing graph being critical is computed. Numerical results are presented on industrial application-specified integrated circuit (ASIC) chips with over two million logic gates, and statistical timing results are compared to exhaustive corner analysis on a chip design whose hardware showed early mode timing violations