作为有史以来发展最为快速的工业之一,半导体工业的进步依赖于不断缩小的特征尺寸以及由此获得的器件性能的快速提高和芯片集成度的指数增长。然而,随着亚波长光刻和化学机械抛光等复杂纳米工艺的普遍采用,越来越严重的工艺参数偏差造成了集成电路成品率的快速恶化。这主要是由于严重的工艺偏差将造成芯片中的关键路径时延呈现显著的非高斯随机分布,从而造成芯片的时序失败概率快速上升。这些时延的随机分布信息可以通过最先进的统计静态时序分析方法,在芯片生产前精确地获得。但目前还缺乏可以充分利用这些统计信息的电路优化方法和工具,从而造成在芯片设计阶段依然缺乏有效的方法来改善芯片的成品率。成品率问题已成为集成电路工艺向纳米时代迈进中,数字芯片设计的致命性瓶颈问题之一。本博士论文的工作将针对成品率的分析和优化问题展开研究。研究主要包括以下两个方面。第一,提出了一种基于端口移除和稀疏网格的随机配置算法和一种基于随机配置法的自适应算法,实现对统计静态时序分析(SSTA)方法中关键性的求最大值MAX问题的快速求解,并显著地提高了国际上已有SSTA算法的精度和效率。第二,在国际上首次提出一种可以精确考虑非高斯关键路径时延分布的时钟偏斜规划方法,从而实现在设计阶段对芯片成品率的优化。本文在以上两个方面的工作中提出以下算法:1.纳米工艺偏差影响下的统计静态时序分析方法。(1)为求解统计静态时序分析中的关键性的求极大值MAX问题,本文提出一种采用基于稀疏网格的随机配置算法SSCM(Stochastic Sparse-grid CollocationMethod)。与目前国际上MAX求解精度最高的基于降维技术的随机Galerkin方法相比,SSCM解决了其计算精度不稳定的问题。其次,SSCM避免了直接张量积配置方法所导致的配置点个数随随机参数个数的增加而指数增长的问题。与在国际项级会议DAC2005上提出的一种基于矩匹配的算法相比,SSCM有显著的精度提升。结合本文提出的端口移除技术,SSCM的运算时间快于上述的各种作为对照的快速算法,且比10,000次蒙特卡罗算法快最少100倍。(2)在SSCM算法的基础上,本文提出了一种自适应的MAX快速计算方法ASCM(Adaptive Stochastic Collocation Method)。通过对MAX在不同统计输入下的非线性特性的分析和分类,ASCM选择最合适的算法来求解不同非线性程度的MAX,从而可以在算法效率和精度间做最佳权衡。在ISCAS’85基准组合逻辑电路上进行统计静态时序分析的结果显示,ASCM与国际上已有的基于降维技术的随机Galerkin方法和一种基于矩匹配的MAX逼近算法相比,可以获得最大10倍的精度提升,且运算时间近似相同。2.纳米工艺偏差影响下,基于时钟偏斜规划的成品率优化方法(1)在时钟偏斜规划研究领域,本文在国际上首次提出一种可以精确考虑非高斯关键路径时延分布的成品率优化问题的描述方法。基于MIN-MAX形式,本文所提出的成品率优化问题描述涵盖了自上世纪90年代以来,在国际顶级ICCAD和DAC会议上提出的相关领域的大部分已有工作。本文基于所提出的通用描述获得对这些已有方法的统计解释,并从理论上指出它们的局限性。(2)此外,本文提出基于最小平衡法的一种通用算法来有效求解所提出的成品率优化问题。为了提高算法的效率,本文提出一种基于分段线性插值的反累积分布函数的快速数值计算方法。在ISCAS’89基准时序逻辑电路上的测试表明,本文所提出的方法在成品率优化结果上较已有的两种在国际上具有代表性的方法(由德国波恩大学的C.Albrecht和Jens Vygen教授等在ICCAD1999会议上提出的EVEN法,和由美国威斯康星麦迪逊大学的Charlie Chung-Ping Chen教授和Kewal K.Saluja教授等在ICCAD2004会议上提出的PROP法)有最高33.6%,平均17.7%的显著改善。