作为有史以来发展最为快速的工业之一，半导体工业的进步依赖于不断缩小的特征尺寸以及由此获得的器件性能的快速提高和芯片集成度的指数增长。然而，特征尺寸不断缩小的步伐给集成电路设计带来了新的挑战。正是因为这样，集成电路设计工具及方法学才需要不停的改进，以使得设计者能够解决不停出现的新问题。上世纪之末，集成电路设计是以互连线为中心的，这主要是由于在深亚微米设计中，互连线成为决定电路性能和可靠性的决定性因素。包括串扰噪声、IR-drop以及耦合导致的延迟偏差在内的信号完整性问题变得越来越严重，这很大程度上是因为集成电路内互连线结构变得复杂、电路密度增大导致互连线的寄生效应变得越来越严重。这个世纪之初至今，特征尺寸的不断缩小已经开始接近它的物理极限，工艺参数偏差成为集成电路设计和制造的主要挑战之一。如今，集成电路工艺到达45nm节点，随着亚波长光刻和化学机械抛光等复杂纳米工艺的普遍采用，越来越严重的工艺参数偏差造成了集成电路成品率的快速恶化。成品率问题已成为纳米集成电路设计的致命性瓶颈问题。电路设计和制造将不能再被分离开来，集成电路设计正进入可制造性设计与成品率驱动设计(DFM／DFY)的新时代。对于主宰电路性能的互连线来说，我们不仅需要对其清确的建模以考虑互连线的寄生效应，而且也需要在建模的过程中考虑由于纳米制造工艺造成的互连线几何参数的偏差。为了这一目的，几何参数偏差驱动的互连线寄生参数提取为设计者提供了互连线的准确的偏差模型，是DFM／DFY的一个关键核心技术。许多其他纳米集成电路设计技术，例如统计的静态时序分析，依赖于这一模型来分析工艺参数偏差下互连线电路的时序与性能。几何参数偏差驱动的寄生参数提取的主要难点在于几何参数偏差的随机性以及由此决定的参数提取的随机问题。本论义主要研究几何参数偏差驱动的寄生电容参数提取问题，并提出两个随机配置方法用于求解寄生电容提取的随机问题。作为随机谱方法的一种，随机配置方法对于求解随机偏微分方程具有最优(指数)收敛的特性，这使得随机配置方法对于求解工艺偏差下的随机问题具有很好的应用前景。本文的主要贡献在于：1)基于几何参数偏差满足高斯随机分布的假设，提出一个用于几何参数驱动奇生电容提取的随机配置方法；2)以及对于实测几何参数偏差具有任意随机分布具有最优(指数)收敛特性的广义随机配置方法。相关的工作发表在IEEE DATE国际会议上，该工作首次将随机配置方法应用到寄生参数提取问题，在接下来的一年里，清华大学、加州大学河滨分校以及麻省理工大学都在此文章的基础上提出了各自的随机谱方法。相比于已有的方法，本文提出的随机配置方法(SCM)与广义随机配置方法(gSCM)具有以下的优点：1)相比于已有的寄生电容提取的扰动方法，本文提出的随机配置方法对于求解电容提取的随机问题具有最优(指数)收敛的特性。扰动方法由美国威斯康星大学麦迪逊分校于ICCAD’2005上提出，该方法基于泰勒展开。众所周知，对于较大的偏差，扰动法无法保证解的收敛性。数值结果也清晰的说明二阶扰动方法相比于一阶扰动方法在精度上的提高并不明显，另一方面，一阶随机配置方法(SCM)具有与二阶扰动方法相当的精度。2)扰动方法中使用的主元分析方法包含了对特征值问题的求解，当面元个数较大时，主元分析方法占据了主要的计算时间。本文提出的随机配置方法(SCM)采用K-L展开方法，该方法利用更为有效的数值方法解决了这一瓶颈问题。3)随机配置方法(SCM)和广义随机配置方法(gSCM)分别使用稀疏网格数值积分公式与广义稀疏网格数值积分公式来构造随机空间的配置点。稀疏网格被视为“高维空间的恩赐”，它避免了直接张量积方法中配置点个数随维度呈指数增长的问题、相比于蒙特卡罗方法在计算时间上有数量级的降低。4)随机配置方法的一个优势是它将随机问题转化为配置点上的确定性问题。本文提出了一个基于最小生成树的重用策略，该策略有助于配置点上的初值选取与预条件矩阵的构造，从而更进一步的提高了计算效率。5)需要注意到的是随机配置方法的最优(指数)收敛特性很大程度上取决于随机正交多项式的正交性。基于几何参数满足高斯随机分布的假设，随机配置方法采用Hermite多项式，然而，实测的几何参数偏差并不具有高斯随机分布的特性，这严重的影响了随机配置方法(SCM)最优(指数)收敛的特性。为了达到随机谱方法的指数收敛特性，本文提出了广义随机配置方法(gSCM)用于考虑实测几何参数偏差具有任意随机分布的寄生电容提取。该算法可以以实测的几何参数偏差数据为输入，自动构造相应的广义随机正交多项式与广义稀疏网格。数值实验表明，对于具有任意随机分布的几何参数偏差，广义随机配置方法可以自动获得最优(指数)的收敛特性。