Adaptive Stochastic Collocation Method (ASCM) for Parameterized Statistical Timing Analysis with Quadratic Delay Model

In this paper, we propose an adaptive stochastic collocation method for block-based statistical static timing analysis (SSTA). A novel adaptive method is proposed to perform SSTA with delays of gates and interconnects modeled by quadratic polynomials based on homogeneous chaos expansion. In order to approximate the key atomic operator MAX in the full random space during timing analysis, the proposed method adaptively chooses the optimal algorithm from a set of stochastic collocation methods by considering different input conditions. Compared with the existing stochastic collocation methods, including the one using dimension reduction technique and the one using sparse grid technique, the proposed method has 10times improvements in the accuracy while using the same order of computation time. The proposed algorithm also show great improvement in accuracy compared with a moment matching method. Compared with the 10,000 Monte Carlo simulations on ISCAS85 benchmark circuits, the results of the proposed method show less than 1% error in the mean and variance, and nearly 100times speeds up.