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

Yi Wang1,  Xuan Zeng1,  Wei Cai2,  Hengliang Zhu1,  Xu Luo1
1State Key Lab. of ASIC & System, Microelectronics Dept., Fudan University, 2Depart. of Mathematics, University of North Carolina at Charlotte


In this paper, we propose an Adaptive Stochastic Collocation Method for block-based Statistical Static Timing Analysis (SSTA). The delays of gates and interconnects are modeled by a quadratic form of Polynomial Chaos expansion in order to capture the nonlinear affects of process variations. Based on this quadratic delay model, a novel adaptive method is proposed to perform SSTA in the presence of process variations. In order to approximate the key atomic operator MAX during timing analysis, the proposed method adaptively chooses the optimal algorithm from a set of stochastic collocation based algorithms by considering different input conditions. Compared to the 10,000 Monte Carlo simulations on ISCAS85 benchmark circuits, our results show less than 1% error in the mean and variance, and nearly 100x speed up. Compared to the other stochastic collocation methods, the proposed method has 10x improvement in the accuracy while using the same order of computation time.