基于随机配置法和输入端缩减技术的统计静态时序分析

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

在考虑工艺偏差影响的统计静态时序分析中,针对求解多个随机分布最大值(MAX)的关键问题,提出一种快速MAX算法.该算法将统计输入下的MAX问题转换为求解一组离散配置点上的确定性MAX问题,并用带权最小二乘来计算MAX输出多项式的系数;基于稀疏网格技术有效地减少配置点数,提出输入端缩减技术,进一步提高了MAX的计算效率.ISCAS85基准电路的实验结果表明,该算法较已有的二阶矩匹配算法和基于降维的随机Galerkin算法明显地提高了精度,且效率相当;与10 000次蒙特卡罗的结果相比,中值和方差的相对误差基本小于5%,且有100倍的速度提升.

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.