VLSI多层供电网络中优化配置垂直通孔的启发式方法

摘要

VLSI多层供电网络中优化配置垂直通孔的启发式方法属于VLSI物理设计领域，其特性在于：它以灵敏度信息作为指导，采用循环累加的方式实现了多层供电网络中垂直通孔的优化配置，与供电网络线宽优化方法类似，该方法也可以很好地改善供电网络的性能；方法中还采用了扩展的特勒根伴随网络技术以及基于不完全乔莱斯基分解的预优共轭梯度技术，使得方法的效率得到了很大的提高。实验结果证明该方法可以快速高效地完成大规模供电网络中通孔的优化配置，与平均分配通孔的方法相比，可以更有效地减少供电网络中电压降，提高芯片的稳定性。

说明书

技术领域

VLSI多层供电网络中优化配置垂直通孔的启发式方法属于VLSI物理设计领域，尤其属于布局布线领域中的供电网络优化设计技术范畴。作为特殊线网布线的一部分，供电网络设计在布局布线阶段具有极其重要的地位。

背景技术

1.供电网络设计的重要性

在芯片物理设计中，供电网络的布线属于特殊线网布线部分。不适当的供电网络设计会引起一系列的严重问题，如半导体器件得不到足够的供电电压所引起的逻辑错误、供电网络中某一支路的电流密度过大所引起的供电网络的损坏等，这些都会极大地影响电路的性能，甚至使电路失效，芯片无法正常工作。因此在布线阶段，供电网络的布线具有最高优先级。

随着集成电路的制造工艺由目前的深亚微米(DSM)进入到超深亚微米(VDSM)，集成电路的设计规模也由超大规模(VLSI)，甚大规模(ULSI)向极大规模(GSI)发展，供电网络的规模与复杂度也在逐渐增大，对原有的设计方法提出了挑战。更重要的是，由于芯片功耗急剧增加及芯片供电电压不断降低，使得供电网络必须提供越来越大的工作电流；与此同时，随着芯片工作频率的急剧提高，使得寄生电容、电感对供电网络影响的日益增大。所有这一切使得芯片的安全供电问题成为芯片设计制造过程中最主要的棘手问题之一，也是制约芯片性能和规模继续提高的主要瓶颈之一。最近对深亚微米集成电路设计的调查表明，79％的设计具有电源网络的问题，需要在流片之前矫正，否则芯片将由于电源网络上的电压降过大而不能正常工作。因此供电网络设计问题受到了学术和工业界的空前重视。

2.供电网络中的IR电压降

设计不当的供电网络可能引起的严重问题之一就是供电网络上过大的供电电压波动。10％的供电电压波动就会导致大于10％的时延不确定性，从而引起逻辑错误、导致芯片失效。可能引发过大电压波动的因素有很多，包括工作电流过大带来的IR电压降、高频率下寄生电感带来的噪声等。 

在当前的频率下，IR电压降依然是可能引发过大电压波动的主要因素。IR电压降主要由片上供电网络的电阻导致。当供电网络中有很大的电流，就会引发过大的电压降，从而影响电路的性能并会导致功耗提高。

IR电压降又分为两类：静态IR电压降和动态IR电压降。静态IR电压降指的是在平均功耗和平均电流的基础上得到的电源和地之间的电压降，可以通过调整供电网络的线宽来消除；而动态IR电压降则考虑了电路模块工作时一个时钟周期内的电流波形和电源与地之间的去耦合电容，动态IR电压降问题可以通过调整线宽和放置去耦合电容两种方式来消除，去耦合电容可以使用NMOS栅氧化层电容来有效的获得。

如前所述，消除IR电压降的最基本的方法之一便是调整供电网络的线宽。但是如果没有很好的规划和设计，调整线宽会使供电网络占用过多的布线面积资源，导致后继的信号线布线阶段的布线拥挤问题。因此，如何调整线宽来占用最少的布线资源以消除供电网络中过大的IR电压降便是一个数学优化问题。

总体来讲，线宽优化可以根据拓扑结构的不同分为两类：一类是针对树形拓扑结构的供电网络，由于树形结构的特殊性，可以证明这是一个凸规划问题，可以采用拉格朗日乘子法进行优化；另一类是带回路的一般图结构，尤其是工业界中普遍使用的网状供电网络，这类结构的优化问题的求解要困难的多，原因在于这种结构中含有回路，各分枝上电流的方向不确定，并且求解之前各个分支的电流都是未知量，因此此时所有约束都是非线性的，成为一个非线性约束优化问题，求解这类问题一般要采用复杂得多的数学规划方法或者启发式方法求解，目前提出的较成熟的方法有Tan-Shi算法、PECT算法等。

然而，有一个很重要的问题是，在含有大量垂直通孔的多层供电网络中，只通过优化线宽并不能起到最好的效果。事实上，随着特征尺寸的减少，垂直通孔的电阻对供电网络IR电压降的影响已经到了不可忽略的地步。

3.多层供电网络中的垂直通孔

随着集成电路的规模不断增加，芯片上的线网也越来越密集，因此现在一般都必须采用多层线网才能实现芯片上各个模块之间的互联，并且多层线网的层数也呈逐渐上升的势态。在多层线网中，为了实现不同层之间金属线的互连，垂直通孔(Via)便是不可或缺的重要组成部分。

近些年来有关垂直通孔的研究日益引起人们重视的原因在于，随着特征尺寸的减少，金属线网的电阻在不断增大，而其中增长速度最快的就是垂直通孔。在特征尺寸为90纳米的芯片中，一个垂直通孔的电阻值可以相当于100微米的金属线。垂直通孔的电阻值在整个多层线网占据的比重越来越大，这对芯片设计的各个阶段都提出了新的挑战。

特别地，这一现象对多层供电网络的设计具有尤其重要的影响。附图1中显示的是一种应用广泛的供电网络结构。在网络中，同一层的金属线都是相互平行，而相邻层的金属线相互垂直，一般情况下，高层的金属线具有较大的宽度(width)同时相邻金属线间的间距(pitch)也相对较大。在这种多层的供电网络中，自然需要通孔来实现不同层间金属线的互连。如附图1所示，为了不占用额外的布线资源，对信号线的布线造成影响，通孔一般都设置在相邻层间金属线的交叉点(intersection)上。

垂直通孔电阻值的增加必然也会带来供电网络上电压降的增大。解决这一问题的基本方法就是增加垂直通孔的数目，如附图1所示，在有些金属线交叉点处就放置了多个通孔。当然，放置太多的垂直通孔也会造成制造成本的增加，并且受几何尺寸等因素影响，在各个交叉点处可以放置的通孔个数也有最大值限制。

这样，随之而来的一个问题就是如何更好地在交叉点处配置通孔的数目。最简单的方法自然是在同一层的交叉点处分配相同数目的通孔，但是很显然，对大多数电路来讲这种方法并不是一个最佳的方法。与线宽优化类似，优化配置通孔的问题也可以抽象为一个有约束的数学优化问题。但是由于各个交叉点处只能配置整数个通孔，该问题是一个离散的数学优化问题，因此，直接用数学规划的方法求解将非常困难。到目前为止，尚没有提出一种成熟的方法解决这个问题。

发明内容

针对目前尚没有一种能对多层供电网络中的垂直通孔进行优化配置以降低网络中电压波动的方法的现状，本发明提出了一种快速高效的优化配置垂直通孔的启发式方法。

其特征在于：该方法是一种以灵敏度信息作为指导，采用循环累加的方式实现多层供电网络中垂直通孔的优化配置的启发式方法，优化的目标是更加合理地配置各个金属线交叉点处垂直通孔的数目，以消除多层供电网络最底层节点中电压降超过规定最大允许值的违规节点，减少最底层节点的最大电压降。该方法是在计算机中依次按以下步骤实现的：

步骤1)读入数据

计算机读入和分析用户提供的几何拓扑信息文件和电学参数信息文件，构造由电导、独立电压源、独立电流源构成的电路网络，其构建过程如下：

相邻层金属线之间的交叉点被抽象成对应金属线上的节点，按顺序编号，这些节点将每一条金属线都分割成了许多小段；

根据几何信息和电学参数信息计算出每一小段金属线的电导值，每个通孔也会对应于电路网络中的一个电导，把位于同一金属线交叉点处的通孔对应的并联电导合并，合并后每一个交叉点只对应于一个电导；

将芯片上连接于供电网络最底层节点的电路模块看作固定值的独立电流源，电流值取做该电流模块在最坏情况下的工作电流；

步骤2)初始化

每个交叉点处只配置一个通孔，接下来从步骤3)到步骤8)将采用循环累加的方式，在每一个循环中都会挑选固定数目个交叉点，在交叉点上增加通孔的个数，如此反复循环，直到供电网络满足电压降的要求、各个交叉点处通孔个数达到最大或者再增加的通孔并不能对电压降的起到很好的改善效果为止；

步骤3)电路模拟分析

步骤3.1)根据节点分析法构建供电网络对应的线性方程组：

                                 GV＝I

其中：G是电导系数矩阵，具有稀疏、对称正定的优良特性，V是电路节点电压向量，I是支路电流向量；

步骤3.2)按以下步骤采用基于不完全乔莱斯基分解的预优共轭梯度方法求解线性方程组GV＝I，得到供电网络：

步骤3.2.1)对电导系数矩阵G进行不完全乔莱斯基分解，得到预优矩阵；

步骤3.2.2)采用共轭梯度法，以循环迭代的方式求得满足近似精度的近似解，得到供电网络各个节点的电压值；

步骤4)检查供电网络最底层的违规点个数

如果违规点的个数为0，循环结束，转步骤9)，否则继续执行下一步；

步骤5)计算违规点的平均电压降

除了第一次循环外，将计算出的平均电压降与上一次循环的违规点平均电压降进行比较，如果平均电压降下降的幅值小于设定的阈值，循环结束，转步骤9)，否则继续执行下一步；

步骤6)电路灵敏度分析，其步骤如下：

步骤6.1)构建扩展特勒根伴随网络，伴随网络与原供电网络几何拓扑结构相同，电导值也相同，但独立电压源设置为短路，独立电流源设置为开路，并且在每个违规点上连接固定大小为1安培的对地吸纳电流源；

步骤6.2)按步骤3)中所述方法对扩展特勒根伴随网络进行模拟分析，得到伴随网络中各个节点的节点电压值；

步骤6.3)根据原网络及伴随网络中对应节点的节点电压值可以得到：

$S=\underset{i\in \mathrm{VIO}}{\Sigma }(V_i-V_{\min })$

$\frac{\partial S}{\partial {\mathrm{vn}}_{a,b}}=\mathrm{vg}(V_a-V_b)(V_a^{\prime }-V_b^{\prime })$

其中：S是方法中定义的目标函数，反映底层所有违规点的电压降情况

vn_a，b是两条金属线的交叉点(a，b)处的垂直通孔数目，S/vn_a，b是两条金属线的交叉点(a，b)处垂直通孔数目相对于目标函数的灵敏度，反映(a，b)处通孔数目的变化对于最低层违规点节点电压降的影响，V_min是底层节点允许的最小电压值，电压值小于它的节点便是违规点，VIO是最底层供电网络中所有违规点的集合，V_i是原供电网络中第i号违规节点的电压值，vg是每一个通孔所对应的电导值，不同层的通孔对应的vg值不同，V_a、V_b分别是原供电网络中交叉点(a，b)两端点的电压值，V_a’、V_b’分别是伴随网络中交叉点(a，b)两端点的电压值；

步骤7)增加通孔

从通孔数尚未达到最大值的交叉点中挑选出N个灵敏度最大的交叉点，将挑选出的每个交叉点处的通孔个数增加1；

步骤8)检查各个交叉点处的通孔个数

如果各个交叉点处通孔数目都已经达到上限，循环结束，转步骤9)，否则开始执行下一循环，转步骤3)；

步骤9)循环结束

输出结果。

实验证明，和平均分配通孔的方法相比，该方法可以更好地改善电路性能，提高供电网络的稳定性。此外，扩展特勒根伴随网络技术以及基于不完全乔莱斯基分解的预优共轭梯度技术的使用极大地提高了方法的效率，使得该方法可以应用于超大规模的供电网络。

附图4便是本方法的具体实现流程。

附图说明

图1：网状多层供电网络示意图，M4——第4层金属线，M3——第3层金属线，

     M2——第2层金属线，M1——第1层金属线，Via——垂直通孔

图2：经过电学参数提取后的供电网络示意图；

图3：不完全乔莱斯基分解的过程示意图；

图4：本发明的具体实现流程图；

具体实施方式

本方法已经使用C++语言在UNIX环境下开发并实现。实现的程序以读入各层供电网络的几何拓扑信息、电学参数信息为开始，最终给出优化配置之后各个交叉点处通孔个数。

下面介绍程序的工作流程：

1.构建电路网络。

通过分析用户提供的信息文件，包括各层供电网络的几何拓扑信息和电学参数信息，最终将构建如附图2所示的由电导、独立电压源、独立电流源构成的电路网络。需要说明的是，在程序中我们考虑的只是如附图1展示的多层网状供电网络，但我们的方法经过适当改动也可以适用树状或者其他拓扑类型的供电网络；另外，由于电源线网络与地线网络在结构上完全相似，因此，在程序中我们只考虑了供电网络中的电源线网络部分。

具体的构建过程如下：相邻层金属线的交叉点都被抽象成对应金属线上的节点(node)，节点按顺序编号，这样，每一条金属线都被节点分割成许多小段(segment)，接下来可以根据几何信息和金属线的方块电阻计算出每一小段金属线的电导值，电路网络中每一小段金属线都会对应一个电导元件；类似的，每个通孔也会对应于电路网络中的一个电导；将芯片上连接于供电网络最底层节点的电路模块看作固定值的独立电流源，电流值取做该模块在最坏情况下的工作电流。

特别地，由于位于同一交叉点上的通孔在经过提取之后将对应于相互并联的电导，因此在我们的方法中进行了简化，将位于同一交叉点处的对应于通孔的电导进行了合并，合并后每一个交叉点只对应于一个电导，电导值等于单个通孔的电导值乘以该交叉点处的通孔个数。

2.初始化

在程序运行的最初阶段，每个交叉点处都只分配一个通孔，之后将采用循环累加的方式，在每一个循环中都会挑选固定数目(N)个交叉点，在交叉点上增加通孔的个数，如此反复循环，直到设计出的供电网络满足电压降的要求、各个交叉点处通孔个数达到最大或者增加的通孔并不能对电压降的起到很好的改善效果为止。

接下来的第3步到第8步便是循环的具体过程。

3.电路模拟分析。

对供电网络进行模拟分析的最基本的方法就是节点分析法。对于只含有电压源、电流源以及电导的电路采用这种方法可以得到如下的线性方程组：

                                     GV＝I

其中V是待求的节点电压向量；G是电导系数矩阵；I是支路电流向量。求解出该线性方程组即可得到供电网络中各个节点的电压值。

由于上面的线性方程组维数等于供电网络中的节点数目，可能会达到十万乃至几十万，因此直接采用高斯消元法求解将十分耗时。但是由于电导系数矩阵G具有稀疏、对称正定等一系列优良的性质，因此我们采用了基于不完全乔莱斯基分解的预优共轭梯度算法。

3.1基于不完全乔莱斯基分解的预优共轭梯度算法

基于不完全乔莱斯基分解的预优共轭梯度算法是一种应用十分广泛的间接求解线性方程组的算法，对于系数矩阵为对称正定的稀疏矩阵的线性方程组，该算法具有速度快，稳定性高的特点。

以线性方程组的标准型Ax＝b为例。如果系数矩阵A是一个对称正定的矩阵，就可以借助于泛函的变分原理将线性方程组求解问题转化为一个求解泛函极值的问题：设A是阶对称正定矩阵，b是已知向量，x是方程组解的充分必要条件为满足：

           (x^*)＝min((x))x∈Rⁿ；

其中其中(，)符号为内积符号；

该原理称为Ritz原理，是共轭梯度法及其演化算法的基础。由上面的变分原理可知，计算(x)极小的算法也就给出了求解原方程组的算法，而求得(x)极小的关键当然是如何使(x)的值下降。

首先考虑经典的最速下降法，设x₀是Rⁿ中任意一点，则(x)在该点下降最快的方向是该点的负梯度方向

经计算可知， 其中r₀称为残差向量

令x₁＝x₀+αr₀    (4.1)

其中α待定，由于(x)沿r₀方向是下降的，于是有(x₁)＜(x₀)为了使下降的效果最佳，自然要使：

这样求得的α可以使x₁沿r₀方向下降最多，而上式的解为${\alpha }_1=\frac{(r_0,r_0)}{({\mathrm{Ar}}_0,r_0)}$如果在(4.1)式中取α＝α₁，就得到一步最速下降法，一般地有

x_k＝x_k-1+α_kr_k-1        k＝1，2，L

其中r_k-1＝b-Ax_k-1，  α_k＝(r_k-1，r_k-1)/(Ar_k-1，r_k-1)

由于A是对称正定的，所以它的所有特征值都是正数，设为λ₁≥λ₂≥L≥λ_n＞0定义${\left|\right|x\left|\right|}_A={(x,\mathrm{Ax})}^{\frac{1}{2}}$为一种向量范数，则最速下降法的收敛性有如下的结果

${\left|\right|x_k-x^{*}\left|\right|}_A\le {\left(\frac{{\lambda }_1-{\lambda }_n}{{\lambda }_1+{\lambda }_n}\right)}^k{\left|\right|x_0-x^{*}\left|\right|}_A$

其中x^*是方程组的精确解，x₀为初始点

应该注意的是虽然r_k是(x)在x_k处的最速下降方向，但这是局部的，要尽快达到(x)的极小值，这样的选择不一定是最优的，另一方面，由于计算中的舍入误差会影响实际下降方向偏离最速下降方向，所以计算的时候具有一定的不稳定性。

共轭梯度的方法则主要针对最速下降法的这几个缺点进行了改进，其主要思想是在(x)的极小化过程中，下降应该具有整体最优的特点。

如果在Rⁿ中能够取到p₁，p₂L p_k是线性无关的，并且能够使xk满足

                  (x_k)＝min((x))  x∈S_k       (4.2)

其中S_k＝span{p₁，p₂L p_k}，即由p₁，p₂L p_k张成的线性空间，则k＝n时就给出了原方程组的解。当k＝1时，只要取p₁＝r₀＝b-Ax₀就可以满足(4.2)式的要求

假设有p₁，p₂L p_k-1(k≥2)使得

$x_{k-1}=\underset{i=1}{\overset{k-1}{\Sigma }}{\alpha }_i{p}_i$且满足   (x_k)＝min((x))x∈S_k

共轭梯度法取x_k＝x_k-1+α_kp_k，只要能选择p_k，使得下面的式子成立(称p_k和p₁，p₂L p_k-1关于A共轭)就能满足(2)式：

(p_i，Ap_k)＝0   i＝1，2Λ k-1

而满足上式的非0向量可以被构造出来：

            p_k＝r_k-1+β_kp_k-1${\beta }_k=\frac{(p_{k-1},{\mathrm{Ar}}_{k-1})}{(p_{k-1},{\mathrm{Ap}}_{k-1})}$

这样通过反复迭代，序列{x_k}将会收敛到原方程组的解。

从理论上讲，共轭梯度法是一种直接求解线性方程组的方法，由方法的构造过程可见，若A是n阶矩阵，则x_n应当是方程组的精确解，但是由于实际计算中舍入误差的影响，p₁，p₂L p_k不可能严格保持A共轭的特性，甚至当k大到一定程度后，p₁，p₂L p_k可能变得几乎线性相关，所以共轭梯度法更多的作为迭代法使用。

由于A是对称正定的，设它的特征值为λ₁≥λ₂≥L≥λ_n＞0，用共轭梯度法给出的向量序列将满足以下估计：

${\left|\right|x_k-x^{*}\left|\right|}_A\le {\left(\frac{\sqrt{{\lambda }_1}-\sqrt{{\lambda }_n}}{\sqrt{{\lambda }_1}+\sqrt{{\lambda }_n}}\right)}^k{\left|\right|x_0-x^{*}\left|\right|}_A$

共轭梯度法作为一种快速收敛的迭代法其优点是可以充分利用系数矩阵的系数性，计算步骤简明，易于并行计算，但是在系数矩阵的特征值出现非均匀分布的情况时，收敛的速度将收到影响。对于经典的共轭梯度法，其收敛的快慢依赖于系数矩阵的谱分布情况，当系数矩阵的条件数很小或特征值分布很集中时它可以用很少几步得到高精度的近似解。而如果系数矩阵的特征值非常不均匀地分布在一个很长的区间上时，共轭梯度法的收敛速度就会变得很慢。为了克服这一个缺点，使之在分析差异很大电路方程的系数矩阵时能够给出比较平稳的求解速度，必须要考虑对电路方程的系数矩阵进行预处理。如果A是对称正定的，那它就一定存在乔莱斯基分解，但如果A还是大型稀疏的，则分解很可能会完全破坏A的稀疏性，而不完全乔莱斯基分解就是将A分解成：

                           A＝LL^T+R

其中L是一个上三角矩阵，R称为剩余矩阵，由于这里R是可以变化的，所以L的稀疏性就可以的到保证，从而克服乔莱斯基分解破坏矩阵稀疏性的问题。可以令预优矩阵M＝LU，U和L有关系U＝DLT，其中D是由A的对角元素组成的矩阵。当剩余矩阵R选得合适时，预优矩阵可以具有和系数矩阵A相同的稀疏性并且和A相近。理论上可以证明，M和A越相近，预优共轭梯度法收敛得越快。我们使用类似于高斯消元的方法来获得系数矩阵的不完全乔莱斯基分解和预优矩阵。

不完全乔莱斯基分解的过程如附图3所示，设系数矩阵A已经被分解到第i步，则此时元素aii成为主元。采用“高斯消元法”使a_ii所在列上的其它元素消为零。然而，这个“高斯消元法”是不完全的，这是因为：既然我们的目的是求得一个上(下)三角矩阵U(L)，那么下(上)三角矩阵的元素可以不加入消元过程。考虑第k列的情况，只有当a_ik和a_jk(i＜j＜k)都不为零时，高斯消元才会发生，在其它情况下a_ik和a_jk都不变。系数矩阵A的稀疏性保证了不完全的乔莱斯基分解的运算量很小。

4.查找供电网络最低层的违规点。

所谓违规点是指供电网络最底层中电压降超过最大允许值的节点。由于程序中只考虑电源线网络，因此电压降超过供电电压(Vdd)5％的节点都会被认为是违规点。即设定供电网络底层允许的最小节点电压(V_min)为95％Vdd，底层节点中电压值小于V_min的就是违规点。

如果违规点的个数为0，说明当前的供电网络已经可以满足最大电压降的需求，循环结束，转第9步；否则继续执行下一步。

5.计算违规点的平均电压降。

除了第一次循环外，将计算出的平均电压降与上一次循环的违规点平均电压降进行比较，如果平均电压降的数值降低并不明显，表明最近增添的通孔已经不能对平均电压降起到很好的改善作用，循环结束，转第8步；否则继续执行下一步。

6.电路灵敏度分析。

在我们的方法中，采用了灵敏度作为指导信息确定增加通孔的最佳位置，因此，电路的灵敏度分析是整个优化过程的核心步骤。为了能快速高效地完成对电路的灵敏度分析，结合优化问题的特点，我们采用扩展的特勒根伴随网络技术。

6.1灵敏度

所谓灵敏度是指元件参数的变化对网络特性的影响程度。最简单的灵敏度的定义是可微分的网络函数对元件参数的导数：

                  灵敏度＝T/h_i  (i＝1，2，...，n)

这个定义反映了函数T随元件参数h_i的变化而变化的趋势和速率。

在我们的方法中，目标函数S被设定为：

$S=\underset{i\in \mathrm{VIO}}{\Sigma }(V_i-V_{\min })$

其中，VIO指的是电路中所有违规点的集合，V_i指的是第i号节点的电压值。根据定义可以看出S小于等于0，并且S会随着违规点的减少、违规点电压值的增大而增大。而我们优化的目标便是使它的值在可行的范围内达到最大。

由于伴随着网络中通孔数目的增加，整个供电网络都在发生变化，因此，在每一次循环中，我们都需要都求出S相对于任何一个交叉点处添加通孔的灵敏度：

$\frac{\partial S}{\partial {\mathrm{vn}}_{a,b}}(a,b)\in M$

其中M指的是交叉点集合，(a，b)指的是位于节点a和b之间的交叉点，节点a和b应当分别位于相邻层的两条金属线上；vn_a，b指的是位于交叉点(a，b)处的通孔的数目。更进一步，可以得到：

$\frac{\partial S}{\partial {\mathrm{vn}}_{a,b}}=\frac{\partial S}{\partial g_{a,b}}\frac{\partial g_{a,b}}{\partial {\mathrm{vn}}_{a,b}}=\mathrm{vg}\frac{\partial S}{\partial g_{a,b}}(a,b)\in M---\left(5.1\right)$

其中g_a，b指的是位于节点a和b之间的交叉点处的通孔电导值的并联值，它与交叉点处的通孔个数是线性相关的关系，二者的比值是每一个通孔的电导值vg。需要说明的是，位于不同层的通孔的电导值并不相同，并且相差很大，因此，求解不同层交叉点处增加通孔的灵敏度时需要使用不同vg值。

从目标函数的定义可以得到，

$\frac{\partial S}{\partial g_{a,b}}=\underset{i\in \mathrm{VIO}}{\Sigma }\frac{{\partial V}_i}{\partial g_{a,b}}(a,b)\in M---\left(5.2\right)$

根据(5.1)式和(5.2)式可以看出，求解交叉点处增加通孔的灵敏度问题被转化为求解V_i/g_a，b的基本电学问题。

6.2特勒根伴随网络技术

可以采用特勒根伴随网络法求解节点a和b之间的电导相对于节点i的电压值的灵敏度，即(5.2)式中的V_i/g_a，b，它是一种求解灵敏度的基本方法。具体实现过程如下：

a)构造特勒根伴随网络N’(i)，N’(i)和原网络具有相同的拓扑结构，各分枝的电导值也相同，不同之处在于N’(i)中除了节点i的吸纳电流设为1A以外，其他节点的吸纳电流都设为0，另外，所有的输入电压都设为0。

b)对N’(i)进行模拟分析，构建节点电压方程组，同样采用第2步中介绍的节点分析法，既然伴随网络和原网络具有相同的拓扑结构和电导值，它们可以共用同一个系数矩阵G，二者对应的线性方程组的区别在于右端向量：N’(i)的右端向量的元素除了和节点i对应的元素为-1以外，所有元素均设置为0，即：

                  I(i)＝[0，0，Λ，0，-1，0，Λ，0]^T

其中-1出现在下标i上。

c)求解伴随网络N’(i)对应的节点电压方程组，在这里也可以采用第2步中介绍的基于不完全乔莱斯基分解的预优共轭梯度技术，并且由于原网络和伴随网络的系数矩阵G相同，所以在这里不需要重复构建预优矩阵。模拟分析后得到伴随网络中分枝(a，b)两端的电压V_a’(i)和V_b’(i)。根据电路灵敏度分析理论，节点电压V_i关于电导g_a，b的偏导数可以用下式表示：

$\frac{\partial V_i}{\partial g_{a,b}}=(V_a-V_b)\times (V_a^{\prime }\left(i\right)-V_b^{\prime }\left(i\right))---\left(5.3\right)$

依照上面的方法，对构建出的伴随网络N’(i)进行模拟分析之后便可方便地求得所有交叉点处的并联电导值相对于节点i的电压值的偏导数。

6.3扩展的特勒根伴随网络技术

直接应用特勒根伴随网络方法的问题在于，为了求解出所有交叉点的灵敏度，需要构建与违规点相同数目的伴随网络进行模拟求解，这将是十分耗时的。因此，我们采用了改进的扩展特勒根伴随网络方法，将所有的伴随网络合并为一个整体，这样只需求解一次即可。下面是该方法的推导过程：

假设V’(i)是N’(i)的节点电压向量，它可通过求解节点电压方程组得到。即，

GV′(i)＝I(i)  (5.4)

其中，V_a′(i)和V_b′(i)是V′(i)的两个元素，设C_a＝[0，0，Λ，0，1，0，Λ，0]，1出现在下标a上；C_b＝[0，0，Λ，0，1，0，Λ，0]，1出现在下标b上；则V_a′(i)和V_b′(i)可分别表示为如下形式，

          V_a′(i)＝C_aV′(i)，V_b′(i)＝C_bV′(i)

而根据(5.2)式和(5.3)式可以推导出，

$\frac{\partial S}{\partial g_{a,b}}=\underset{i\in \mathrm{VIO}}{\Sigma }\frac{\partial V_i}{\partial g_{a,b}}=(V_a-V_b)\underset{i\in \mathrm{VIO}}{\Sigma }(V_a^{\prime }\left(i\right)-V_b^{\prime }\left(i\right))=(V_a-V_b)(C_a-C_b)\underset{i\in \mathrm{VIO}}{\Sigma }{V}^{\prime }\left(i\right)---\left(5.5\right)$

结合(5.4)式可以看出，上式中的可通过求解下列线性方程组得到，

$G\underset{i\in \mathrm{VIO}}{\Sigma }{V}^{\prime }\left(i\right)=\underset{i\in \mathrm{VIO}}{\Sigma }I\left(i\right)$

进一步可以设定，

$V^{\prime }=\underset{i\in \mathrm{VIO}}{\Sigma }{V}^{\prime }\left(i\right)$$I^{\prime }=\underset{i\in \mathrm{VIO}}{\Sigma }I\left(i\right)---\left(5.6\right)$

其中I’中的元素只可能为-1或0，VIO集合中的节点对应的下标处为-1，否则为0。

因此，可以认为V’和I’分别为如下的扩展特勒根伴随网络的节点电压向量和节点电流向量：该伴随网络与原网络同样具有相同的拓扑结构，原网络的所有的独立电压源都设为短路，所有的独立电流源都设为开路，最后在所有的底层违规点处增加固定大小为1A的吸纳电流源。

而根据(5.6)式，(5.5)式可以转化为：

$\frac{\partial S}{\partial g_{a,b}}==(V_a-V_b)(C_a-C_b)V^{\prime }=(V_a-V_b)(V_a^{\prime }-V_b^{\prime })---\left(5.7\right)$

其中V_a’和V_a’分别为扩展的特勒根伴随网络中节点a与b的节点电压。

根据以上的推导可以看出，只要按照以下的步骤便可求得任一交叉点处通孔数相对于目标函数S的灵敏度：

a)构建扩展特勒根伴随网络。构建过程与5.2中构建特勒根伴随网络相类似，只是最后要在所有的底层违规点处添加大小为1A的吸纳电流源。

b)对伴随网络进行模拟分析。系数矩阵与原网络相同，支路电流向量如(5.6)式所示。

c)求解出伴随网络中所有节点的电压值后，根据(5.1)和(5.7)式即可方便地求解出所需的灵敏度。

7.挑选灵敏度最大的N个交叉点。

从通孔数尚未达到最大值的交叉点中挑选出N个灵敏度最大的交叉点。将挑选出的交叉点处的通孔个数增加1，同时对电路网络中对应交叉点的电导值做相应改变。

N的大小可以随意指定，选择不同的N对程序的运行时间、结果都有影响。一般来讲，选择较大的N可以减少运行时间但是运行后的结果较差。

8.检查各个交叉点处的通孔个数。

如果各个交叉点处通孔数目都已达到上限，表明已无法再配置更多的通孔，循环结束，转第8步；否则转第2步，继续执行下一次循环。

9.循环结束，输出结果。

如下表所示便是程序在4个不同的七层供电网络上运行后的结果，程序对第二层以上的交叉点处的通孔数目进行了优化配置。通过与同一层交叉点处平均配置垂直通孔的方法相比较，可以看出，使用较少数目的通孔，我们的方法更有效地消除了底层的违规点，并且底层节点的最大电压降也平均提高了8％以上。

节点数交叉点数N  运行时  间(s)  与平均配  置比较 总通 孔数                 交叉点处通孔数的平均值  最大电  压降(v)  违规点  个数   7-6层  6-5层  5-4层  4-3层   3-2层  1  19078  2127  100  186.08  优化配置  平均配置 3627 5376    4.79    5  3.06  4  3.71  4  2.04  3   1.13   2  0.0586  0.06378    0    89  2  36562  4044  150  611.99  优化配置  平均配置 6294 8872    3.91    4  2.64  3  3.00  3  1.86  2   1.11   2  0.06726  0.07573    69    709  3  58287  8394  200  957.75  优化配置  平均配置 12594 18724    4.95    5  2.44  3  2.15  3  1.51  2   1.14   2  0.0652  0.07035    177    756  4  106929  11695  300  3021  优化配置  平均配置 17995 26858    4.03    5  2.70  3  3.01  4  1.78  2   1.11   2  0.05998  0.0646    0    446