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

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

作　　者：王毅[1] 曾璇[1] 陶俊[1] 朱恒亮[1] 罗旭[1] 严昌浩[1] 蔡伟 

机构地区：[1]复旦大学专用集成电路与系统国家重点实验室,上海201203 [2]Department of Mathematics, University of North Carolina at Charlotte, Charlotte, NC 28223 0001 USA

出　　处：《计算机辅助设计与图形学学报》2008年第12期1527-1534,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金重点项目(90307017);国家自然科学基金(60676018,60806031);国家“九七三”重点基础研究发展规划项目(2005CB321701);教育部跨世纪优秀人才培养计划基金;教育部高等学校博士学科点专项科研基金(20050246082);US National Science Foundation grants(CCF-0727791)

摘　　要：在考虑工艺偏差影响的统计静态时序分析中,针对求解多个随机分布最大值(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.

关 键 词：统计静态时序分析 随机配置法 稀疏网格 输入端缩减 工艺参数偏差 

分 类 号：TN47[电子电信—微电子学与固体电子学]