Path-Based Statistical Timing Analysis Handling Arbitrary Delay Correlations: Theory and Implementation

An efficient path-based statistical timing analysis algorithm that can handle arbitrary causes of delay correlations is proposed in this paper. The algorithm derives bounds for the cumulative distribution function (cdf) of the circuit delay using a new mathematical formulation based on the theory of stochastic majorization. Structural and interchip correlations between path delays can be taken into account. Because the analytical computation of an exact cdf for a probabilistic timing graph is infeasible, tight upper and lower bounds on the true cumulative distribution are derived. The efficiency and accuracy of the algorithm is demonstrated on a set of ISCAS´85 benchmarks. Across the benchmarks, the error of the 95th-percentile delay is 1.1%-3.3%, and the root-mean-square error of the cumulative probability is 1.7%-4.5%. The run time of the proposed algorithm for the largest benchmark circuit takes less than 4 s