Stochastic Collocation Method for Statistical Static Timing Analysis with Input Truncation Technique

A novel stochastic collocation method with sparse grid and input truncation technique is proposed to perform statistical static timing analysis considering process variations.The proposed method first transforms the key operator MAX with statistical inputs into a set of deterministic MAX problems on a set of collocation points generated with sparse grid,and then solves the unknown coefficients with weighted least square technique.A novel input truncation technique is proposed to further reduce the computational time.Experimental results show that the algorithm achieved obvious improvements on accuracy compared with an existing moment matching based method and a stochastic Galerkin method with dimension reduction technique while kept the same order of efficiency.In comparison with 10 000 Monte Carlo simulation results,the proposed method achieved relative errors of mean and variance mostly below 5%,with nearly 100X speeds up.