基于随机行走电容提取的保证准确度的线网时延计算方法

摘要

本发明公开了一种基于随机行走电容提取的保证准确度的线网时延计算方法，包括以下步骤：计算单输入单输出的互连线网或者一输入多输出的互连线网中互连时延随机误差与电容随机误差的关系；根据用户指定的随机行走电容提取精度进行随机行走电容的提取；根据提取的随机行走电容值构造RC等效电路，并根据互连线网中互连时延随机误差与电容随机误差的关系式计算互连时延随机误差，若不满足用户预设的互连时延随机误差阈值的要求，则再次根据设置的随机行走电容提取精度执行提取过程与后续的时延计算，通过若干次迭代，直到满足用户预设的互连时延随机误差阈值的要求。本发明在确保时延误差可控的同时使包含电容提取的总计算时间最短。

说明书

技术领域

本发明涉及集成电路技术领域，尤其涉及一种基于随机行走电容提取的保证准确 度的线网时延计算方法。

背景技术

随着集成电路制造工艺的发展，其特征尺寸逐渐减小、集成度逐渐增高。在目前已 普遍采用的纳米级制造工艺(特征尺寸在65纳米以下)中，单个芯片集成的晶体管已经达到 十亿个。由此引发的问题是，互连线时延占电路时延的比例日益增大。因此，在集成电路物 理设计与验证中，准确、快速的实现寄生参数提取(计算互连线的寄生电阻、电容)，同时进 行准确的互连时延分析，成为保证芯片良率、缩短设计周期的关键步骤。

寄生参数提取方法一般使用模式匹配法和场求解器方法。模式匹配法虽然计算速 度快，但是在纳米级工艺下，由于互连结构复杂度与设计准确度要求的提高，它常常无法满 足要求。而通过数值求解三维静电场方程的方法(也称“场求解器”)具有非常高的准确度， 因此近年来再次受到关注。基于随机行走的场求解器电容提取方法适用于规模大、复杂度 高的互连结构，并具有易于并行、准确度高、灵活性好等特点，已被用于一些关键线网、甚至 整个电路的寄生电容提取问题。

不同于其他基于有限差分、有限元或边界元的方法，随机行走方法不需要求解线 性方程组，其原理主要是通过马尔可夫随机过程与蒙特卡洛方法计算电容值。因此，随机行 走电容提取方法的误差主要是随机统计误差，而且利用统计学原理可以控制提取过程在满 足误差阈值后自动结束。这种准确度可控的特点也是随机行走电容提取方法的独特优势之 一，它使得用户可以根据需要获得最佳的计算时间与准确度的折衷。

由于随机行走电容提取的结果具有统计随机性，这种随机性将被带入后续的互连 时延计算中。因此，如何自动控制互连时延计算的随机误差成为一个亟待解决的问题。

发明内容

本发明的目的，在于自动控制互连时延计算的随机误差，提供一种保证准确度的 自适应互连时延计算方法，对随机行走电容提取过程进行自适应调整，在保证时延准确度 的前提下使整体计算时间最短。

本发明为达上述目的所采用的技术方案是：

提供一种基于随机行走电容提取的保证准确度的线网时延计算方法，包括以下步 骤：

计算单输入单输出的互连线网或者一输入多输出的互连线网中互连时延随机误 差与电容随机误差的关系，得到关系式其中p_τ为互连时延随机误差，p为电容 提取的误差阈值，r₁为所求时延路径上第一个导体块的电阻，r_n是所求时延路径上所有导体 块的电阻和，r_n-1是所求时延路径上除了最后一个导体块的所有导体块的电阻和，n为整数；

根据预设的经验值或者用户指定的随机行走电容提取精度进行随机行走电容的 提取；

根据提取的随机行走电容值构造RC等效电路，并根据互连线网中互连时延随机误 差与电容随机误差的关系式计算互连时延随机误差p_τ，若p_τ不满足用户预设的互连时延随 机误差阈值p_usert的要求，则再次根据设置的随机行走电容提取精度执行提取过程与后续的 时延计算，通过若干次迭代，直到满足用户预设的互连时延随机误差阈值p_usert的要求。

本发明所述的方法中，当采用误差上限估计进行自适应时延计算时，所述用户指 定的随机行走电容提取精度小于p_usert，在再次执行提取过程中以的 精度进行随机行走电容的提取。

本发明所述的方法中，所述预设的经验值在0-1之间。

本发明所述的方法中，当采用误差微调进行自适应时延计算时，所述用户指定的 随机行走电容提取精度等于p_usert，再次执行提取过程中以p＝0.9p_usert的精度进行随机行 走电容的提取。

本发明所述的方法中，所构造的RC等效电路采用SPICE电路网表文件描述。

本发明所述的方法中，采用Elmore时延模型计算互连时延随机误差p_τ，并调用 RWCap进行不同精度的电容提取。

本发明还提供了一种基于随机行走电容提取的保证准确度的线网时延计算系统， 包括：

关系式计算模块，用于计算单输入单输出的互连线网或者一输入多输出的互连线 网中互连时延随机误差与电容随机误差的关系，得到关系式其中p_τ为互连 时延随机误差，p为电容提取的误差，r₁为所求时延路径上第一个导体块的电阻，r_n是所求时 延路径上所有导体块的电阻和，r_n-1是所求时延路径上除了最后一个导体块的所有导体块 的电阻和，n为整数；

随机行走电容的提取模块，用于根据用户指定的随机行走电容提取精度进行随机 行走电容的提取；

RC等效电路构造模块，用于根据提取的随机行走电容值构造RC等效电路；

迭代模块，用于根据互连线网中互连时延随机误差与电容随机误差的关系式计算 互连时延随机误差p_τ，若p_τ不满足用户预设的互连时延随机误差阈值p_usert的要求，则再次 根据设置的随机行走电容提取精度执行提取过程与后续的时延计算，通过若干次迭代，直 到满足用户预设的互连时延随机误差阈值p_usert的要求。

本发明产生的有益效果是：本发明从随机统计原理出发，考虑基于随机行走电容 提取的多端线网时延计算，根据用户指定的时延误差阈值，对随机行走电容提取过程进行 自适应调整，并且通过“断点续算”提取技术，在保证时延准确度的前提下使整体计算时间 最短。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明实施例基于随机行走电容提取的保证准确度的线网时延计算方法流 程图；

图2a是本发明实施例单输入单输出等效RC电路；

图2b是本发明实施例一输入多输出的等效RC电路；

图3a是本发明实施例采用误差上限估计的自适应时延计算流程图；

图3b是本发明实施例采用误差微调的自适应时延计算流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对 本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不 用于限定本发明。

如图1所示，本发明实施例基于随机行走电容提取的保证准确度的线网时延计算 方法，包括以下步骤：

S1、计算单输入单输出的互连线网或者一输入多输出的互连线网中互连时延随机 误差与电容随机误差的关系，得到关系式其中p_τ为互连时延随机误差，p为电 容提取的误差阈值，r₁为所求时延路径上第一个导体块的电阻，r_n是所求时延路径上所有导 体块的电阻和，r_n-1是所求时延路径上除了最后一个导体块的所有导体块的电阻和，n为整 数；

S2、根据预设的经验值或者用户指定的随机行走电容提取精度进行随机行走电容 的提取；本发明的一个实施例中，这个预设的经验值是采用误差上限估计时，为了得到RC等 效电路，在第一次进行随机行走的时候，指定的一个经验值，其可以为0-1之间的任何数，如 0.05，采用该经验值可能只需进行这一次随机行走，就能满足要求。

S3、根据提取的随机行走电容值构造RC等效电路；根据互连线网中互连时延随机 误差与电容随机误差的关系式计算互连时延随机误差p_τ；

S4、若p_τ不满足用户预设的互连时延随机误差阈值p_usert的要求，则再次根据设置 的随机行走电容提取精度执行提取过程与后续的时延计算，通过若干次迭代，直到满足用 户预设的互连时延随机误差阈值p_usert的要求。

步骤S1中推导互连时延随机误差与电容随机误差的关系具体为：

1)单输入单输出的互连线网

设c为随机行走电容提取得出的该线网总电容，σ为其随机误差，p为电容提取的误 差阈值，则有σ＝cp，又因为线网总电容等于组成它的各导体块的电容和，所以有其中c_bi为该线网中导体块i的电容，n为导体块数目。设第i块导体电容对应的随机误差为 σ_bi，则由于随机行走路径的独立性，有${\sigma }^2=\underset{i=1}{\overset{i=n}{\Sigma }}{\sigma }_{bi}^2.$

单输入单输出线网的等效RC电路如图2a所示，图中的每一个电阻对应一个导体 块，每一个电阻的两端节点都有一个对地电容。这个对地电容由该节点两侧导体块的电容 共同贡献，即$\begin{array}{ccc}{c}_i=\frac{1}{2}(c_{bi}+c_{b(i+1)}),& i=1,2,...,n-1,& c_n=\frac{1}{2}{c}_{b,n}\end{array}.$

根据Elmore模型基于电容的公式，从V_in到V_out端的延迟时间为可设 同时将上面的式子代入，则可得$\tau =\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{rc}}_i=\frac{1}{2}\underset{i=1}{\overset{n}{\Sigma }}(r_{i-1}+r_i)c_{bi}.$

由于电阻值为确定值，根据随机变量的误差传递得时延τ的随机误差σ_τ满足 根据上面的式子可得互连时延的随机相对误差p_τ满足(这里设r0＝0) 因为序列{ri}是单调递增的，可得到不等式$p_{\tau }^2\le \frac{{(r_{n-1}+r_n)}^2\underset{i=1}{\overset{n}{\Sigma }}{\sigma }_{bi}^2}{r_1^2{\left(\underset{i=1}{\overset{n}{\Sigma }}{c}_{bi}\right)}^2}=\frac{{(r_{n-1}+r_n)}^2}{r_1^2}·p^2,$即 $p_{\tau }\le \frac{r_{n-1}+r_n}{r_1}·p.$

上式反映了时延误差上限与随机行走电容提取误差的关系。

2)一输入多输出的互连线网

对于一输入多输出的线网，假定需要计算的是从端口N₁到端口N_m+1的时延，可用图 2b表示该线网的等效RC电路，其中从N₁到N_m+1路径的中间节点可能延伸出到其他输出端的 路径。假设从N₁到N_m+1路径上导体块对节点N_i的电容贡献为c_i-1，而从节点N_i(1<i<m+1)延伸 出去路径上导体块对节点N_i的电容贡献为c_(i-1),s。

由Elmore时延计算模型知，从V_in到V_out端的延迟时间为设根据导体块连接关系，得展开并重新组合得 由于导体块电容值的随机独立性，时延τ的随机误差σ_τ满足 因为{ri}是单调递增的，可知互连时延的随机相对误差p_τ满足 因为成立，所以p_τ可放大为即其中r₁＝R₁，是所求时 延路径上第一个导体块的电阻，r_m是所求时延路径上所有导体块的电阻和，r_m-1是所求时 延路径上除了最后一个导体块的所有导体块的电阻和。

单输入单输出线网是一输入多输出线网的特殊情况，根据上面的推导结果可以看 出单输入单输出与一输入多输出的时延误差与随机行走电容的提取的结果误差关系是一 样的。

自适应时延计算的基本思想是，首先按某个随机误差阈值来进行随机行走电容提 取，然后计算时延及其随机误差，如果不满足用户指定的随机误差阈值，则需要以更高的准 确度要求再次执行电容提取过程以及后续的时延计算，通过若干次这样的迭代，直到满足 时延误差阈值要求。当再次进行随机行走电容提取时，其精度要求必然比前一次电容提取 的精度要求高，即需要执行更多的随机行走路径。本文提出一种“断点续算”提取技术，它利 用前一次随机行走的结果，节省后续随机行走电容提取的时间。“断点续算”的原理是，在前 一次随机行走电容提取完成后，将其执行的随机行走路径数N_walk、这N_walk次的电容估计值的 和、及其平方和可直接存在内存中(或硬盘文件中)，当再次对同一个例子进行随机行走电 容提取时，读取上述数据即相当于执行了N_walk次随机行走，然后再按更高精度要求执行更 多的随机行走，这样可大大节省电容提取时间。

为了保证时延计算的随机误差满足用户要求，本发明实施例提出如下两种计算流 程。

1)采用误差上限估计的自适应时延计算流程

如图3a所示，设p_usert为用户指定的时延随机误差阈值，p为随机行走电容提取结果 的精度阈值，p_τ为实际计算时延结果的随机误差。根据上面推导的依赖关系，无论是单输入 单输出还是一输入多输出线网，只需要令即可满足p_τ≤p_usert，所以，设置 来进行随机行走电容提取，就能保证用户对时延的精度要求。

因为p＝g(p_usert)的计算与线网导体块的电阻值有关，所以需要先构造线网的RC 等效电路才能得到这些电阻值。在实际操作中，可以先以较低的准确度执行随机行走电容 提取，然后利用得到的电容值构造RC等效电路，然后再根据公式计算满足用户要求所需的 随机行走电容提取误差阈值，再次执行提取过程与后续的时延计算。

2)采用误差微调的自适应时延计算流程

如图3b所示，根据公式推导可知道，根据随机行走电容提取的结果，是可以求出线 网的时延值及其相应的随机误差p_τ。通过对较多测试用例进行实验后发现，当设置p＝p_usert进行随机行走电容提取，其最终导致的时延随机误差p_τ大多数情况即可满足p_usert的阈值要 求。对于少数不满足的情况，可以再将随机行走电容提取的误差阈值调小，利用“断点续算” 电容提取技术再次进行电容提取和后续时延计算，如此反复直到时延误差满足用户指定阈 值。具体地，电容提取误差阈值的缩小比例设为0.9。

为实现上述实施例的方法，本发明还提供了一种基于随机行走电容提取的保证准 确度的线网时延计算系统，包括：

关系式计算模块，用于计算单输入单输出的互连线网或者一输入多输出的互连线 网中互连时延随机误差与电容随机误差的关系，得到关系式其中p_τ为互连 时延随机误差，p为电容提取的误差阈值，r₁为所求时延路径上第一个导体块的电阻，r_n是所 求时延路径上所有导体块的电阻和，r_n-1是所求时延路径上除了最后一个导体块的所有导 体块的电阻和，n为整数；

随机行走电容的提取模块，用于根据用户指定的随机行走电容提取精度进行随机 行走电容的提取；

RC等效电路构造模块，用于根据提取的随机行走电容值构造RC等效电路；

迭代模块，用于根据互连线网中互连时延随机误差与电容随机误差的关系式计 算互连时延随机误差p_τ，若p_τ不满足用户预设的互连时延随机误差阈值p_usert的要求，则再 次根据设置的随机行走电容提取精度执行提取过程与后续的时延计算，通过若干次迭代， 直到满足用户预设的互连时延随机误差阈值p_usert的要求。

本发明实施例所选用的例子都是来自实际的集成电路设计，根据原始的GDSII版 图数据可以得到互连线的三维结构描述。然后，使用RWCap程序执行随机行走电容提取，经 过对互连三维结构的几何处理也得到线网中导体块的连接关系，形成RC等效电路。其中，电 阻的计算基于电阻率与解析公式的方法，RC等效电路用SPICE电路网表文件描述。本发明采 用C语言实现了提出的自适应线网时延计算方法，它采用Elmore时延模型，并调用RWCap进 行不同精度的电容提取。

本实验运行环境是IntelXeonE5-26306核双CPU的UbuntuLinux工作站，主频 2.00GHz，内存32GB。

首先，将程序算出的时延值与商业软件HSPICE计算的结果进行比较。HSPICE对电 路进行瞬态分析，假设线网输入信号为阶跃信号，上升时间t_r＝100ps，幅度V_DD＝5V，在输入 电压上升到50％的V_DD(即2.5V)时触发计时器，在输出电压也达到50％的V_DD时停止计时器， 根据HSPICE中的.measure语句计算时延值。

然后对两种保证时延准确度的自适应计算流程进行比较。通过对来自实际电路设 计的多端互连线网进行实验，可以发现采用误差微调方案比采用误差上限估计方案的自适 应时延计算方法所耗时间更少、效率更高。

综上，本发明通过基于误差上限估计和基于误差微调的2种自适应互连时延计算 策略，根据用户指定的时延误差阈值自动调整执行随机行走电容提取的精度设置与次数， 并通过“断点续算”提取技术缩短整体计算时间。在确保时延误差可控的同时使包含电容提 取的总计算时间最短。

应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换， 而所有这些改进和变换都应属于本发明所附权利要求的保护范围。