基于模式匹配的电源/地线网络与布图规划的协同设计方法

摘要

基于模式匹配的电源/地线网络与布图规划的协同设计法属于集成电路计算机辅助设计领域，其特征在于：是一种首先创建一个电源/地线网络模式表，将预先建立的112种网格形式的重要信息数据存放在该表中，然后对于给定的一个版图，可以从已经建立好的电源/地线网络模式表中根据一定的模式选择机制选择适当的电源/地线网络，同时采用电源/地线网络的增量式布图规划方法，达到电源/地线网络与布图规划的有效协同设计的方法，它具有快速，易于扩展的优点，可扩大能够处理的芯片的规模。

主权项

1.基于模式匹配的电源/地线网络与布图规划的协同设计法，其特征在于：在计算机中是按照如下步骤实现的：步骤(1).计算机读入初始版图信息和约束文件，该约束文件包括三种电性能约束：(I).电压降约束：模块k每个电源引脚上的电压要大于或等于从电源线上获取电压的最小值V_min，k，模块k的每个地线引脚上的电压要小于或等于从地线上获取电压的最大值V_max，k；，(II).最小线宽约束：在电源/地线网络上连接相邻两个结点n₁和n₂的分支b的宽度必须大于一个最小的宽度值：$w_b=\frac{\rho ·l_b·I_b}{V_b}\ge w_{b,\min },$其中，b是分支序号，w_b是分支b的宽度，w_b，min是分支b的最小宽度，l_b是分支b的长度，I_b是分支b上的电流，ρ是电阻率，V_b是分支b上的电压，(III).电迁移约束，即最大电流密度约束，表示为：|V_n1-V_n2|≤ρ·l_b·σ，其中，V_n1，V_n2分别为所述两个相邻结点n₁和n₂上的电压，σ是工艺所允许的最大电流密度；步骤(2).创建包含112种模式的电源/地线网络模式表，包括7种不同长宽比的Mesh网格，所述长宽比分别是1∶3，1∶2，1∶1，1.5∶1，2∶1，2.5∶1和3∶1，在每种长宽比确定的前提下，Mesh网格的密度包括3×3，4×4，...，17×17，18×18共16种选择，其中，网格密度为MxM的Mesh网格表示将长和宽分别M等分后建立的网格，其中，每个电源/地线网络表示为G＝{N，B}，N为结点数，N＝{1，2，3，...，n，...，N}，B表示分支数，B＝{1，2，3，...，b，...，B}，每一个分支b连接两个相邻结点n1，n2，每个分支b的电阻值R_b＝ρ·l_b/w_b，两个电源分别放在左下角和右上角；步骤(3).根据输入的版图信息，构造初始的二叉树B*-Tree：版图中左下角的模块对应于所述B*-Tree中的根结点，从所述左下角模块出发，用箭头所表示的分支指向的模块称为子模块，在版图上从同一个模块出发，用箭头所指向的左、右相邻的两个子模块在所述B*-Tree上为两个右、左相邻的两个子结点，根结点为第零层，以下各子结点的层次逐层加1，设置温度T＝T₀，所述温度T为模拟退火算法中的基本要素，T₀为设定的初始温度，设置迭代次数计数器counter＝0；步骤(4).从步骤(2)中建立的电源/地线网格模式表中选择长宽比的归一化值与该版图的长宽比的归一化值最接近的网格模式来满足给定的版图，同时将所选择的模式根据版图的长和宽依照设定的比例进行缩放以保证电源/地线网络能刚好覆盖住版图，之后选择最小的3×3的网格密度；步骤(5).电源地线网络引脚分配：1)分别计算出每个模块到两个供电电源之间的距离，模块到电源的距离即为模块的中心坐标到电源坐标的距离，2)分别分配距离供电电源最远的模块的电源引脚和地线引脚，然后沿左下角方向依次分配直到相关模块的引脚分配完成，3)返回到所述距供电电源最远的模块，向右上角方向未分配引脚的模块依次分配引脚；步骤(6).构造电源/地线网络的静态分析模型GV＝I，其中，G是电阻的电导矩阵，V表示的是结点电压向量，I是结点电流向量，向量I和V的维数等于电源/地线网络中的结点个数，利用ICCG算法求解各结点的电压V＝G^-1I；步骤(7).根据步骤(6)的分析结果，如果存在违反约束的模块，即存在模块违反步骤(1)中所描述的约束条件，则根据下述方程进行线宽优化：$\mathrm{Width}\_\mathrm{fact}=\frac{\mathrm{Worst}\_\mathrm{IR}}{T\arg \mathrm{et}\_\mathrm{IR}},$其中，Width_fact表示的是在改变线宽操作之后的电源/地线网络的电源线宽，Worst_IR表示当前最大的电压降，Target_IR指的是允许的最大电压降，如果Width_fact＞1，则以步长α·Width_fact增加电源线的宽度，α为设定的增量因子，1＜α＜10，转步骤(6)，如果Width_fact＜1，减小电源线宽以降低布线资源，转步骤(6)，如果增加的线宽达到最大线宽但仍然存在不满足约束的模块，增大一个Mesh网格密度，转步骤(5)；步骤(8).如果所有的网格密度都不能消除违反约束的模块，则按照如下步骤增量式改进布图结构：步骤(8.1).利用违反约束的模块的坐标分别计算出该模块与所述两个供电电源的距离，从其中选择一个距离较小的供电电源，再以距离这个距离较小的供电电源最近的模块作为零层次，重新按逐层加1的方法确定各个模块的层次，步骤(8.2).在所述B*-Tree二叉树上进行如下增量式操作：选择一个比所述违反约束的模块所对应的结点在层次上更低的其他结点与这个对应着违反约束的模块的结点进行交换，或者，选择一个结点作为对应于违反约束模块的结点的父结点，以取得比该违反约束的模块对应的结点的原始位置所在的层次更低，步骤(8.3).转步骤(10)；步骤(9).若存在某个网格密度能消除所有违反约束的模块，对版图结构进行扰动，在其对应的B*-Tree上按设定的交换次数随机交换两个结点，或者按设定的移动次数随机移动一个结点来对应地改变版图布局以产生新解；步骤(10).利用如下代价函数评价所得解：其中，A(s)表示版图的面积，W(s)表示总的互连线长，Ap(s)表示用于电源/地线网络的绕线资源，表示的是针对电压降约束和电子迁移约束的惩罚函数，λi为归一化常数，即$\underset{k=1}{\overset{4}{\Sigma }}{\lambda }_k=\mathrm{1,0}<{\lambda }_k<\mathrm{1,1}\le k\le 4;$给定一个版图s，A_P(s)按下式计算：$A_p\left(s\right)=\underset{b=1}{\overset{B}{\Sigma }}{l}_b\times w_b,$其中，l_b为分支b的长度，w_b为分支b的宽度；按下式计算：其中，对于电源网上的结点n，对于地网上的结点n，其中，结点n所对应的电源或地线引脚属于模块k，结点n₁和n₂为分支b的两个端点，v_n1和v_n2分别为n₁和n₂上的电压，v_n为结点n所对应的引脚上的电压值；步骤(11).利用步骤(10)中的公式计算新解ω_new，将所述新解和前counter次迭代次数计算出来的最优解ω_best比较：若counter＝0，ω_best＝ω_new，否则，如果ω_new＜ω_best，则ω_best＝ω_new，如果ω_new≥ω_best，则按照概率使ω_best＝ω_new；步骤(12).计数器counter加1，若counter达到设定的迭代次数C，保存该C次循环过程中的最优值ω_best，否则转步骤(4)，步骤(13).温度T＝β·T，0＜β＜1，若T≤T_min，其中T_min为设定的最小温度，则程序结束，从所得的一组最优值中选取最小的值即为所得最优解，否则，counter＝0，转步骤(4)。