一种大规模电阻网络端到端等效电阻的快速计算方法

　　[0001]大规模电阻网络端到端等效电阻的计算方法是EDA工具在芯片设计过程中的一种对驱动端到负载端之间的等效电阻进行快速计算的方法。本发明属于EDA领域。

　　【背景技术】

　　[0002]目前，超大规模集成电路的发展，使得互连线的寄生效应对电路性能的影响日趋明显，在检查电路性能时，从驱动端管脚到负载端管脚之间的等效电阻，成为衡量芯片电学性能是否达标的一项重要参数。

　　[0003]要计算管脚间的等效电阻，首先需要对版图中管脚所在的线网进行电阻提取，建立一个电阻网络，每个管脚在网络中均表示为一个节点。考虑图1所示的一个电阻网络，我们要计算管脚A和管脚B之间的等效电阻，可在A和B上分别添加一个大小为IA而方向相反的电流源，然后计算得到A和B之间的电压差，根据欧姆定律，A和B之间的等效电阻为:

　　RAB=VA-VB(I)

　　其中，VA和VB分别是节点A和B上的电压值。对图1中的每个节点，它和周围相邻节点间存在电流路径，结合欧姆定律和基尔霍夫定律，对节点A-F可依次列出如下方程:

　　(VF- VA)/RAF+(VB- VA)/RAB=-1(VC- VB)/RBC+(VA- VB)/RAB=-1(VD- VC)/RCD+(VE- VC)/RCE+(VB- VC)/RBC =-0

　　(VF- VD)/RFD+(VE- VD)/RED+(VC- VD)/RCD =-0(2)

　　(VC- VE)/RCE+(VD- VE)/RDE+(VF- VE)/RFE =-0(VA- VF)/RAF+(VD- VF)/RDF+(VE- VF)/REF =-0如果令所有R均等于1，以上方程组可化约为如下矩阵形式:

　　(-2，I, O, O, O, IVA-1

　　I,-2，I, O, O, OVBI

　　O,I, -3，I, I, O X (VC)=( O )⑶

　　O,O, I, -3，I, IVDO

　　0,O, I, I, -3，IVEO

　　1,O, O, I, I, -3)VFO

　　其中，左端系数矩阵为导纳矩阵A，右端向量是节点电流向量IAB，均为已知项。求解此方程，可得到节点电压向量UAB，在获得节点A和B的电压值VA和VB后，根据式(I)，即可计算得到节点A和B间的等效电阻。

　　[0004]从数学上可以证明，矩阵A是一个奇异矩阵，这意味着式(3)不可解。因此我们无法通过直接求解式(3)来获得节点电压向量UAB，而是必须选择一个不同于A和B的任意节点，赋予其一个固定电压，然后重新改写式(3).例如，如果我们令节点F的电压VF为零，则式(3)可改写为如下形式:

　　(-2，I, O, O, OVA-1 I,-2，I, O, OVBI

　　O, I, -3，I, I X (VC)=( O )⑷

　　O, O, I, -3，IVDO

　　0.0, I, I, -3)VEO

　　式⑷中，左端系数矩阵记为A’，右端向量是节点A-E对应的节点电流向量I’AB，从数学上可以证明，矩阵A’是非奇异，式(4)可以求解并获得唯一解U’ AB。然后根据式(I)就可以得到A和B间的等效电阻。

　　[0005]存在多种方法可用来求解式(4)，例如GMRES算法、CG算法、LU分解等，为了使用以下的加速方法，我们采用了 LU分解的算法来求解方程，其基本过程如下:

　　1.对矩阵A’做LU分解，求得其逆矩阵B’；

　　2.U’ΑΒ=Β’*1’AB(5) 以上是计算管脚间电阻的基本算法，在整个过程中，占计算时间主要部分的是对矩阵

　　A’做LU分解求逆的过程。由于全线网导纳矩阵A奇异，无法直接求解，必须随机选择一个节点并指定其电压，然后对一个不完全导纳矩阵A’求逆。这样，当需要求解多对管脚之间的等效电阻时，不完全导纳矩阵A’会随着管脚的变化而改变，必须再次进行LU分解。

　　[0006]在实际中，由于超大规模的芯片往往有上万甚至更多的管脚，可能形成的管脚对可达上百万甚至更多，如果计算每一对管脚的等效电阻都需要进行一次LU分解，所需时间远远超出了整个设计周期可接受的范围。因此需要找到一种能够在合理时间内计算得到所有管脚对的等效电阻的快速方法。

　　【发明内容】

　　[0007]通过分析以上求解过程，可以发现影响计算性能的一个重要因素是，全线网导纳矩阵A奇异，无法直接进行LU分解，因此必须随机选择一个节点并指定其电压。这样，对于不同的管脚对，其待求解矩阵也不相同，必须再次进行LU分解，导致整体运行时间居高不下。

　　[0008]矩阵A的奇异可以由数学理论推导得出，理论上，当矩阵A中的每个元素均对应两节点间精确的导纳值时，该矩阵必然奇异。但是在实际应用中，由于以下一些原因，在电脑中所存储的导纳矩阵A，必然和理论值存在偏差:

　　1.矩阵A中的每一项数值都是实数，在电脑中以浮点数格式存储，而浮点数格式并不能精确表示每一个实数，它采用有效数字+指数的方式来存储实数，必然带来误差；

　　2.矩阵A中的每一项数值，都需要在电脑中经过若干次的四则运算得到。在四则运算过程中，临时的计算结果会储存在精度更高的寄存器上，当计算结束后，将结果写入为浮点格式时，必然存在截断或舍入误差。

　　[0009]这意味着，我们在电脑中存储并用来计算的矩阵，和理论上的导纳矩阵A，在数值上是存在偏差的。也就是说，电脑中实际存储的矩阵，并不是理论上的矩阵A，因此它有可能是非奇异的。

　　[0010]经过数千个测例的验证，我们发现，所有这些理论上奇异的矩阵确实都具有非奇异性，可以成功进行LU分解，并求得其逆矩阵。这样，我们可以直接求解式(3)，得到节点电压向量，从而得到节点间等效电阻值。基本过程如下: 1.对矩阵A做LU分解，求得其逆矩阵B；

　　2.UAB = B^IAB(6)

　　线网中的管脚数和待求解的管脚对数量有如下关系:

　　M=[N*(N-1)]/2(7)

　　其中，N是管脚数量，M是待求解的管脚对数量。可以看到，当管脚数增加时，待求解的管脚对数量会迅速上升。即使仅需对全线网导纳矩阵求一次逆，但对每对管脚，都需要按式

　　(6)执行一次矩阵向量乘:，其计算时间累积起来也相当可观。

　　[0011]由于我们是基于全导纳矩阵进行计算，所有节点电流向量都和一个相同的矩阵做矩阵向量乘。考虑节点电流向量IAB:1AB=(…iA...1B...) = (...1A...0...)+ (…O …iB…)(8)

　　式(8)中，节点电流向量IAB被拆为两个向量IA和IA，每个向量中仅含一个非零值，因此，式(6)可以改为如下形式:

　　UAB = B*IA + B* IB(9)

　　这里我们可以看到，方程右端由两部分组成，第一部分所包含的节点电流向量IA仅仅在节点A的位置包含一个非零值，第二部分所包含的节点电流向量IB仅在节点B的位置包含一个非零值。以此类推，对于N个管脚，我们可构造N个节点电流向量，每个向量仅在对应节点的位置含一个非零值，然后分别与矩阵B相乘，得到如下结果:

　　UA=B*IA...........(10)

　　UB=B^IB

　　对任意指定的两个管脚A和B，我们从式(10)中取出对应的UA和UB，然后可得到节点电压向量

　　U A B = U A + U B(11)

　　这样，仅需要进行N次矩阵向量乘，就可以组合得到任意两个管脚间的节点电压向量，进而可根据式(I)计算这两个管脚间的等效电阻值，这大大降低了总体计算时间。

　　【附图说明】

　　[0012]图1:版图中线网电阻网络的一个示例具体实施步骤

　　结合一个具体的实例说明大规模端到端等效电阻的计算方法，具体的操作步骤如下:

　　1)准备一份OpenAccess格式的版图数据、工艺文件，以及记录版图与工艺文件中的金属层匹配关系的map文件；

　　2)对版图中的指定线网做电阻提取，获得一个电阻网络；

　　3)列出全线网导纳矩阵；使用LU分解求其逆矩阵；

　　4)如果导纳矩阵奇异，则退出当前过程，改由传统方式计算管脚间电阻；

　　5)针对每一个待计算管脚，找到它在电阻网络中对应的节点，建立一个电流向量，在这个电流向量中，这个待计算管脚节点对应的项为1，其余项为O ; 6)将每一个管脚对应的电流向量分别和导纳逆矩阵做矩阵向量乘，得到管脚对应的电压向量；

　　7)对每一组需要计算等效电阻的管脚对，将它们分别对应的电压向量相加，从结果中取出两个管脚分别对应的电压值，计算电压差，得到管脚间等效电阻；

　　步骤5、6、7可以反复执行，直到所有待求管脚对之间的等效电阻均被计算得到。

　　【主权项】

　　1.一种大规模电阻网络端到端等效电阻计算的快速方法，涉及到EDA设计工具的主要特征为: (1)针对芯片线网做电阻提取，列出全线网导纳矩阵并存储于电脑中； (2)全线网导纳矩阵在电脑中存储并使用时会有不可避免的浮点数误差； (3)浮点数误差会导致电脑中存储并使用的矩阵与理论上的全线网导纳矩阵存在偏差，具有非奇异性； (4)对全线网导纳矩阵求逆，并依次与不同的节点电流向量相乘，可得到不同的端到端间等效电阻值。

　　2.要求保护具有特征(I)、(2)、(3)、(4)的组合。

　　【专利摘要】本发明涉及一种大规模电阻网络端到端等效电阻的快速计算方法。目前，超大规模集成电路的发展，使得互连线的寄生效应对电路性能的影响日趋明显，在检查电路性能时，从驱动端管脚到负载端管脚之间的等效电阻，成为一项衡量芯片电学性能是否达标的重要参数。但由于超大规模芯片中的电源网络往往有上万甚至更多的管脚，要一一计算它们之间的等效电阻，所需时间远远超出了整个设计周期可接受的范围。本文提出了一种复用LU分解(LUDecomposeReuse)的方法，利用计算机在存储浮点数时不可避免的浮点数误差，可对全线网导纳矩阵做LU分解，并将其应用于所有的管脚间等效电阻计算中，极大的提高了管脚间等效电阻的计算效率。

　　更多电阻网络内容，请访问RS PRO。