General Terms

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 pairwise operations are performed. In this paper, we analyze known “run-time expensive ” ordering techniques that attempt to reduce this error in the context of SSTA and SSTA driven optimization. We propose new techniques to speeding up the computation of the max/min of a set of Gaussians by special handling of prevalent “zero error ” cases. Two new methods are presented using these techniques that provide more than 60 % run-time savings (3X speed-up) in max/min operations. This translates to an overall run-time improvement of 2-17 % for a single SSTA run and an improvement of up to 8 hours (55%) in an SSTA driven optimization run