基于电源/地网格与行对齐的消除串扰的总体布线方法

摘要

本发明属于标准单元之总体布线的计算机辅助设计领域，其特征在于：首先利用现有技术产生总体布线的初始解，着重考虑了电感干扰约束的费用函数，通过迭代总体布线进行优化，消除串扰；然后再参考已有费用函数，提出了一个考虑了解决行对齐问题的新费用函数，得到了一个同时考虑行对齐和不一致网格问题来进行屏蔽线分配的最终解。本发明解决了基于电源/地网格的串扰消除的问题，同时实现了减少电路的延时的布线的优化。

主权项

1.基于电源/地网格与行对齐的消除串扰的总体布线方法，其特征在于，所述方法是在计算机中依次按以下步骤实施的：步骤1：向该计算机输入给定的考虑耦合电容的总体布线的初始解：总体布线图GRG网格的行数和列数；线网数；源漏对数；每个源漏对在GRG网格上所经过的边的集合；每条GRG边上所经过的线网的集合；一个线网有一个源点和多个漏点，源漏对是指，由这个源点和每个漏点分别构成的对；步骤2：对当前的总体布线初始解进行不断迭代消除布线初始解中的串扰，在经过一定迭代次数或串扰现象没有减轻时，结束迭代，每一次迭代依次含有以下步骤：步骤2A：读入总体布线的解和用户设定的串扰约束：所选用户设定的串扰约束规定了在所有线网漏点处允许的最大互感系数值；步骤2B：分配串扰约束，以便把用户给出的漏点处的约束转化为相应线网在所经过的每个漏点的GRG边上的最大互感系数的约束，下面定义了一个加入串扰信息后的GRG边权w_t来进行具体分配：$w_t=\frac{f_t+\delta }{c_t+\delta }+\frac{n_{\mathrm{vt}}}{c_t+\delta }$其中，f_t为GRG边t的通道占用量，该通道占用量指GRG边的实际通过的线网数；c_t为边t的通道容量，该通道容量指GRG边容许通过的最大线网数；δ为一个小实数，保证当c_t为0时该定义仍有意义，n_vt为该边上违反串扰约束的线网段个数，串扰约束指的是一条GRG边容许的最大串扰值，由总体布线时的输入给定；w_t表示了边t的实际拥挤度；由于边权w_t的定义引入了n_vt，使得权重中含有串扰信息，在总体布线时能兼顾串扰约束；在这个步骤结束后，每个线网在每个GRG边上都会得到一个串扰约束值w_it，其中下标i为线网编号，t为GRG边的编号；步骤2C：在每个GRG边上消除串扰，首先采用线形长度串扰LSK模型来计算线网之间的互感系数，再用已知的禁忌搜索技术加入屏蔽线来寻找一个能够满足约束，并且面积最小的线网排列方案：设定：在一个左右分别为屏蔽线L和屏蔽线R的区域内，有两个互相敏感的线网i和j，而i在j的左边；则：线网i和j之间的互感系数k_ij为：$k_{\mathrm{ij}}=\frac{1}{2}(\frac{l_{\mathrm{Li}}}{l_{\mathrm{Lj}}}+\frac{l_{\mathrm{Rj}}}{l_{\mathrm{Ri}}})$其中，l_Li为线网i到左侧屏蔽线L的距离，l_Lj为线网j到左侧屏蔽线L的距离，l_Ri为线网i到右侧屏蔽线R的距离，l_Rj为线网j到右侧屏蔽线R的距离；同时，对于线网i，其实际的互感系数K_cff为：j为所有与i敏感的线网；接着，利用公知的禁忌搜索方法来产生一个串扰在约束范围内的线网排列顺序，其具体步骤依次表达如下：步骤a)：取当前GRG边上的线网顺序x^cur为当前解，同时设定以下参数：N_a，在最优解x^min无改进的情况下算法的迭代次数，为正整数，取值在100到500之间，所述最优解是指曾经到达的费用函数最小的解；N_b，在当前解邻域的合法候选解集中随机挑选候选解的个数，为正整数，取值在100到200之间，所述合法候选解集即邻域中未被禁忌的解的集合；N_c，为了找到一个合法候选解而搜索的最大次数，N_c是用于控制当前领域中大部分的解；解空间，为当前GRG边中线网集合可能构成的所有排列，其中某一种排列对应一个解x；费用函数，评定某个解x优劣的定量标准，用cost(x)表示，费用函数值越大，则解的质量就越差：cost(x)＝w₁c₁+w₂c₂+w₃c₃+w₄c₄；其中，c₁为该GRG边中与敏感线网相邻的线网总数；c₂为该GRG边上的屏蔽线数目；c₃等于GRG边中所有K_cff大于K_th的线网的K_cff-K_th之值的总和，所述K_cff为某个线网i在该GRG边上实际的互感系数，K_th为该线网i在该GRG边上所分配到的互感系数约束值，c₃的表达式如下：$\underset{i}{\Sigma }(K_{\mathrm{eff}}-K_{\mathrm{th}}),\forall i,$满足K_cff＞K_thc₄为该GRG边中满足K_cff＞K_th的线网的总的个数；w₁，w₂，w₃，w₄为权重因子，为0到5的实数；禁忌，是指把费用函数值所设定的被禁忌的费用函数值相等的解记录在一个被称为禁忌表H的表内，使它们在搜索的过程中不能作为新解被选中；禁忌长度T，是一个正整数，取值在1到60之间，表示一个解遭到禁忌后，在T次迭代内不能被选中，超过禁忌长度后，原本遭到禁忌的解可以重新参与挑选过程；禁忌表H，记录被禁忌的解及其相应禁忌长度的列表，在完成一次迭代后，该表中所有被禁忌的解的禁忌长度都会减1，新的禁忌长度为零的被禁忌的解会被从禁忌表中删除，重新考虑挑选过程；在设定以上参数及费用函数后，初始化禁忌表H，计数器a和c清空，初始化x^min＝x^cur；步骤b)：判断计数器a的迭代次数是否小于N_a，若a的值不小于参数N_a，搜索结束；否则转步骤c)；步骤c)：将临时变量tmpcost变量置为无穷大，清空计数器b，所述tmpcost是xtmp的费用函数，而tmpcost是从合法候选集中所能找到的费用函数最小的解；步骤d)：判断计数器b的值是否小于数N_b，若b的值不小于参数N_b，转步骤i)，否则转步骤e)；步骤e)：通过随机移动产生新解x^ncw，并判断其费用函数是否遭到禁忌，若没有遭禁忌，转步骤g)，若遭到禁忌，转步骤f)；所述的随机移动即从当前解x^cur的邻域中找到一个新解x^now的方法，包括随机调换两个线网的位置，其权重为w₅；随机移动一个线网的位置，其权重为w₆；随机插入一个屏蔽线，其权重为w₇；随机删除一个屏蔽线，其权重为w₈；满足w₅+w₆+w₇+w₈＝1；所有权重值事先设定，每次随机操作时从这四种移动中选择一种；步骤f)：计数器c的值加1，并判断c的值是否小于参数N_c，N_c为正整数，取值在5到50之间；若c的值不小于N_c，则将计数器c清空，并转步骤g)，否则转步骤e)，重新搜索一个合法候选解；步骤g)：判断新解x^new的费用函数cost(x^new)是否小于变量tmpcost，若是，则将x^new记录为x^tmp，并将其费用记录为tmpcost，否则不做记录；步骤h)：计数器b的值加1，并转步骤d)，重新寻找一个合法候选解；步骤i)：禁忌x^new的费用函数cost(x^new)，并选取x^tmp为当前解x^cur，并比较x^cur的费用函数cost(x^cur)和最优解x^min的费用函数cost(x^min)；若cost(x^cur)小于cost(x^min)，则将x^cur记录为x^min，同时清空计数器a；否则不作记录，计数器a的值加1；步骤j)：更新禁忌表H，即对所有被禁忌的费用函数，禁忌长度减1，禁忌长度减为零的则解除禁忌；禁忌长度的合理取值范围为1到60，同时转步骤b)；步骤3：利用性能和串扰驱动的最小化面积的总体布线程序Gr，对由步骤2得到的串扰最小的解进行布线并得到结果X₁；Gr包含以下步骤：3.a.初始化总体布线参数；3.b.读总体布线树初始解；3.c.统计总的资源使用情况，以及关键路径情况；4.c.进行一系列优化，以得到近似最优解，具体步骤如下：4.c.a.重新计算当前解的拥挤度；4.c.b.如果当前解可以接受，返回，否则进入4.c.c；4.c.c.建立待优化线网数组tmpNets；4.c.d.当优化循环小于给定的次数，或结束标志没来时：先将tmpNets中的线网顺序打乱；然后对每个线网：将该线网在GRG网格中占用的资源释放；重新计算那些用量有改变的的边的权重，也就是拥挤度；对该线网进行拆线重布；随后，不同线网在同一GRG边上的排列位置关系变化会改变该边的串扰值；而插入屏蔽线会消除它两侧线网之间的串扰；本发明采用调换线网顺序同时插入屏蔽线shield的方法，消除X₁中的串扰，并得到结果X₂；步骤4：得到基于行对齐原则的费用函数计算公式：本方法采用禁忌搜索算法来消除串扰噪声；但是本方法考虑了行对齐问题；所谓行对齐问题，是指同一线网的边，处在相邻GRG边上，但是不位于同样的通道，这可能在详细布线阶段造成更多的通孔；对GRG边采用新的费用计算公式，如下：cost′(x)＝w₁′c₁  +w₂′c₂+w₃′c₃+w₄′c₄+w₉ c₉其中w₁′，w₂′，w₃′和w₄′是权重，分别等于13，2，13和10；c₁是敏感线网，凡是能够影响线网i上信号性能的其他线网，都称之为与线网i敏感；这些线网也就是线网i的敏感线网；相邻的数目，c₂是插入的屏蔽线个数，c₃是违反串扰约束的值之和，c₄是违反串扰约束的线网个数；w₁′，w₂′，w₃′，w₄′以及c₁，c₂，c₃，c₄的定义和第3步中提到的禁忌搜索中采用费用计算公式的定义相同，和原有的公式相比，本方法增加了w₉和c₉；w₉是权重，等于15，c₉＝1-p/q，p是同一线网相邻边在同一通道位置的边的个数，q是GRG边的容量，GRG边的容量指的是GRG边在实际走线时容许布的最大通道数；步骤5：设定的水平方向屏蔽线长度下，解决在屏蔽线达不到设定长度时引发的网格不连续问题：设定水平方向的屏蔽线长度等于3条GRG边的长度，在调整相邻的3条GRG边线网布线水平顺序时，依次含有以下步骤：5.A.GRG的同一水平坐标的水平边按水平顺序，每3条GRG边分为一组，最后若不足3条，也归入同一组；5.B.在同一组内，计算每一条GRG边含有的屏蔽线个数，将屏蔽线最多的GRG边定为关键边；接着，本方法让其余2条GRG边上与关键边的屏蔽线在同一通道的线网边改为屏蔽线，将原有的线网边暂时移动到通道上还没有占用的位置上；5.C.最后，本方法调整非关键边中的线网顺序，使费用最小化；本方法采用了步骤4中基于行对齐原则的费用函数计算公式作为边的费用函数，并采用禁忌搜索算法，找到使费用最小的解。