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

Yi WANG
Xuan ZENG
Jun TAO
Hengliang ZHU
Wei CAI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A    No.12    pp.3465-3473
Publication Date: 2008/12/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.12.3465
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Device and Circuit Modeling and Analysis
Keyword: 
statistical timing analysis,  adaptive stochastic collocation method,  process variations,  

Full Text: PDF>>
Buy this Article


Summary: 
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 10x improvements in the accuracy while using the same order of computation time. The proposed algorithm also shows 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 100x speeds up.