时序松弛约束下超大规模集成电路绕障X结构布线方法

时序松弛约束下超大规模集成电路绕障x结构布线方法
技术领域
1.本发明属于计算机辅助设计技术领域，具体涉及一种超大规模集成电路绕障x结构布线方法。


背景技术：

2.现有技术分为以下三种类型的工作，分别是构建x结构steiner最小树(x-architecture steiner minimum tree，xsmt)、绕障x结构steiner最小树(obstacle-avoiding x-architecture steiner minimum tree，oaxsmt)以及时序约束下x结构steiner最小树(timing-driven x-architecture steiner minimum tree(tdxsmt)。
3.1.xsmt
4.smt的构造问题是布线阶段的一个关键性问题，而xsmt由于在线长和时延等关键性指标中明显优于直角结构的steiner最小树，因此在近几年受到人们的广泛关注。
5.coulston提出了一种精确的xsmt构造方法，但该方法由于其时间复杂度呈指数级，所以实用性不高。zhu等提出了两种分别结合边替换和三角收缩的方式来构造xsmt。ho等提出了一种构造针对多层布线问题的xsmt方法，并且设计了针对3引脚线网的最佳x结构布线结构。arora等提出了一种基于蚁群算法的xsmt构造方法，可以有效减少线长和电容。wu等提出了一种基于微分进化算法的xsmt构造方法，结合遗传算法来解决离散的smt构造问题，从而得到了一个高质量的解决方案。
6.2.oaxsmt
7.由于芯片中存在预布线网、宏单元等障碍物，oasmt问题得到了人们的重视，在非曼哈顿结构的oasmt中，最常见的是oaxsmt。
8.jing等提出了一种纯启发式的λ-oasmt构造方法。基于对障碍物的三角剖分算法，构造了一个全连接树，并通过区域组合将其嵌入到λ-oasmt中。λ-oasmt的高效和准确性使其在布线阶段非常实用。huang等提出了一种基于粒子群优化算法的oaxsmt构造方法，该方法在各种基准测试中都取得了良好的效果，并在合理的运行时间下获得了高质量的解。huang等提出了一种快速四步启发式方法，在不过度牺牲质量的情况下，其运行速度得到了极大的提升。huang等的方法中首先基于查找表来构建三维无障碍物的mst，再采用三种基于投影的避障策略，最后结合两种有效的精炼技术将三维mst转化为多层oaxsmt。
9.3.tdxsmt
10.随着互连线的时延在总时延中的比例越来越大，在布线阶段考虑时序约束的研究也越来越多。
11.在给定任意线网的直角steiner最小树的情况下，yan提出了一种有效的基于变换的方法，通过对x结构距离的计算、steiner点再分配和路径重构，构造了一个tdxsmt。huang等提出了一种针对矩形和非矩形障碍物的tdxsmt算法。该方法可以处理矩形和非矩形障碍物，减少从源点到汇点的最小延迟。liu等提出了一种基于多目标pso和elmore延迟模型，构建了一个拥有最小半径的最小代价生成树。chen等提出了一种基于社会学习多目标pso的
有效方法，构造了一个半径最短的tdxsmt。
12.然而以上三种类型的超大规模集成电路布线算法都没有考虑将芯片中的障碍物和互连线的时延同时作为布线的约束，忽视了其中的一种或者两种约束对布线效果的影响。


技术实现要素：

13.为了克服现有技术的不足，本发明提供了一种时序松弛约束下超大规模集成电路绕障x结构布线方法，在粒子群优化方法的基础上，采用一种基于遗传算子的更新方式，通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新。对处于半径的所有连线进行遍历，选择最小化线长和时延的布线结构，并允许牺牲少量的线长来增大引脚的时序松弛值。根据连线与障碍组相交的的情况来选择伪steiner点，通过添加伪steiner点使得所有引脚之间的连线完全绕障。本发明方法能够有效绕障并优化线长和最坏负松弛值(worst negative slack，wns)，从而优化芯片的性能。
14.本发明解决其技术问题所采用的技术方案包括如下步骤：
15.步骤1：信息初始化；
16.构建边障表记录各连线与障碍的相交情况信息并在后续引入伪steiner点后进行更新；
17.综合考虑线长和半径，利用prim-dijkstra算法构建初始的生成pd树；
18.对pd树进行编码；遍历pd树每两个引脚之间的连线，并将每条连线用3个数字保存，这3个数字分别代表两个引脚的编号和它们的连线方式并在最后1位数中给出pd树的适应值；
19.步骤2：粒子的更新方式；
20.采用基于遗传算子的离散位置更新方式，在并查集的基础上通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新；
21.粒子的更新公式具体表示成如下公式：
[0022][0023]
其中，表示第i个，第t代粒子；c2为全局交叉操作，c1为个体交叉操作，v为个体变异操作；r1和r2为交叉的概率，w为个体变异概率；
[0024]
步骤3：种群初始化；
[0025]
粒子种群的初始化是设定种群数量popsize、最大迭代次数count、加速因子和权重的数值，随机生成popsize个pd树并编码将其作为粒子群的初始种群，并初始化每个粒子的历史最优位置和粒子群的全局最优位置；
[0026]
设计一种线性增长公式使w、r1和r2随迭代次数自适应改变，其计算公式如式(2)、(3)、(4)：
[0027][0028]
[0029][0030]
其中w
t
、r
1t
和r
2t
表示第t代的w、r1和r2；ws、r
1s
和r
2s
表示w、r1和r2的初始值；we、r
1e
和r
2e
表示w、r1和r2的最终值；count为粒子种群的迭代总数，t为粒子种群的迭代次数；
[0031]
步骤4：变异操作；
[0032]
利用个体变异操作来扩大粒子群搜索范围，从而找到全局最优解；
[0033]
变异操作公式如下：
[0034][0035]
其中v表示变异操作，c1表示[0,1)区间的随机数；
[0036]
步骤5：交叉操作；
[0037]
设计个体交叉操作使粒子在局部范围内搜索和全局交叉操作使粒子群向全局最优粒子收敛；
[0038]
个体交叉操作是将粒子与其本身的历史最优位置交叉，使粒子进行局部搜索，公式如下：
[0039][0040]
其中c1表示个体交叉操作，c2表示[0,1)区间的随机数；
[0041]
全局交叉操作是将粒子与粒子种群的最优情况交叉，加快粒子群的收敛速度，其公式如下：
[0042][0043]
其中c2表示个体交叉操作，c3表示[0,1)区间的随机数；
[0044]
步骤6：适应度值的计算；
[0045]
步骤6-1：适应度的计算以优化线长和半径为目标，其公式如下：
[0046]
fitness＝(1-d
t
)
×
wl+d
t
×
pl
ꢀꢀꢀꢀ
(81)5
[0047]
其中wl表示线长；pl表示半径；d
t
是一个均衡线长和半径的平衡因子，随着迭代次数的增长进行线性增长，从而线性的改变线长和半径的比重，线性增长的公式如下：
[0048][0049]
其中ds为d
t
的初始值，de为d
t
的最终值；
[0050]
步骤6-2：在线长的计算中加入障碍组的部分周长，从而减少绕障的线长，线长计算公式如下：
[0051][0052]
其中是边e
se
的线长，(xe,ye)和(xs,ys)分别为边e
se
的两个顶点坐标，为边e
se
穿过的障碍组的四分之一周长，其公式如下：
[0053]
[0054]
其中，(x
bmin
,y
bmin
)和(x
bmax
,y
bmax
)分别表示连线e
se
经过的障碍组的左下角坐标和右上角坐标；
[0055]
wl是布线的总线长，其计算公式如下：
[0056][0057]
其中wl
re
是连线中重叠边的线长；
[0058]
pl是布线的半径，其计算公式如下：
[0059][0060]
其中表示生成树的叶子节点，表示从源点到引脚pn的路径；
[0061]
步骤7：时序松弛优化策略；
[0062]
构建最优更新数组来保存更新的连线以及更新后的线长和wns，将粒子群优化算法生成的最优粒子及其线长和wns作为最优更新数组的初始值；
[0063]
找到最优粒子中具有最坏负松弛值的引脚，并确定该引脚所在的从源点到汇点的最长路径，假设在该条路径上，从源点到叶子节点之间的引脚分别为p1,p2…
,p
l
；遍历该条路径上除源点以及源点的下一个引脚外的所有引脚pi，即i≠1,2，删除pi与p
i-1
的连线，并将pi与p1,p2…
,p
i-2
逐一相连；将每次更新后的线长和wns与最优更新的线长和wns进行对比，将得到以下四种结果之一：
[0064]
(1)线长以及wns都得到优化，则将其替换为最优更新；
[0065]
(2)线长得到优化，wns未被优化，若减少的线长大于减少的wns，则将其替换为最优更新，反之跳过该更新；
[0066]
(3)线长未得到优化，wns被优化，则将其替换为最优更新；
[0067]
(4)线长和wns都未得到优化，则跳过该更新；
[0068]
步骤8：连线方式的选取；
[0069]
当连线经过障碍时，删除该条连线，并分别用4种连线方式连接两个引脚，并通过边障表判断是否经过障碍，此时有以下三种情况：
[0070]
(1)若连线方式0或连线方式1未经过障碍，则用连线方式0或连线方式1连接两个引脚；
[0071]
(2)若连线方式0和连线方式1都经过障碍但连线方式2或连线方式3未经过障碍，则对比连线方式0和连线方式1经过的障碍组的半周长，用半周长最小的连线连线方式连接两个引脚，并进入伪steiner点的选取；
[0072]
(3)若连线方式0、连线方式1、连线方式2和连线方式3都经过障碍，则对比连线方式0、连线方式1、连线方式2和连线方式3经过的障碍组的半周长，用半周长最小的连线方式连接两个引脚，并进入伪steiner点的选取；
[0073]
步骤9：伪steiner点的选取；
[0074]
确定两个引脚之间的连线方式所经过的障碍组的左下角和右上角的坐标，将两个引脚直接相连，连线与障碍组之间的联系有以下三种：
[0075]
(1)连线未与障碍组相交时，选择与连线的垂直距离最短的障碍组内的障碍的顶角作为伪steiner点；
[0076]
(2)连线与障碍组相邻的两边相交时，若连线与障碍组的左边和上边相交，则选取障碍组的左上角为伪steiner点；若连线与障碍组的左边与下边相交，则选取障碍组的左下角为伪steiner点，以此类推；若上述选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替删除该伪steiner点；
[0077]
(3)连线与障碍组相对的两边相交时，障碍组被连线划分为两个部分，选择周长较小的那一部分的两个顶角作为伪steiner点；若选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替删除该伪steiner点；
[0078]
步骤10：绕障策略；
[0079]
首先，通过边障表判断连线是否经过障碍，若经过障碍，则删除该条连线，选取伪steiner点，并增添新的连线；若未经过障碍，则跳过该条连线，继续判断下一条连线是否经过障碍；最后根据新的生成树更新边障表，循环以上操作直至所有连线都不经过障碍，则绕障结束。
[0080]
步骤11：路径精炼策略；
[0081]
通过路径精炼策略增加连线的共享边长度，从而得到拥有更短线长的布线结构；
[0082]
首先，计算每个引脚的度，并记录与该引脚相连的所有引脚；如果引脚的度为d，则列出引脚的4d种布线结构，并选择满足绕障约束并具有最小线长和延迟的连线作为最佳连线；其次，计算每个布线的共享边长度wl
re
，并根据共享边的长度按降序排列；最后，将引脚的初始布线结构替换为其最优布线结构。
[0083]
优选地，所述变异操作为随机删除生成树的一条边后，利用并查集划分两棵树的引脚并分别放入两个集合之中，再从两个集合中随机选出两个引脚，并将其相连。
[0084]
优选地，所述交叉操作首先将两棵生成树中相同的连线放入一个集合作为下一代粒子的部分连线，接着将两个粒子中的不同连线放入另一个集合，利用并查集随机的从第二个集合里挑选连线作为下一代粒子的剩余连线，直到构成一棵完整的生成树。
[0085]
本发明的有益效果如下：
[0086]
本发明方法在芯片物理设计的布线阶段中考虑了障碍物和时延对芯片布线效果的影响，并对布线的线长和半径进行优化，使本发明在完全绕障的基础上，尽可能的减小了时延对布线的负面影响。本发明方法能够有效绕障并优化线长和最坏负松弛值，从而优化芯片的性能。
附图说明
[0087]
图1为两引脚的四种连线方式示意图。
[0088]
图2为变异操作示意图。
[0089]
图3为交叉操作示意图。
[0090]
图4为未绕障的x结构steiner最小树示意图。
[0091]
图5为时序优化策略示意图。
[0092]
图6为绕障策略示意图。
具体实施方式
[0093]
下面结合附图和实施例对本发明进一步说明。
[0094]
本发明提出了一种时序松弛约束的超大规模集成电路绕障x结构布线方法，具体包含以下过程：
[0095]
1.提出粒子群优化策略：在粒子群优化方法的基础上，采用一种基于遗传算子的更新方式，通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新。
[0096]
2.提出时序松弛优化策略：对处于半径的所有连线进行遍历，选择最小化线长和时延的布线结构，并允许牺牲少量的线长来增大引脚的时序松弛值。
[0097]
3.提出绕障策略：根据连线与障碍组相交的的情况来选择伪steiner点，通过添加伪steiner点使得所有引脚之间的连线完全绕障。
[0098]
具体实现如下：
[0099]
1.信息初始化
[0100]
由于后续策略都需要频繁的使用各连线与障碍的相交情况信息，所以本发明构建边障表来记录这些信息并在后续引入伪steiner点后进行更新，以便后续策略的使用。
[0101]
本发明需要综合考虑线长和半径，利用prim-dijkstra算法来构建初始的生成树，以避免造成某些路径过长导致其中某些引脚的最坏负松弛值过小或者为了优化各个引脚的最坏负松弛值而过度牺牲线长的结果。
[0102]
同时，为了构建离散粒子群的初始种群，需要对pd树进行编码。遍历pd树每两个引脚之间的连线，并将每条连线用3个数字保存，其中这3个数字分别代表两个引脚的编号和它们的连线方式(四种连线方式参照图1)，并在最后1位数中给出pd树的适应值。
[0103]
2.粒子的更新方式
[0104]
本发明在粒子群优化算法的基础上采用一种基于遗传算子的离散位置更新方式，在并查集的基础上通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新。
[0105]
粒子的更新公式具体可表示成如下公式：
[0106][0107]
其中，表示第i个，第t代粒子；c2为全局交叉操作，c1为个体交叉操作，v为个体变异操作；r1和r2为交叉的概率，w为个体变异概率。
[0108]
3.种群初始化
[0109]
粒子种群的初始化是设定种群数量popsize、最大迭代次数count、加速因子和权重的数值，随机生成popsize个pd树并编码将其作为粒子群的初始种群，并初始化每个粒子的历史最优位置和粒子群的全局最优位置。同时，本发明设计了一种线性增长公式使w、r1和r2随迭代次数自适应改变。其计算公式如式2、3、4：
[0110][0111]
[0112][0113]
其中w
t
、r
1t
和r
2t
表示第t代的w、r1和r2；ws、r
1s
和r
2s
表示w、r1和r2的初始值；we、r
1e
和r
2e
表示w、r1和r2的最终值；count为粒子种群的迭代总数，t为粒子种群的迭代次数。
[0114]
4.变异操作
[0115]
为了避免陷入局部最优，本发明利用个体变异操作来扩大粒子群搜索范围，从而找到全局最优解。
[0116]
变异操作公式如下：
[0117][0118]
其中v表示变异操作，c1表示[0,1)区间的随机数。
[0119]
变异操作的基本思想为随机删除生成树的一条边后，利用并查集划分两棵树的引脚并分别放入两个集合之中，再从两个集合中随机选出两个引脚，并将其相连。参照图2，随机删除了引脚p1与p3之间的连线，后利用并查集从两个集合中随机选出引脚p4和p3并将其连接。
[0120]
5.交叉操作
[0121]
为了增加种群的多样性并加快粒子群的收敛速度，本发明设计了个体交叉操作使粒子在局部范围内搜索和全局交叉操作使粒子群向全局最优粒子收敛。
[0122]
个体交叉操作是将粒子与其本身的历史最优位置交叉，使粒子进行局部搜索。其公式如下：
[0123][0124]
其中c1表示个体交叉操作，c2表示[0,1)区间的随机数。
[0125]
全局交叉操作是将粒子与粒子种群的最优情况交叉，加快粒子群的收敛速度。其公式如下：
[0126][0127]
其中c2表示个体交叉操作，c3表示[0,1)区间的随机数。
[0128]
交叉操作的原理参照图3。首先将两棵生成树中相同的连线放入一个集合作为下一代粒子的部分连线，接着将两个粒子中的不同连线放入另一个集合，利用并查集随机的从第二个集合里挑选连线作为下一代粒子的剩余连线，直到构成一棵完整的生成树。
[0129]
6.适应度值的计算
[0130]
本发明不仅需要减少线长，还需要满足时序约束，且由于时序约束与半径息息相关，半径越长的路径往往越容易违背时序约束，因此适应度的计算以优化线长和半径为目标，其公式如下：
[0131]
fitness＝(1-d
t
)
×
wl+d
t
×
pl
ꢀꢀꢀꢀꢀꢀ
(8)
[0132]
其中wl表示线长，pl表示半径，d
t
是一个均衡线长和半径的平衡因子，它会随着迭代次数的增长进行线性增长，从而线性的改变线长和半径的比重。其线性增长的公式如下：
[0133][0134]
其中ds为d
t
的初始值，de为d
t
的最终值。
[0135]
由于障碍的存在，连线若经过障碍一定会导致线长增大，因此本发明考虑在线长的计算中加入障碍组的部分周长，从而减少绕障的线长。线长计算公式如下：
[0136][0137]
其中是边e
se
的线长，(xe,ye)和(xs,ys)分别为边e
se
的两个顶点坐标，为边e
se
穿过的障碍组的四分之一周长，其公式如下：
[0138][0139]
其中，(x
bmin
,y
bmin
)和(x
bmax
,y
bmax
)分别表示连线e
se
经过的障碍组的左下角坐标和右上角坐标。
[0140]
wl是布线的总线长，其计算公式如下：
[0141][0142]
其中wl
re
是连线中重叠边的线长。
[0143]
pl是布线的半径，其计算公式如下：
[0144][0145]
其中表示生成树的叶子节点，表示从源点到引脚pn的路径。
[0146]
7.时序松弛优化策略
[0147]
首先，构建最优更新数组来保存更新的连线以及更新后的线长和wns，将粒子群优化算法生成的最优粒子及其线长和wns作为最优更新数组的初始值。找到最优粒子中具有最坏负松弛值的的引脚，并确定该引脚所在的从源点到汇点的最长路径，假设在该条路径上，从源点到的叶子节点之间的引脚分别为p1,p2…
,p
l
。遍历该条路径上除源点以及源点的下一个引脚外的所有引脚pi(即i≠1,2)，删除pi与p
i-1
的连线，并将pi与p1,p2…
,p
i-2
逐一相连。将每次更新后的线长和wns与最优更新的线长和wns进行对比，将得到以下四种结果之一：
[0148]
(1)线长以及wns都得到优化，则将其替换为最优更新。
[0149]
(2)线长得到优化，wns未被优化。若减少的线长大于减少的wns，则将其替换为最优更新，反之跳过该更新。
[0150]
(3)线长未得到优化，wns被优化，则将其替换为最优更新。
[0151]
(4)线长和wns都未得到优化，则跳过该更新。
[0152]
8.连线方式的选取
[0153]
当连线经过障碍时，删除该条连线，并分别用4种连线方式连接两个引脚，并通过边障表判断是否经过障碍，此时有以下三种情况：
[0154]
若连线方式0或连线方式1未经过障碍，则用连线方式0或连线方式1连接两个引脚；
[0155]
若连线方式0和连线方式1都经过障碍但连线方式2或连线方式3未经过障碍，则对
比连线方式0和连线方式1经过的障碍组的半周长，用半周长最小的连线连线方式连接两个引脚，并进入伪steiner点的选取；
[0156]
若连线方式0、连线方式1、连线方式2和连线方式3都经过障碍，则对比连线方式0、连线方式1、连线方式2和连线方式3经过的障碍组的半周长，用半周长最小的连线方式连接两个引脚，并进入伪steiner点的选取。
[0157]
9.伪steiner点的选取
[0158]
确定两个引脚之间的连线方式所经过的障碍组的左下角和右上角的坐标，将两个引脚直接相连，连线与障碍组之间的联系有以下三种：
[0159]
(1)连线未与障碍组相交时，选择与连线的垂直距离最短的障碍组内的障碍的顶角作为伪steiner点。
[0160]
(2)连线与障碍组相邻的两边相交时，若连线与障碍组的左边和上边相交，则选取障碍组的左上角为伪steiner点；若连线与障碍组的左边与下边相交，则选取障碍组的左下角为伪steiner点，以此类推。若上述选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替该伪steiner点。
[0161]
(3)连线与障碍组相对的两边相交时，障碍组被连线划分为两个部分，选择周长较小的那一部分的两个顶角作为伪steiner点。若选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替该伪steiner点。
[0162]
10.绕障策略
[0163]
首先，通过边障表判断连线是否经过障碍，若经过障碍，则删除该条连线，选取伪steiner点，并增添新的连线；若未经过障碍，则跳过该条连线，继续判断下一条连线是否经过障碍。最后根据新的生成树更新边障表，循环以上操作直至所有连线都不经过障碍，则绕障结束。
[0164]
11.路径精炼策略
[0165]
在满足避障约束和时序松弛约束后，一些路径在线长上仍可以进一步优化。本发明通过路径精炼策略来增加连线的共享边长度，从而得到拥有更短线长的布线结构。
[0166]
首先，计算每个引脚的度，并记录与该引脚相连的所有引脚。如果引脚的度为d，则列出引脚的4d种布线结构，并选择满足绕障约束并具有最小线长和延迟的连线作为最佳连线。其次，计算每个布线的共享边长度wl
re
，并根据共享边的长度按降序排列。最后，将引脚的初始布线结构替换为其最优布线结构。
[0167]
具体实施例：
[0168]
1.通过粒子群优化策略构建一棵未绕障的x结构steiner最小树，参照图4；
[0169]
2.通过时序松弛优化策略优化x结构steiner最小树的时延，参照图5，其中，a表示引脚信息的实际到达时间，r表示引脚信息要求到达的时间，s表示引脚的松弛值，松弛值越大说明布线稳定性越好；
[0170]
3.通过绕障策略使x结构steiner最小树完全绕障，参照图6。
[0171]
为了证明粒子群优化策略的有效性，本发明在严格松弛条件下，比较了有无粒子群优化策略的方法的半径、线长以及wns。如表1所示，粒子群优化策略使半径、线长及wns分别优化了11％、2％和8％。
[0172]
表1在严格松弛条件下，有无粒子群优化策略的对比。
[0173][0174]
为了证明时序松弛优化策略的有效性，本发明在严格松弛条件下，比较了有无时序松弛优化策略前后的半径、线长以及wns。如表2所示，时序松弛优化策略使半径、线长及wns分别优化了19％、2％和17％。
[0175]
表2在严格松弛条件下，有无时序松弛优化策略的对比。
[0176][0177][0178]
为了证明绕障策略的有效性，本发明在严格松弛条件下，比较了有无绕障策略的半径、线长以及wns。如表3所示，绕障策略使半径、线长及wns分别优化了3％、3％和9％。
[0179]
表3在严格松弛条件下，有无绕障策略的对比。
[0180][0181]
为了验证本发明策略的有效性，本发明与相关方法在严格松弛条件下进行比较。未考虑时序松弛约束的oaxsmt算法，如表4所示，本发明相较于文献，在半径、线长及wns分别优化了41％、6％和59％。tdxsmt算法，如表5所示，本发明与文献线长相当，但在半径和wns上分别优化了12％和51％。
[0182]
表4在严格松弛条件下，本发明与文献的对比
[0183][0184][0185]
表5在严格松弛条件下，本发明与文献的对比
[0186]

技术特征：
1.一种时序松弛约束下超大规模集成电路绕障x结构布线方法，其特征在于，包括如下步骤：步骤1：信息初始化；构建边障表记录各连线与障碍的相交情况信息并在后续引入伪steiner点后进行更新；综合考虑线长和半径，利用prim-dijkstra算法构建初始的生成pd树；对pd树进行编码；遍历pd树每两个引脚之间的连线，并将每条连线用3个数字保存，这3个数字分别代表两个引脚的编号和它们的连线方式并在最后1位数中给出pd树的适应值；步骤2：粒子的更新方式；采用基于遗传算子的离散位置更新方式，在并查集的基础上通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新；粒子的更新公式具体表示成如下公式：其中，表示第i个，第t代粒子；c2为全局交叉操作，c1为个体交叉操作，v为个体变异操作；r1和r2为交叉的概率，w为个体变异概率；步骤3：种群初始化；粒子种群的初始化是设定种群数量popsize、最大迭代次数count、加速因子和权重的数值，随机生成popsize个pd树并编码将其作为粒子群的初始种群，并初始化每个粒子的历史最优位置和粒子群的全局最优位置；设计一种线性增长公式使w、r1和r2随迭代次数自适应改变，其计算公式如式(2)、(3)、(4)：(4)：(4)：其中w
t
、r
1t
和r
2t
表示第t代的w、r1和r2；w
s
、r
1s
和r
2s
表示w、r1和r2的初始值；w
e
、r
1e
和r
2e
表示w、r1和r2的最终值；count为粒子种群的迭代总数，t为粒子种群的迭代次数；步骤4：变异操作；利用个体变异操作来扩大粒子群搜索范围，从而找到全局最优解；变异操作公式如下：其中v表示变异操作，c1表示[0,1)区间的随机数；步骤5：交叉操作；设计个体交叉操作使粒子在局部范围内搜索和全局交叉操作使粒子群向全局最优粒子收敛；
个体交叉操作是将粒子与其本身的历史最优位置交叉，使粒子进行局部搜索，公式如下：其中c1表示个体交叉操作，c2表示[0,1)区间的随机数；全局交叉操作是将粒子与粒子种群的最优情况交叉，加快粒子群的收敛速度，其公式如下：其中c2表示个体交叉操作，c3表示[0,1)区间的随机数；步骤6：适应度值的计算；步骤6-1：适应度的计算以优化线长和半径为目标，其公式如下：fitness＝(1-d
t
)
×
wl+d
t
×
pl
ꢀꢀꢀꢀꢀꢀꢀꢀ
(8)其中wl表示线长；pl表示半径；d
t
是一个均衡线长和半径的平衡因子，随着迭代次数的增长进行线性增长，从而线性的改变线长和半径的比重，线性增长的公式如下：其中d
s
为d
t
的初始值，d
e
为d
t
的最终值；步骤6-2：在线长的计算中加入障碍组的部分周长，从而减少绕障的线长，线长计算公式如下：其中是边e
se
的线长，(x
e
,y
e
)和(x
s
,y
s
)分别为边e
se
的两个顶点坐标，为边e
se
穿过的障碍组的四分之一周长，其公式如下：其中，(x
bmin
,y
bmin
)和(x
bmax
,y
bmax
)分别表示连线e
se
经过的障碍组的左下角坐标和右上角坐标；wl是布线的总线长，其计算公式如下：其中wl
re
是连线中重叠边的线长；pl是布线的半径，其计算公式如下：其中表示生成树的叶子节点，表示从源点到引脚p
n
的路径；步骤7：时序松弛优化策略；构建最优更新数组来保存更新的连线以及更新后的线长和wns，将粒子群优化算法生成的最优粒子及其线长和wns作为最优更新数组的初始值；
找到最优粒子中具有最坏负松弛值的引脚，并确定该引脚所在的从源点到汇点的最长路径，假设在该条路径上，从源点到叶子节点之间的引脚分别为p1,p2…
,p
l
；遍历该条路径上除源点以及源点的下一个引脚外的所有引脚p
i
，即i≠1,2，删除p
i
与p
i-1
的连线，并将p
i
与p1,p2…
,p
i-2
逐一相连；将每次更新后的线长和wns与最优更新的线长和wns进行对比，将得到以下四种结果之一：(1)线长以及wns都得到优化，则将其替换为最优更新；(2)线长得到优化，wns未被优化，若减少的线长大于减少的wns，则将其替换为最优更新，反之跳过该更新；(3)线长未得到优化，wns被优化，则将其替换为最优更新；(4)线长和wns都未得到优化，则跳过该更新；步骤8：连线方式的选取；当连线经过障碍时，删除该条连线，并分别用4种连线方式连接两个引脚，并通过边障表判断是否经过障碍，此时有以下三种情况：(1)若连线方式0或连线方式1未经过障碍，则用连线方式0或连线方式1连接两个引脚；(2)若连线方式0和连线方式1都经过障碍但连线方式2或连线方式3未经过障碍，则对比连线方式0和连线方式1经过的障碍组的半周长，用半周长最小的连线连线方式连接两个引脚，并进入伪steiner点的选取；(3)若连线方式0、连线方式1、连线方式2和连线方式3都经过障碍，则对比连线方式0、连线方式1、连线方式2和连线方式3经过的障碍组的半周长，用半周长最小的连线方式连接两个引脚，并进入伪steiner点的选取；步骤9：伪steiner点的选取；确定两个引脚之间的连线方式所经过的障碍组的左下角和右上角的坐标，将两个引脚直接相连，连线与障碍组之间的联系有以下三种：(1)连线未与障碍组相交时，选择与连线的垂直距离最短的障碍组内的障碍的顶角作为伪steiner点；(2)连线与障碍组相邻的两边相交时，若连线与障碍组的左边和上边相交，则选取障碍组的左上角为伪steiner点；若连线与障碍组的左边与下边相交，则选取障碍组的左下角为伪steiner点，以此类推；若上述选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替删除该伪steiner点；(3)连线与障碍组相对的两边相交时，障碍组被连线划分为两个部分，选择周长较小的那一部分的两个顶角作为伪steiner点；若选取的伪steiner点不属于障碍组内的障碍的顶角，则选择距离该伪steiner点最近的障碍组内的障碍的顶角来代替删除该伪steiner点；步骤10：绕障策略；首先，通过边障表判断连线是否经过障碍，若经过障碍，则删除该条连线，选取伪steiner点，并增添新的连线；若未经过障碍，则跳过该条连线，继续判断下一条连线是否经过障碍；最后根据新的生成树更新边障表，循环以上操作直至所有连线都不经过障碍，则绕障结束；步骤11：路径精炼策略；通过路径精炼策略增加连线的共享边长度，从而得到拥有更短线长的布线结构；
首先，计算每个引脚的度，并记录与该引脚相连的所有引脚；如果引脚的度为d，则列出引脚的4
d
种布线结构，并选择满足绕障约束并具有最小线长和延迟的连线作为最佳连线；其次，计算每个布线的共享边长度wl
re
，并根据共享边的长度按降序排列；最后，将引脚的初始布线结构替换为其最优布线结构。2.根据权利要求1所述的一种时序松弛约束下超大规模集成电路绕障x结构布线方法，其特征在于，所述变异操作为随机删除生成树的一条边后，利用并查集划分两棵树的引脚并分别放入两个集合之中，再从两个集合中随机选出两个引脚，并将其相连。3.根据权利要求1所述的一种时序松弛约束下超大规模集成电路绕障x结构布线方法，其特征在于，所述交叉操作首先将两棵生成树中相同的连线放入一个集合作为下一代粒子的部分连线，接着将两个粒子中的不同连线放入另一个集合，利用并查集随机的从第二个集合里挑选连线作为下一代粒子的剩余连线，直到构成一棵完整的生成树。

技术总结
本发明公开了一种时序松弛约束下超大规模集成电路绕障X结构布线方法，在粒子群优化方法的基础上，采用一种基于遗传算子的更新方式，通过变异操作和交叉操作使粒子可以通过个体变化和种群之间信息交互来实现粒子群的搜索和更新。对处于半径的所有连线进行遍历，选择最小化线长和时延的布线结构，并允许牺牲少量的线长来增大引脚的时序松弛值。根据连线与障碍组相交的的情况来选择伪Steiner点，通过添加伪Steiner点使得所有引脚之间的连线完全绕障。本发明方法能够有效绕障并优化线长和最坏负松弛值(Worst Negative Slack，WNS)，从而优化芯片的性能。优化芯片的性能。优化芯片的性能。


技术研发人员：黄兴 於志文 郭斌 刘耿耿 鲁任 何宗易
受保护的技术使用者：西北工业大学
技术研发日：2023.05.16
技术公布日：2023/7/20