第5章

单层绕障X结构


Steiner最小树算法



5．1引言
单层绕障Steiner最小树(Obstacle Avoiding Steiner Minimum Tree，OASMT)的构建方法主要包含4类： 先构造再替换法、不确定性算法、基于生成图的方法、精确算法。先构造再替换法是指先构造连接布线端点的Steiner最小树而不考虑障碍物，之后再将穿过障碍物的边替换为经过障碍物边界的布线边； 不确定性算法采用元启发式策略； 基于生成图的方法一般能够将引脚端点以及部分障碍物端点包含在生成图中从而降低求解空间的复杂度； 精确算法能为绕障布线得到准确的方案。
为求解线长优化能力更强也更具难度的非曼哈顿结构单层绕障布线问题，5．2节~5．4节分别介绍了4种有效的单层绕障X结构Steiner最小树构造算法。
单层绕障X结构Steiner最小树(Obstacle Avoiding Xarchitecture Steiner Minimum Tree，OAXSMT)问题的数学模型可以简化如下： 设P={P1,P2,P3，…,Pn}是线网中的一组引脚，其中每个Pi被赋予其坐标(xi，yi)。设B={B1,B2,B3，…,Bm}是芯片上的一组障碍物，其中每个Bi与两个坐标(xi1，yi1)和(xi2，yi2)相关联。(xi1，yi1)和(xi2，yi2)分别是矩形障碍物的左下角和右上角的坐标。关键的问题是构建一个Steiner树，将所有给定的引脚用0°、45°、90°和135°的线连接起来，绕开所有给定的障碍物并且使成本最小化。应该注意，树可以包括一些pseudoSteiner点。
关于布线结构的λ几何学理论的具体定义已由1．2．1节的定义1．2给出。
定义5．1障碍物在单层绕障X结构Steiner最小树问题中，障碍物可以是任意尺寸的矩形。任意两个障碍物不能互相重叠，但可以点与点接触或是边与边接触。
定义5．2引脚引脚端点可以是在布线区域内的任意端点，不能处于任意障碍内，但可以分布在障碍的边上或是障碍角点处。
定义5．3边界框两个端点pi和pj的边界框是由pi和pj形成的矩形。一组障碍的边界框是完全包含所有障碍物的最小矩形。图5．1显示了两个实例。


图5．1边界框






定义5．4矩形连接模型(RecConnected Model)在布线模型中，如果一个引脚可以通过拐弯不超过一次连接到另一个引脚，并且布线选择仅限于选择2或选择3，将其称为矩形连接模型。如图5．2(a)所示，引脚p可以通过布线区域中的一次选择3与引脚q连接。
定义5．5八角连接模型(OctConnected Model)在布线模型中，如果一个引脚可以通过拐弯不超过一次连接到另一个引脚，并且布线选择仅限于选择0或选择1，将其称为八角连接模型。如图5．2(b)所示，引脚p可以通过布线区域中的一次选择1与引脚q连接。
定义5．6完全连接模型(Fully Connected Model)如果由两个引脚形成的布线模型既是矩形连接模型，也是八角连接模型，将其称为完全连接模型。
定义5．7断开连接模型(Disconnected Model)障碍物的存在可能会阻止某些点被选为pseudoSteiner点。如果一个引脚可以通过拐弯至少两次或更多次来连接到另一个引脚，如图5．2(c)所示，则它形成断开连接模型。


图5．23种连接模型


5．2基于离散粒子群优化的X结构绕障Steiner最小树算法

绕障X结构Steiner最小树问题(Obstacle Avoiding Octagonal Steiner Minimum Tree， OAOSMT)是构造一棵将布线区域上所有给定点及Steiner点连接起来的树，同时以最小代价绕过所有障碍。为了解决这个问题，第一步是构造X结构Steiner最小树。文献［2］提出了一种时间复杂度为O(|V|+|E|)的算法来构造一个与给定的直角结构Steiner树同构的X结构Steiner最小树。其中，|V|和|E|是给定树的顶点和边。在绕障方面，2008年文献［3］提出了一种通过修正构造的方法来解决绕障直角Steiner树(Obstacle Avoiding Rectilinear Steiner Minimum Tree， OARSMT)构造问题，它构建了一个障碍加权生成树在逃逸图上构造OARSMT。文献［4］提出了一种基于迷宫布线的启发式方法来解决OARSMT问题，该方法基于迷宫布线的搜索过程，在解决方案质量和内存空间使用方面都能很好地处理多端线网。2009年，文献［5］的算法改进并扩展了GeoSteiner方法，允许在布线区域内出现直线障碍。该算法可以在合理的时间内生成最优解。与以往的方法不同，文献［6］提出了一种新的算法，首先确定所有引脚的连接顺序，然后用贪心启发式算法迭代连接相邻的两个引脚。文献［7］应用计算几何技术开发了一种高效的算法，该算法可以获得质量优良的解，与之前已知的结果相比，速度有显著提高。然而，上述方法都是基于曼哈顿Steiner树，在布线长度上不能得到很好的优化。
作为一种基于群体的进化方法。由Eberhart和Kennedy在1995年提出的粒子群优化算法(Particle Swarm Optimization， PSO)被证明是一种全局优化算法。PSO具有收敛快、全局搜索、稳定、高效等诸多优点。大量的实践证明，与其他方法相比，粒子群算法能够在全局优化问题上获得代价更低的最优解。
然而，PSO的初始原型用于求解连续优化问题，但自PSO算法提出以来，已有许多工作尝试使用PSO来求解离散问题。例如，文献［9］提出了一种求解TSP的离散粒子群优化（Discrete Particle Swarm Optimization, DPSO）算法。文献［10］提出了一种基于DPSO的X结构Steiner最小树(Octagonal Steiner Minimal Tree， OSMT)算法来优化线长。
本节提出了一种有效的OAOSMT构造算法。它包括以下5个步骤。
(1) 初始化。在该步骤中，有效地生成粒子群，其中每个粒子是连接所有给定引脚的OSMT。
(2) 预处理。在该步骤中，生成包含任何两个引脚的所有连接信息的表，为后续步骤提供快速的信息查询。
(3) 飞行。在此步骤中，通过引入两个新的基于并查集的遗传算子来更新每个粒子。
(4) 调整。在该步骤中，如果需要，调整群体的最终全局最优粒子gf以确保所有边绕开所有障碍。
(5) 精炼。在该步骤中，应用精炼的方法，进一步提高了最终全局最优粒子gf的质量。此外，采用后续处理方法来确保可用于当前的制造技术。
5．2．1算法细节
1． 初始化
为每个引脚和障碍提供唯一的序列号。然后，使用一组最小生成树边来表示候选布线树，并向每个边添加一个额外变量，表示pseudoSteiner点的布线选择，以便随后将其转换为X结构Steiner树。每个pseudoSteiner点的布线选择包括4种类型，如定义2．7~2．10(见2．5．2节)所示。如果网中有n个引脚，则最小生成树将包括n-1个边，n-1个pseudoSteiner点，以及一个额外变量，即粒子的适应度值(见式(5．1))。因此，一个粒子的长度为3(n-1)+1。例如，如图5．3所示，粒子可以表示为以下数字串： 1 3 2 2 3 0 3 4 1 3 5 3 27．3，其中23．7代表粒子的适应度值。前3个数字1 3 2表示一条边，即根据选择2来连接引脚1和引脚3。


 图5．3X结构Steiner树

因为步骤1基于最小生成树(Minimum Spanning Tree， MST)算法，所以可以通过使用一些基于图形的方法(例如，Prim算法或Kruskal算法)或更高效的基于Delaunay三角剖分的算法来轻松获得X结构MST。应当注意，每条边的初始布线方向是从4个给定布线选择中随机选择的，因此可以穿过障碍物。
2． 预处理
根据PSO算法的基本模型，在初始化粒子群后，每个粒子将通过更新其速度和位置来移动，并且整个群体将相互合作以搜索期望的目标。但是，在介绍该粒子更新方法之前，首先描述预处理策略，主要是由于以下3个问题。
第一，在粒子飞行步骤中，当评估刚刚在运动之后生成的粒子时，除了计算每条边的长度之外，还应检查每条边是否避开所有障碍物。然后赋予每个粒子一个适当的适应度值，算法可以选择正确的全局最优粒子gi和个体最优粒子pi。
第二，在操作调整方法之前，必须确定最终全局最优粒子gf的每条边是否绕开所有障碍物。应该决定是否有必要进行调整。如有必要，应该调整哪些边，以及哪些障碍物已经被穿过？应计算所有这些信息。
第三，在精炼过程中，不断改变某些边的路径方向，以尽可能地增加公共边的长度。但是，怎样才能确保调整后的边能够避开所有障碍物？此信息也需要计算。
由于现代芯片的密度急剧增加，问题的规模变得越来越大。如果算法每次计算前面提到的信息，无疑会对整个算法的性能产生负面影响。因此，提出了一种预处理策略，该策略可以通过生成预先计算的查找表来为步骤3~步骤5提供快速信息查询。
预处理策略的想法简单易行。令P={P1,P2,P3，…,Pn}为网络中的一组引脚，并且B={B1,B2,B3，…,Bm}芯片上的一组障碍物。对于每对引脚，例如pi和pj，计算边pipj(c)穿过的障碍物的数量，并记录这些障碍物为集合{Bk}，其中c表示pi和pj之间的布线选择。所有可能的边将构成最终的查找表。图5．4显示了预处理原理。线网中有5个引脚(1~5)，芯片上有6个障碍物(b1~b6)。以引脚1为例，图5．4(a)显示了引脚1与基于选择2和选择3的其他引脚的连接图，而图5．4(b)包括选择0和选择1。可以看出，一些线段穿过障碍物而其他线则没有。基于图5．4，可以容易地生成引脚1的记录。如表5．1所示的引脚的连接信息，很容易查询关于引脚1的所有连接信息。例如，当引脚1基于选择1连接到引脚4时，边穿过障碍物b3和障碍物b4。但是，当引脚1根据选择2连接到引脚3时，就避开了所有障碍物。


图5．4预处理原理



表5．1引脚1的连接信息



引脚
布线选择

0123


2b2—-b2

3b4b4—-

4b3b3,b4b3b3,b4

5b3—b3-

表5．2显示了具有2．9GHz CPU和2GB内存的PC中的查找表生成时间。Pin＃和Obs＃分别代表引脚和障碍物的数量。因为只需要为每组布线数据生成一次查找表，所以在实现实验时只使用传统的数据结构，例如数组。在生成边记录时扫描每个障碍物bk，如果没有bk的角点位于两个针脚的矩形边界框中，那么直接检查下一个障碍物bk+1。此外，45°和135°段的存在无疑会增加问题的复杂性。当输入的比例很大时，可能需要几秒钟，但这是可以接受的。


表5．2查找表生成时间



引脚数/障碍物数CPU时间引脚数/障碍物数CPU时间

10/3210/4310/5025/79

0．000s0．000s0．000s0．000s

33/7110/1030/1050/10

0．000s0．000s0．000s0．000s

70/10100/10100/500200/500

0．000s0．000s0．140s0．578s

200/800200/1000500/1001000/100

0．889s1．139s0．795s3．073s

3． 飞行
1) 粒子的适应度函数
在PSO算法的基本模型中，适应度函数是最重要的组件之一。pi和gi的正确性直接影响适应度函数的准确性。因为优化的目标是线长，所以很明显使用OSMT的总长度作为一个粒子的适应度值是一个很好的选择； 它可以直接反映一个部分的卓越程度。事实上，在定义的OSMT模型中，有3种边，可以定义如下。给定一个布线树Ts和两个引脚p和q，有以下内容。
定义5．8Oseg(p,q)表示p和q之间的边，其不穿过布线平面中的任何障碍物。
定义5．9Dseg(p,q)表示穿过一个或多个障碍物的p和q之间的边，并且可以仅通过改变p和q之间的布线选择来绕开它们。
定义5．10Cseg(p,q)表示穿过一个或多个障碍物的p和q之间的边，但是必须从这些障碍物中选择一些角点以绕开障碍物。
实际上，Cseg(p,q)是断开连接模型，Oseg(p,q)和Dseg(p,q)可能是3个模型中的任何一个。如图5．5(a)所示，A和B之间的边属于Oseg(A,B)，A和D之间的边属于Dseg(A,D)，因为它只能通过改变布线选择来绕开障碍物［即从选择3改为选择1(见图5．5(b)］。A和C之间的边属于Cseg(A,C)，因为必须选择障碍物的角点C1作为中间节点(见图5．5(b))。应该注意，AC1和CC1之间可以有其他布线选择。
定义5．11ADseg(p,q)表示在改变p和q之间的布线选择之后从Dseg(p,q)获得的p和q之间的边，并且避免了所有障碍物。
定义5．12ACseg(p,q)表示在添加障碍物的一个或多个角点之后从Cseg(p,q)获得的p和q之间的一组边，并且避免了所有障碍物。
在图5．5(b)中，A和D之间的边属于ADseg(A,D)。另外，A和C之间的两条边(AC和CC1)属于ACseg(A,C)。假设L(r)等于r的总长度。在前面的定义的基础上，适应度函数如下。
Fitness(P)=(∑Oseg(p,q)L(Oseg(p,q))+∑Dseg(p,q)L(Dseg(p,q))+

∑Cseg(p,q)L(Cseg(p,q)))(5．1)
在式(5．1)中，可以通过查找表容易地识别Oseg(p,q)、Dseg(p,q)、ADseg(p,q)和Cseg(p,q)。对于ACseg(p,q)，其计算类似于调整过程，但只是计算L(ACseg(p,q))的结果而不是实现实际的加法和删除操作。


图5．53种边对应绕障方法


2) 粒子的更新方法
算法5．1显示了粒子更新的伪代码。本节算法具体的更新公式与4．2．2节介绍的更新方式类似，此处不再赘述。
引理5．1假设Cp是粒子p的当前位置，Ap是更新后的位置。Fp是p正在寻找的目标，dis(t)表示位置t和Fp之间的距离。可能存在dis(Ap)＞dis(Cp)。
证明： 很明显，因为更新方法以随机模式操作，所以可能导致p的一些好因素被一些意外因素(线长不减小，反而增加，因为PSO是随机算法)所取代。如图5．6的粒子更新示意图所示，当更新p的速度(见图5．6(a))时，如果选择边2 3 2并由边3 6 3替换，则将获得图5．6(b)。显然，dis(b)> dis(a)。


图5．6粒子更新示意图





算法5．1粒子的更新方法


输入： 惯性权重w，加速因子c1和c2，粒子p，全局(个体) 最优粒子gi(pi)

输出： 新的粒子p

for each particle p in Swarm do

Generates r1=Random(0,1);

if (r1<w) then

mutation operator(p);//变异操作

end if

Generates r2 =Random(0,1);

if(r2<c1) then

crossover operator(p，pi);//交叉操作

end if

Generates r3 =Random(0,1);

if(r3 < c2) then


crossover operator(p，gi);//交叉操作

end if

Update(pi);//更新个体最优粒子pi

end for

Update(gi);//更新全局最优粒子gi

4． 调整
在粒子飞行结束后，选择全局最佳粒子gf作为最终的X结构布线树。粒子gf可能非常优秀，直接避开了所有障碍物。当然，它可能也很糟糕，穿过了许多障碍物。对于后者，当粒子的边pq穿过障碍物时，只有两种可能的场景： Dseg(p,q)和Cseg(p,q)。两者都可以通过表查找直接识别，第一个也可以通过查找表来调整。然而，第二个可能需要更多的技术支持，因此提出这种调整方法。详细步骤如下。
(1) 对于gf的一个边pq，通过查找表来判断是否避开了所有障碍物。如果避开，则重复此步骤以检查下一条边，直到检查完所有的边； 否则，转到步骤(2)。
(2) 通过查找表来检查边pq的选择0和选择1。如果它们中的任何一个可以避开所有障碍物，则用当前布线选择替换原始布线选择； 否则，删除边pq，然后转到步骤(3)。
(3) 通过查找表列出pq贯穿的所有障碍物，并根据p与障碍物中心之间的距离以非递减顺序对这些障碍物进行排序。假设排序列表是Bk={Bk，1,Bk，2,…,Bk，n}和当前起始点s=p，并且当前障碍物B=Bk,j,j=1。
(4) 从B中选择最接近直线sq的角点c。计算sc的连接信息并将该信息添加到查找表中。同时，优先使用选择0和选择1连接sc。然后设置s=c。如果j=n并转到步骤(5)； 否则，重复此步骤，B=Bk,j+1。
(5) 计算sq的连接信息，并将该信息添加到查找表中。然后根据选择0和选择1的标准连接sq。
在这种调整方法中，步骤(2)用于处理Dseg(p，q)，因为它只需要表查找。步骤(3)~步骤(5)用于求解Cseg(p，q)。图5．7是粒子调整示意图，图5．7(a)显示了pq的原始连接图，它穿过障碍物B1和B2。删除边pq后，根据p与B1和B2中心之间的距离，首先检查B1。从图5．7(b)可以看出，c1是与直线pq最近的角点，因此它被选择为中间节点并连接到p。然后检查障碍物B2。在图5．7(c)中，c2连接到c1，因为它是与直线c1q最近的角点。最后，c2连接到图5．7(d)中的q。有3点需要注意。首先，应将新边的所有连接信息添加到查找表中，因为它对精炼策略很有用。其次，步骤(2)仅检查选择0和选择1。即使选择2或选择3可以避免所有障碍物，也不实施替换操作。最后，采用一种策略，其中在步骤(4)和步骤(5)中优选选择0和选择1。虽然这可能在少数情况下获得非最佳结果，但由于精炼策略的存在而无关紧要。


图5．7粒子调整示意图


在以下部分中，假设Rec(p,q)表示使用选择2或选择3时p和q之间的距离。Oct(p,q)表示使用选择0或选项1时的距离，以及L(p,q)表示4个布线选择中的任何一个的距离。
引理5．2假设引脚p和引脚q之间的边形成断开连接模型，并且该边pq穿过障碍物b。为了避开b，将b的一个角点作为中间节点添加会使线长最多增加1．3L~1．6L，其中L是b的边长。
证明： 假设MAX(a)和MIN(a)分别是a的最大值和最小值。在不失一般性的情况下，假设p低于障碍物并且靠近b的左下角，q高于障碍物，并且pq形成断开连接模型。图5．8是引理5．2的实例图，图5．8(a)显示了q在p的左侧的情况，从而可以根据调整方法选择b的左下角和左上角两者作为中间节点。因为两个角点的Rec(p,c)+Rec(c,q)是相同的，所以只给出第一个角点的证明。另一种情况是q位于p的右侧，因此可以选择b的左下角和右上角作为中间节点。图5．8(b)和图5．8(c)分别显示了连接图。对于图5．8(a)，有以下内容。
MAX(1(p,c))+MAX(1(c,q))-MIN(1(p,q))

=Rec(p,c)+Rec(c,q)-Oct(c,q)

=pa+ab+bd+dc+ce+ef+fq-pb-bg-gq

=(pa+ab-pb)+(bd+ce-bg)+dc+(ef-gq)+fq

≈0．6×ad+2×dc<0．3L+L=1．3Lad<L2,dc<L2


图5．8引理5．2的实例


对于图5．8(b)，有以下内容。

MAX(1(p,c))+MAX(1(c,q))-MIN(1(p,q))

=Rec(p,c)+Rec(c,q)-Oct(c,q)

=pa+ac+ce+eg+gh+hq-pa-af-fq

=ac+eg+gh+hq-fq

=ac+gh+(eq+hq-fq)

≈2×gh+0．6×hq<L+0．6L=1．6Lgh<L2,hq<L
对于图5．8(c)，有以下内容。
MAX(1(p,c))+MAX(1(c,q))-MIN(1(p,q))

=Rec(p,c)+Rec(c,q)-Oct(c,q)

=pa+ab+bc+ce+eq-pd-dq

=pa+eq+df-dq

≈pa+eq-0．4fq<L+0．5L=1．5Lgh<L2,hq<L
因此，增加的线长为1．3L~1．6L。对于具有不同p和q位置的其他情况，可以使用类似的证明，因此这里省略它们。

引理5．3如果点c是点p和点q的中间节点，则如果c位于p和q的矩形边界框中，则Rec(p,q)=Rec(p,c)+Rec(c,q)。如果c位于由p和q形成的45°或135°方向形成的平行四边形中，则Oct(p,q)=Oct(p,c)+Oct(c,q)。
证明： 根据p、c和q形成的分段之间的平行关系，可以很容易地得到方程。因此，此处不再赘述。
引理5．4当引脚p和引脚q之间的边形成矩形连接模型并穿过障碍物b时，与仅改变pq的布线选择相比，添加一个角点c作为中间节点可以使线长减少。
证明： 图5．9是引理5．4实例，如图5．9(a)所示，pq贯穿障碍物b。由于边pq形成了一个矩形连接模型，可以通过将pq的布线选择从选择0替换为选择2来绕开障碍物b。但是，如图5．9(b)所示，如果选择c点作为中间节点，将有oct(p,c)≤Rec(p，c)，oct(c，q)≤Rec(c，q)，所以当且仅当p、c和c、q分别共线时，等号成立。根据引理5．3，由于c位于pq的矩形边界框中，因此Rec(p,c)+Rec(c,q)=Rec(p,q)。因此，有Oct(p,c)+Oct(q,c)≤Rec(p,q)。请注意，在最坏的情况下，pc和cq会形成矩形连接模型，因此线长减少为零。


图5．9引理5．4实例


定理5．1使用调整方法可以增加线长或减少线长。
证明： 如上所述，当存在断开连接模型时，线长可能会增加1．3L~1．6L。然而，当存在矩形连接模型时，在引理5．4中已经证明，与边直接避开障碍物的情况相比，线长也可以减小。此外，对于八角连接模型与完全连接模型，如果存在一个穿过障碍物的边，则调整方法将用选择0或选择1来替换原始布线选择。它是p和q之间的最短路径。该策略对于减少线长具有重要意义。
5． 精炼
引理5．1证明了粒子在更新后的位置可能会变差。事实上，粒子以随机模式飞行是PSO算法具有如此强大的搜索能力的主要原因之一。此外，在调整步骤中，优先使用选择0和选择1的规则并不总是有效的，因此获得的结果可能仍然包括或多或少的非最优结构。图5．10是连接子结构的示意图，如图5．10所示(为了简单起见，只给出水平距离大于两垂直距离的两个引脚的图)，p是一个2度引脚，分别连接到引脚q和引脚g。有两条边，每条边有4种布线选择，因此可以得到16个子结构，但只有一个是最优的。假设Hor(p,q)表示p和q之间的水平距离。


图5．10连接子结构的示意图


在图5．11中，Hor(p,q)>Hor(p,g)，s是pq使用选择0时的Steiner点。当g在p和s之间(包括边界)时，最优结构将是pq0 pg3。图5．11是g在q和s的连接示意图。在这种情况下，p和g之间的布线选择取决于实际长度的增加。也就是说，当ge+es＜gd或es＞ed＞0时，pg3将被选择，否则，pg0将被完成。此外，图5．12为一个4度模型，它可以被分成两个2度模型。图5．12右侧的9个结构是最佳结构的候选。


图5．11连接示意图





图5．124度模型


在前面分析的基础上，本节提出了一种基于公共边策略的面向引脚的精炼方法，该方法能够将所有这些非最优结构转换为最优结构，同时绕开所有障碍。具体步骤如下。
(1) 扫描粒子gf的每个边以计数每个端点p的度，同时记录所有连接到p的端点。
(2) 对于每个端点p，如果p的度为d，则枚举p的所有4d的布线选择组合，并选择获得最小适应度值的组合，同时避开所有障碍物。


图5．13示例冲突

在细化过程中，有两点需要注意。首先，关于终端的组合是否避开所有障碍物的问题可以通过查表直接确定，因为在调整过程中添加了障碍物角点的必要连接信息。其次，对于每个绕障组合，为了为整个粒子选择最优组合，可能需要计算整个粒子的适应度值，而不仅仅是组合本身的长度。图5．13显示了一个示例冲突。在计算引脚p的最优组合时，将得到pq0 pg3。然而，当sq>sr+rt时，pq3 fq3才是最佳结果，因此需要从全局角度来决定pq的布线选择。
实际上，图5．14是粒子改进的飞行过程，利用这种改进方法，粒子群不必在飞行步骤期间搜索期望的目标，因此提高了算法的效率。


图5．14粒子改进的飞行过程


算法5．2显示了该改进方法的伪代码。




算法5．2改进方法


输入： 经过调整后的全局最优粒子g′f,引脚总数n

输出： 新的粒子p

Initialize list() to empty; //初始化每个引脚所连接的引脚列表为空

Initialize degree() to zero; //初始化每个引脚的度为0

for each edge l(u,v) of g′f do //粒子g′f中的每条边,u和v是一条边的两个引脚

add u to list(v);

degree(v)+1； 

add v to list(u);

degree(u)+1;

end for

f=Fitness(g′f);

g= g′f;

for each pin p do //对于粒子g′f中的每个引脚p

for each routing combination t of p do //枚举所有编码组合

if check(t)=true then //如果当前的编码组合绕开障碍物或满足松弛条件

replace(g, t); //使用当前编码组合替换原始编码组合

fmid=Fitness(g′f); //更新粒子适应度值

if fmid<f then //如果在当前编码组合下整个粒子gf′的适应度值更小

g′f=g; 

f=fmid; 

else

g= g′f;

end if


end if

end for

end for

degree(p)用于计算p的度，list(p)用于记录与p连接的所有终端，replace(g,t)表示用组合t代替粒子g的相应部分，check(t)表示通过表查找检查组合t的每条边是否绕开了所有障碍物。
5．2．2考虑可制造性的后续操作
到目前为止，已经在全局最优粒子被精炼后获得了优秀的基于X结构的OASMT。但是，应该注意的是，这个基于X结构的OASMT可能包括一些45°角。这些锐角由两个相交的边形成，例如，如图5．15(a)所示，两个边pg0和pq3形成角度θ=45°。考虑到工业生产的实际情况，应该去掉这些45°角，因此提出了一种简单的后续处理方法。
通过分析锐角产生的原因和这些锐角的结构，将它们分为两类。第一个可以通过直接改变两条相交边的一个边的布线选择来解决。图5．15是消除锐角的示意图，以图5．15(a)为例，可以通过改变边pg从选择0到选择3的布线选择来消除锐角。如图5．15(b)所示，得到一个没有锐角的新布线结构。图5．15(c)显示了第二种锐角。仅通过改变一个边的布线选择并不能消除这种锐角，因为这样做会产生交叉或新的锐角。因此，采用一种策略，通过删除边并生成新边来消除锐角。如图5．11(d)所示，通过删除边pq0并生成边pg3，可以成功地移除45°角。当然，也可以删除边gq0并生成新的边gp2以消除这个45°角(见图5．15(e))。应当注意，原始边的布线选择也可以在新生成的结构中改变，并且应该保证新的布线选择避开所有障碍物。很明显，可以通过直接查找表来执行此操作。例如，边pq的布线选择在图5．15(e)中从选择0改变为选择3。因为线长是优化目标，算法将选择具有最短线长的结构。根据精炼过程中degree(p)和list(p)的结果，可以快速识别所有相交的边。在将该后处理方法应用于最终的全局最优粒子gf之后，可以有效地消除所有锐角。


图5．15消除锐角的示意图


算法5．3显示了后处理方法的伪代码。在算法5．3中，change_routing_choice(l)用于改变边l的布线选择并且选择不产生任何锐角的那个，同时实现最短的线长。 Routing_combination(l1,l2)用于计算边l1和l2的布线选择组合，并且在获得最短线长时不获得任何锐角。Select(r1,r2)用于选择r1和r2之间的一个组合，并且必须保证该结果避开所有障碍物且实现更短的线长。从算法5．3中可以看出，首先尝试使用第一种类型的方法然后使用第二种类型的方法去除锐角。注意，可以通过直接查找表来获得边的所有连接信息，因此该过程是有效的。
5．2．3参数策略
性质5．1粒子的局部开发能力和全局探索能力受惯性权重影响。
在PSO算法中，粒子飞行的动力由惯性分量提供，体现了先前速度对飞行轨迹的影响，惯性权重则决定了这种影响程度。较大的惯性权重使粒子能够搜索未知的区域，从而跳出局部极值； 反之，较小的惯性权重使粒子在目前所达区域附近搜索，使算法加速收敛。
文献［15］、［16］中提出了一种基于线性减小惯性权重的PSO算法，并在4种不同的基准函数上进行了仿真实验，实验结果表明这种参数策略能够提高PSO算法的性能。
性质5．2较大的加速因子c1可能使粒子在本地范围内游荡，较大的加速因子c2将使算法过早收敛。
加速因子c1和c2用于粒子之间的通信。在早期使用较大的c1和较小的c2，并在之后进行反转。通过这种方式，该算法将保证在局部范围内进行详细搜索，以避免在早期阶段直接移动到全局最优的位置，并加快后续阶段的收敛。同样地，该算法的实验取得了很好的效果。




算法5．3后处理方法


输入： 最终的全局最优粒子gf

输出： 最终的布线结果

for each pair of intersected edges pg and pq do//对于每对相交的边pg和pq

if intersected_angle(pg，pq)=45° then//若其形成45°角

result1=change_routing_choice(pg);//改变边pg的布线选择并选择不产生锐角的那个

if obstacle_avoiding(result1)=true then //若该结果避开所有障碍物

set result1 as a result; 



continue;

end if

result2=change_routing_choice(pq); //改变边pq的布线选择并选择不产生锐角的
//那个

if obstacle_avoiding(result2)=true then

set result2 as a result; //将其设置为最终布线结果

continue;

end if

generate a new edge gq;//生成一条新的边gq

result3=routing_combination(pg，gq);//计算边pg和gq的布线选择组合

result4=routing_combination(pq，gq); //计算边pq和gq的布线选择组合

fr=select(result3，result4);//选择result3和result4之间的一个组合

set fr as a result; 

end if

end for

5．2．4实验结果
本节算法使用C/C++语言实现，在具有2．9 GHz CPU和2GB内存的PC上进行所有实验。并使用MATLAB来模拟最终的布线图。通常使用多组基准作为绕障问题的测试用例。前5组是Synopsys的工业测试案例。其余的是绕障问题的基准。注意，引脚可以位于障碍物的边界。
表5．3显示了精炼之前和之后线长的比较结果，其中Pin#和Obs#分别表示引脚和障碍物的数量。改进率等于((before-after)/before)×100%。如前所述，粒子群在飞行过程中只需要搜索一个次优结果，然后使用精炼方法得到最优结构。从表5．3可以看出，经过精炼后，线长可以得到0．00%~10．56%的改善，平均改善也可以达到7．93%。
众所周知，这是专门解决基于X结构的单层绕障问题的第一项工作。以往的X结构的研究大多集中在无障碍布线平面上，然后对布线长度或时延进行优化。表5．4显示了线长与λ几何结构的比较，其中列3是通过该算法获得的线长。
与OARSMT(λ=2)相比，线长减少9．61%~48．16%,平均减少25．08%。对于OAOSMT(λ=4)，当问题的规模较小(即只有少数障碍物的小规模网络)时，文献［5］的算法在大多数测试用例中与该结果相似。然而，当问题的规模很大时，特别是当障碍物的数量多于引脚的数量时，由于文献［5］的算法可能会引入一些冗余的角点，该算法具有很大的优势，其中对于具有200个引脚和1000个障碍物的测试用例，最大减少率可以达到42．36％。X架构的平均改进率为16．42％。


表5．3精炼前后的线长比较结果



引脚数障碍数精炼前精炼后优化率/%

10326185629．06

1043972494313．01

10595745740．00

2579112810338．42

33711440128810．56

101026761247177．64

301044822407519．09

501057253520339．12

701061725572507．25

1001080486727389．63

10050085992786438．55

2005001169051055429．72

2008001268201162048．37

20010001231771113859．57

5001001721261575208．49

10001002392312190378．44

均值 7．93



表5．4与λ几何结构算法的线长比较结果



引脚数障碍数本节算法线长
线长线长减少率/%

λ=2λ=4λ=2λ=4


101024717304102727918．729．39

301040751456404122210．711．14

501052033585705243211．160．76

70105725063340576999．610．78

1001072738831507309012．520．48

1005007864314972513545447．4841．94

20050010554218147016276241．8435．16

20080011620420274118205642．6836．17

200100011138521485019322848．1642．36

50010015752019801017649720．4510．75

100010021903725057022275812．581．67

均值25．0816．42

此外，表5．5将所提出的算法的线长与近年来发表的基于直角结构的一些启发式算法(文献［31］、［32］、［11］、［12］、［19］和文献［20］提出的算法)进行了比较，并显示了迄今为止的最佳结果。为了简单起见，在实验表格中按照前面的顺序将对比文献标记为A~F。
2014年，在GPU的帮助下，文献［32］提出了构造OARSMT的并行方法，与之相比得到了-0．60%~6．95%的线长改善，平均线长减少了3．87%，只有一个测试情况更糟(0．60%)。虽然文献［31］的算法提出时间稍早，但在这6篇论文中效果最好。其中一个主要原因是文献［31］的算法提出了一种优秀的4步Steiner点选择方法，该方法能够以令人满意的位置添加Steiner点，从而减少线长。与文献［31］的算法相比，本节算法获得了-0．47%~7．72%的线长改善,平均达到4．23%。此外，从表5．5中可以看出，与C、D、E、F 4种优秀算法相比，本节算法可以获得平均4．55%~6．68%的线长改善。


表5．5与一些直角结构启发式算法的线长比较结果



PBOur_L
线长优化率(X-Our_L)/X/%

［31］A［32］B［11］CX=AX=BX=C


10325626096046047．726．956．95

104394319500960095000．731．760．73

10595746006006004．334．334．33

257910331092109211295．405．408．50

337112881345135313644．244．805．57

1010247172598025980259804．864．864．86

3010407514174041350421102．371．453．23

5010520335550054360560306．254．287．13

7010572506012059530597204．773．834．14

10010727387539074720750003．522．653．02

100500786438134081290812293．323．263．18

2005001055421109521108511107644．884．794．71

200800116204115663115516116047-0．47-0．60-0．14

20010001113851142751132541155932．531．653．64

5001001575201678301669701682806．145．666．34

10001002190372358662348752344167．136．746．56

均值 4．233．874．55

PBOur_L
线长优化率(X-Our_L)/X/%

［12］D［19］E［20］FX=DX=EX=F


103257963663263911．6411．0812．05

1043948996009600100001．761．765．69

10595886136136236．366．367．87

257910851116112111267．447．858．26

337113211364136413795．575．576．60

1010251302598026900275404．868．1210．25

3010409244207042210419303．143．462．81

5010540395463055750541804．756．673．96
续表


PBOur_L
线长优化率(X-Our_L)/X/%

［12］D［19］E［20］FX=DX=EX=F


7010585365927060350590503．415．143．05

10010740637541076330756303．544．713．82

100500786438230083365863814．445．668．96

2005001055421117521132601170935．566．819．86

2008001162041166461187471223060．382．144．99

20010001113851137811161681193082．114．126．64

5001001575201675401706901679785．987．726．23

10001002190372340972366152323816．437．435．74

均值 4．835．916．68

对于运行时间，一方面，与传统的直角结构相比，X结构引入了45°和135°的布线方向。这无疑会增加问题的复杂性。另一方面，由于PSO算法具有非常强的搜索能力，所以使用它来优化线长。但从本质上讲，PSO算法是一种基于群的方法，与普通的启发式方法相比非常耗时。表5．6给出了算法的详细运行时间。第3列显示了预处理时间，可以看到，大多数测试用例只需要不到一秒钟。第4列显示了粒子飞行步骤的运行时间。在这里，有两点要解释。首先，对于所有测试案例，由于在下一步骤中将会使用调整方法和精炼方法，粒子群只需要搜索次优结果，甚至可以包括一些穿过障碍物的边。因此大大减少了搜索时间。其次，当障碍物的数量大于引脚的数量时，很明显会形成许多断开连接模型，因此无论如何增加搜索过程的强度，粒子都无法避开所有障碍物。因此，借助于调整方法仅需要相对少量的搜索时间。表5．6第11行~第14行属于这种类型。第5列描述了有关调整方法的信息，其中null表示最终全局最佳粒子直接避免了所有障碍的情况，即没有用于调整的情况。在a/b中，a是调整的运行时间，b是通过调整选择的角点的总数。可以看出，大多数测试用例选择了几个角点。表5．6第11行~第14行选择更多的角点，因为它们包含更多断开连接模型，因此调整时间也相对较长。第6列是精炼方法的运行时间，这是算法中最耗时的部分。主要原因如下。为了选择一个端点的最佳布线组合，需要计算粒子的适应度值，而不仅仅是绕障组合本身的长度。问题是公共边应该只计算一次，因为由于存在45°和135°段，处理和判断它们需要花费更多的时间。最后一列显示了所提算法的总运行时间，其中超过一半的测试用例可以在一秒内获得很好的结果。对于最后一组测试用例，最长的运行时间是9．329s，但这是一个相当优异的结果。从表5．6可以看出，所有运行时间都是合理且可接受的。


表5．6算法的详细运行时间



引脚数障碍数预处理时间粒子飞行时间调整时间精炼时间合计

10320．000s0．015s0．000s0．015s

10430．000s0．015s0．000s/70．000s0．015s

10590．000s0．015s0．000s0．015s

25790．000s0．015s0．000s/80．000s0．015s

33710．000s0．015s0．000s/190．031s0．046s

10100．000s0．015s0．000s/40．000s0．015s

30100．000s0．015s0．000s/50．000s0．015s

50100．000s0．063s0．000s/40．031s0．094s

70100．000s0．094s0．000s/40．095s0．189s

100100．000s0．172s0．000s/60．083s0．255s

1005000．140s0．016s0．015s/910．385s0．556s

2005000．546s0．016s0．015s/871．373s1．950s

2008000．889s0．032s0．015s/762．015s2．951s

20010001．139s0．078s0．016s/2092．030s3．263s

5001000．795s0．093s0．000s/394．515s5．403s

10001003．073s0．312s0．000s/255．944s9．329s

5．2．5小结
随着制造技术的进步，在X结构模型中可以允许45°和135°对角线段。本节算法提出了一种基于离散PSO在X架构中构建OASMT的有效方法。同时，集成了一些启发式策略和GA算法的两个算子，进一步提高了算法的性能。经过实验证明所提出的算法在合理的运行时间内获得了很好的结果，与基于直角结构的最新成果相比，获得了线长提高3．87％~6．68％。对于X架构，与相关的工作相比较，本节算法平均减少了16．42％的线长。
5．3快速绕障X结构Steiner最小树算法
5．3．1引言
自从1966年人们提出Hanan网格以来，直角Steiner最小树(Rectilinear Steiner Minimum Tree,RSMT)被广泛应用于超大规模集成电路(Very Large Scale Integration,VLSI)的布线问题。另一方面，由于VLSI电路的密度急剧增加，许多可重复使用的组件集成在现代芯片中，例如IP块。在布线过程中无法移动这些组件。因此，在过去的几年中，OARSMT的构建问题得到了广泛的研究。
随着VLSI电路制造技术的进步，X结构布线模型中可以允许45°和135°的斜线段。与传统的直角结构相比，X结构可以极大地优化线长，从而降低了时间延迟、线容量和拥塞的成本。例如，文献［23］提出的X结构Steiner最小树(OSMT)算法显示了其与RSMT相比，通孔数量、总线长和管芯尺寸分别减少了40％、20％和11％。因此，近年来学术界和工业界都致力于使用X结构。
作为一个基本问题，研究人员已经提出了一些用于解决OSMT构造问题的算法。例如，文献［23］和文献［24］提出了构造时间驱动的OSMT算法，其可以显著提高芯片的性能。此外，文献［18］还提出了对应方法来解决λ几何绕障Steiner树构造问题。
本节提出了一种OAOSMT构建算法。主要贡献总结如下： 
(1) 算法生成了两个有关引脚和障碍物的查找表，为整个算法提供了快速的信息查询。
(2) 在快速查表的基础上，提出了一种绕障策略和一种精炼技术。这两种方法都是有效和高效的。
(3) 与以前的算法相比，本节算法的线长和运行时间都是最好的。对科研和工业生产都具有价值。

5．3．2算法框架
图5．16是OAOSMT的构建输入引脚和障碍物。本节算法可以分为以下4个步骤： 


图5．16OAOSMT的构建


步骤1，首先在给定的引脚顶点上构造Delaunay三角剖分(DT)(见图5．16(b))，并构造OFEMST(见图5．16(c))。
步骤2，生成两个查找表，用于记录有关OFEMST边的连接信息。它们可以为第3步和第4步提供快速信息查询。
步骤3，OFEMST首先转换为X结构Steiner树(OST)(见图5．16(d))。然后利用障碍物的一些角生成OAOST。在图5．16(e)中，c1被选择为p1p3之间的中间节点。
步骤4，采用一种能够充分利用共享边原理的精炼技术，来生成最终的OAOSMT(见图5．16(f))。
5．3．3算法细节
1． OFEMST的构建
在无障碍平面上，有许多现有的最小生成树构造算法。本节采用了一种基于DT的策略，首先根据给定的引脚构建DT。然后可以使用Prim或Kruskal算法在O(nlogn)时间内构造OFEMST。之后直接使用文献［25］中的Sweepline算法来构造DT，此处不再赘述。
2． 预查表生成
本节算法计算了OFEMST边在一个X结构平面上的连接信息。在此步骤中生成两个预先计算的查找表。第一种称为边障碍表(EdgeObstacle Table，EOT)，记录每条X结构边穿过的障碍物信息。另一个称为边段表(EdgeSegment Table，EST)，记录每条X结构边的两个线段的坐标信息。
由于OFEMST具有n-1个边，并且每条边具有4个布线选择，因此总共有4(n-1)条X结构边。对于每一条X结构边，记录穿过的障碍物集合。同时，将值设置为这些障碍物的半周长之和。所有4(n-1)条边和其集合构成了最终的EOT。此外，每条边包括两条线段。记录这两个段的坐标。所有X结构边的信息构成最终EST。
查找表生成的伪代码在算法5．4中给出。有两点需要注意。首先，在第3行，对于障碍物b，仅在b的至少一个拐角点与pipj的边界框重叠时检查它。其次，如果存在一个45°或135°段，将其绕原点顺时针旋转45°，形成一个新的水平或竖直段(第9~14行)，然后记录新段的坐标。这有利于总线长和局部线长的计算，因为可以轻松识别公共的45°和135°段，而无须更改线长。




算法5．4查找表生成


输入： OFEMST

输出： EOT，EST

for each edge pipj of OFEMST do

for each routing choice k do

for each obstacle b do //EOT生成

if run_through(pisk，b)=True or run_through(skpj，b)=True then

Lijk =Lijk+semiperimeter(b);//将Lijk值设置为这些障碍物的半周长之和

Add b to {Bijk};//将障碍物b加入pipjk穿过的障碍物集合{Bijk}

end if

end for


if pisk=45° or pisk=135° then//EST生成

Rotate(pisk，45°);//将pisk绕原点顺时针旋转45°

end if

if skpj=45° or skpj=135° then

Rotate(skpj，45°); //将pisk绕原点顺时针旋转45°

end if

record the coordinates of pisk;//记录新段pisk的坐标

record the coordinates of skpj;//记录新段skpj的坐标

end for

end for

3． 绕障策略
1) OST生成
在该步骤中，基于查找EOT，将OFEMST转换为OST，细节如下。
检查OFEMST的每条边pipj。如果X结构的边pipj0或pipj1可以避开所有障碍物，直接将pipj2的布线选择设置为选择0或选择1； 否则，如果pipj2或pipj3可以避开所有障碍物，仍然设置(根据Lij0和Lij1的值)选择0或选择1。如果所有4个布线选择都通过障碍物，那么选择具有最小Lijk的布线选择。应该注意的是，所有判断都可以通过直接查找EOT来执行。因此，这个过程非常快。OST生成的伪代码在算法5．5中给出。




算法5．5OST生成


输入： OFEMST，EOT

输出： OST

for each edge pipj of OFEMST do

if {Bij0}= then //如果X结构的边pipj0可以避开所有障碍物

pipjk= pipj0;//将pipj的布线选择设置为选择0

end if

else if{Bij1}= then //如果X结构的边pipj1可以避开所有障碍物

pipjk= pipj1; //将pipj的布线选择设置为选择1

end if

else if{Bij2}= or {Bij3}= then//如果pipj2或pipj3可以避开所有障碍物

//根据Lij0和Lij1的值设置选择0或选择1

if Lij0<= Lij1then

pipjk= pipj0;

else


pipjk= pipj1;

end if

else//如果所有4个布线选择都通过障碍物

select min(Lijt), t=0,1,2,3;//选择具有最小Lijt的布线选择

pipjk= pipjt;

end if

end for

2) OAOST生成
显然，OST的某些边可能会穿过障碍物。因此，提出了一种绕障方法来帮助这些边绕开障碍。算法5．6中显示了OAOST生成的伪代码。




算法5．6OAOST生成


输入： OST，EOT

输出： OAOST

for each edge pipjk of OST do

if {Bijk} ≠  then //如果边pipjk穿过了障碍物

delete(pipjk);//删除pipjk

sort({Bijk});//根据Dis(pi，o)按非递减顺序对{Bijk}进行排序，o是障碍物的中心点

end if

s=pi;//设起点为pi

for each obstacle b in {Bijk} do//逐一检查障碍集中的障碍物

c=select_corner(b);//从当前障碍物中选择一个拐点c

add sc to EOT and EST;//计算边sc的连接信息，并将这些信息添加到EOT和EST中

connect s with c;//将s连接到c

s=c;//用c替换s作为当前起点

end for

add spj to EOT and EST;//计算边spj的连接信息，并将这些信息添加到EOT和
//EST中

connect s with pj;//将最后一个选定的拐点s连接到pj

end for

对于OST的每条边pipjk(k是OST中的布线选择)，如果它穿过了障碍物，则直接删除pipjk，并根据Dis(pj，o)按非递减顺序对障碍物集{Bijk}进行排序，其中o是障碍物的中心点。然后设起点s为pj。对于已排序的集合{Bijk}，逐一检查这些障碍物。从当前障碍物中选择一个拐点c，它是最接近直线spj的。然后计算边sc的连接信息，并将这些信息添加到EOT和EST中。将s连接到c后，用c替换s作为当前起点，并继续检查下一个障碍物，直到最后一个选定的拐点连接到pj。

这种绕障方法可以操作多次，直到所有的边都绕开所有的障碍物。图5．17展示了一个简单绕障实例。图5．17(a)是原始边p1p2，它穿过障碍物B1和B2
({B123}={B1，B2})。删除边p1p2后，由于Dis(p1，o1)<Dis(p1，o2)，首先检查B1。由于c1是B1与直线p1p2最接近的拐点，因此选择它作为中间节点并连接到p1(见图5．17(b))。然后检查B2。在图5．17(c)中，由于c2是与直线c1p2最近的拐点，所以c2连接到c1。最后，在图5．17(d)中，c2连接到p2。注意，新边的所有连接信息都应该添加到EOT和EST，因为它们对于精炼是有用的。


图5．17绕障实例


4． 精炼
事实上，对于任何一个引脚，其互连总是存在一个最佳结构。图5．18显示了具有2度端点p3的一个示例，其中p1和p2连接到p3。在不损失一般性的情况下，假设两个引脚之间存在Δx>Δy。由于每个边有4个布线选择，总共有16个子结构。但当p2在s1和p3之间时，其中s1是边p1p2的pseudoSteiner点，则图5．18(a)是p3的唯一最佳结构。当p2在p1和s1之间(见图5．18(b))时，如果p2e+es1<p2d或es1>ed，则图5．18(c)成为最佳结构； 否则，图5．18(d)是最佳的。障碍物存在的平面也遵循类似的原理。但是最佳结构可能成为16个子结构中的任意一个。例如，如图5．18(e)所示，p2只能通过选择3连接到p3。因此，图5．18(e)成为最佳结构之一。


图5．18精炼实例


基于上述分析，提出了一种精炼技术(见算法5．7)。通过扫描OAOST的边一次，首先计算每个引脚pi的度，并将连接到pi的引脚记录为列表。然后计算每个引脚pi的最佳结构(osi)。假设pi的度为d。列举了pi的所有4d个布线选择组合，并选择了具有最小线长的且绕障的那一个作为osi。此外，计算每个osi的公共边(sei)的长度。接着根据sei的值按降序对所有引脚进行排序。最后，根据已排序的引脚列表将每个引脚的osi 应用于原始的OAOST，直到确定了所有OAOST边的布线选择。




算法5．7精炼


输入： OAOST，EOT，EST

输出： OAOSMT

for each edge pipjk of OAOST do

degree(pi)=degree(pi)+1;//计算每个引脚pi的度

degree(pj)=degree(pj)+1;//计算每个引脚pj的度

add pj to list(pj);//将连接到pj的引脚记录为列表

add pi to list(pi);//将连接到pi的引脚记录为列表

end for

//计算每个引脚pi的最佳结构osi

Initialize each length(osi)=+∞;

for each terminal pi of OAOST do

for each substructure st of pi do//对于pi的所有布线选择组合

if obstacleavoiding(st)=True and length(st)<length(osi) then

osi=st;//选择具有最小线长的且绕障的那一个作为osi

end if

end for

sei=length_shared_edges(osi);//计算每个osi的公共边的长度sei

end for

sort({P}) in decreasing order according sei;//根据sei的值按降序对所有引脚进行排序

for each terminal pi of OAOST do

apply osi to OAOST;//将每个引脚的osi应用于原始的OAOST

if all edges of OAOST have been decided then //直到确定了所有OAOST边的布线选择

break;

end if

end for

有两点需要注意。首先，可以通过直接查找表来确定布线选择组合是否避免所有障碍(第10行)。其次，如果已经确定了OAOST边的布线选择，则即使当前osi对该边具有不同的选择，也不会改变它(第18行)。
定理5．2该算法的最坏时间复杂度为O(nm)，其中n和m分别是引脚和障碍物的数。
5．3．4实验结果
所有算法都已用C语言实现和执行，实验在具有2．9GHz CPU和2GB存储器的PC上进行。IND1~IND5是Synopsys的工业测试用例。RC01~RC12是绕障问题的基准。目前解决单层OAOSMT问题的唯一相关工作是文献［18］提出来的，是为λ几何问题设计的。此外，还有近年来文献［31］、［32］、［12］所提出的OARSMT构建算法。表5．7显示了本节算法与其他算法的线长比较结果。


表5．7与其他算法的线长比较结果



测试用例引脚数障碍物数本节算法

线长
线长优化率/%

文献［18］
λ=4文献［32］文献［18］
λ=4文献［32］


IND11032569—609—6．57

IND210439549—9500—-0．52

IND31059575—600—4．17

IND425791070—1092—2．01

IND533711378—1345—-2．45

RC0110102508427279259808．053．45

RC0230103948841222417404．215．40

RC035010541775243255500-3．332．38

RC047010599885769960120-3．970．22

RC05100107283373090753900．353．39

RC06100500780791354548134042．204．01

RC0720050010595016276211095234．904．51

RC0820080011394318205611566337．411．49

RC09200100011125819322811427542．422．64

RC1050010015632917649716783011．436．85

RC1110001002169372227582358662．618．03

RC12100010000703669156417076212455．017．67

均值 19．293．52续表


测试用例引脚数障碍物数本节算法

线长
线长优化率/%

文献［18］
λ=4文献［32］文献［18］
λ=4文献［32］


IND110325696046395．7910．95

IND210439549950010000-0．524．52

IND310595756006234．177．70

IND425791070112911265．234．97

IND53371137813641379-1．030．01

RC0110102508425980275403．458．92

RC0230103948842110419306．235．82

RC0350105417756030541803．310．00

RC047010599885972059050-0．45-1．59

RC05100107283375000756302．893．70

RC061005007807981229863813．889．61

RC072005001059501107641170934．359．52

RC082008001139431160471223061．816．84

RC0920010001112581155931193083．756．75

RC105001001563291682801679787．106．93

RC1110001002169372344162323817．566．65

RC121000100007036697569988426897．0416．50

均值 3．806．34

表5．7中第4列是本节算法的线长，与文献［18］所提算法相比，当问题的规模较小时(即只有几个障碍的小规模网络)，文献［18］所提算法具有与本节算法相似的平均表现(RC01~RC05)。而在大规模的用例中，即在引脚数大于70的线网中，本节算法的线长优化能力比文献［18］的算法优秀很多，最大减少了55．01％的线长。平均改善率也可达到19．29％。与文献［32］相比，该算法产生的线长优化提高了-0．52％~8．03％，平均减少了3．52％，只有两个测试用例比它差。此外，该算法平均比文献［31］所提算法优化3．80%，比文献［12］所提出的算法优化6．34%。
该算法在实际问题上的处理速度非常快。有3个主要原因。首先，步骤3、4中使用的查找表的方法只需要O(1)的复杂度。其次，因为步骤1生成MST，两个引脚的矩形边界框很小，除非它们彼此非常远。因此，在步骤2和步骤3中不需要检查大多数的障碍物。最后，对于步骤3中的OAOST生成，只需要检查穿过障碍物的边。在表5．8中提供与其他算法的运行时间对比。最后一行中的值是标准化结果。与文献［18］的算法相比，本节算法快了5．93倍。此外，比文献［32］的算法快42倍，比文献［12］的算法快11．92倍。特别是，文献［31］提出的算法实现了4种算法中最快的运行时间。与之相比，本节算法的平均速度依然提高了2．35倍。


表5．8与其他算法的运行时间对比



测试用例
CPU时间/s

文献［18］λ=4文献［32］文献［31］文献［12］本节算法


IND1—0．050．000．010．00

IND2—0．060．000．010．00

IND3—0．050．000．010．00

IND4—0．090．000．020．00

IND5—0．080．000．020．00

RC010．000．050．000．010．00

RC010．000．060．000．010．00

RC030．000．070．000．010．00

RC040．010．060．000．020．00

RC050．010．090．000．020．00

RC060．070．380．030．130．02

RC070．080．310．030．150．02

RC080．120．460．050．270．03

RC090．160．610．060．360．03

RC100．030．200．020．080．02

RC110．050．340．030．140．03

RC123．0321．781．195．880．45

合计3．5624．741．417．150．60

比率5．9342．232．3511．921．00

5．3．5小结
本节提出了一种高效、有效的OAOSMT构建算法。经过多组标准测试用例的测试，实验结果表明，本节设计的算法在线长和运行时间均取得了最佳效果。它在VLSI布线过程中非常实用和有效。未来的工作可能集中在三维绕障问题上。
5．4X结构绕障Steiner最小树四步启发式算法
表5．9和表5．10给出了本节的主要符号的描述和主要缩写的描述。


表5．9主要符号的描述



符号描述

n引脚顶点的数量

m障碍物的数量

pi第i个引脚的序列号 
bi第i个障碍物的序列号
续表


符号描述

pipjk当使用布线选择k时，引脚pi和pj的X结构边

piskpipjk的第一个线段

skpjpipjk的第二个线段

rec(pi,pj)pipj2或pipj3的线长

oct(pi,pj)pipj0或pipj1的线长

dis(pi,pj)引脚pi和pj的欧氏距离

{Bijk}pipjk穿过的障碍集

box(t)t的直角边界框

sp(t)t的半周长

Lijkbox({Bijk})的半周长

len(pi,pj)引脚pi和pj的绕障线长

osi引脚pi的最优拓扑结构

seiosi的公共边长度



表5．10主要缩写的描述



缩写描述

SMTSteiner最小树

OSTX结构Steiner树

OSMTX结构Steiner最小树

RSMT直角结构Steiner最小树

OAOST绕障X结构Steiner树

OAOSMT绕障X结构Steiner最小树

OARSMT绕障直角结构Steiner最小树

OFEMST不考虑障碍的欧氏最小生成树

DT德劳内三角剖分

MST最小生成树

HPWL半周长线长

EOT边障碍表

EST边段表

TDST二维线段树


图5．19是OAOSMT四步启发式算法实例。输入引脚和障碍物如图5．19(a)所示。有4个引脚和4个障碍物。算法可以分为以下4个步骤。
步骤1，OFEMST构建。在此步骤中，OFEMST用于构造X结构Steiner树(OST)的初始解，因为它可以很容易地生成并转换为OST。首先在给定的引脚顶点上构造DT(见图5．19(b))。然后使用Kruskal算法生成OFEMST(见图5．19(c))。


图5．19OAOSMT四步启发式算法实例


步骤2，查找表生成。在此步骤中，将生成两个查找表，用于记录有关OFEMST边的连接信息。两个表都可以为整个算法提供信息支持。
步骤3，绕障策略。在此步骤中，OFEMST首先根据表查找转换为OST(见图5．19(d))。然后选择布线平面上的一些点作为pseudoSteiner点以生成OAOST。在图5．19(e)中，s1和c1被选择为p1和p3之间的两个pseudoSteiner点，并且s2和c2被选择为p1和p4之间的两个pseudoSteiner点。

步骤4，精炼。在该步骤中，采用包括3种策略的精炼方法，即冗余pseudoSteiner点消除、pseudoSteiner点连接优化和布线选择优化，来生成最终的OAOSMT。例如，通过共享s3和p1之间的布线路径并移除冗余的pseudoSteiner点s2，图5．19(e)中的OAOST被转换为图5．14(f)中的OAOSMT。

图5．20是OAOSMT四步启发式算法流程图。本节根据框架按顺序给出了所提算法的细节。


图5．20OAOSMT四步启发式算法流程图


5．4．1算法细节
1． OFEMST的构建
OFEMST通常用于在无障碍平面上构建OST的初始骨架，因为它可以很容易地生成并转换为OST，所以首先研究OFEMST构造问题。有许多现成的OFEMST构造算法。文献［18］使用绕障约束DT(ObstacleAvoiding Constrained Delaunay Triangulation,OACDT)来构造绕障MST(OAMST)算法。因为OACDT包含至少一个OAMST并且仅具有O(n)个候选边，因此，本节首先根据给定的引脚构建DT，然后可以使用Prim或Kruskal算法在O(n)时间内构造OFEMST。由于文献［25］的扫描线算法是Voronoi图(Voronoi Diagram,VD)构造中的一种非常成熟的技术，在此步骤中直接使用它来构造VD，然后通过将VD转换为对偶图来生成DT。
2． 查找表的生成
在此步骤中生成两个预先计算的查找表： 第一种称为边障碍表(EOT)，记录每条边穿过的障碍物信息； 另一个称为边段表(EST)，记录每条边的两个线段的坐标信息。
由于OFEMST具有n-1条边，并且每条边具有4个布线选择，因此总共有4(n-1)条边。对于每一条边pipjk，记录一个集合{Bijk}作为pipjk穿过的障碍物。同时，计算每个{Bijk}的边界框，并将Lijk值设置为该边界框的HPWL。所有4(n-1)的{Bijk}和Lijk构成了最终的EOT。此外，每条边pipjk包括两条线段(pisk和skpi)。记录这两个段的坐标。注意，对于45°和135°的线段，绕原点顺时针旋转45°然后记录新段的坐标。所有4(n-1)的边的信息构成最终EST。
具体步骤如下。
(1) 初始化t=1。
(2) 检查OFEMST的第t条边pipj。针对每个布线选择k计算两条分段pisk和skpj的起始坐标和结束坐标。
(3) 对于每个活动障碍物Bp(0 <p<m)，如果pisk和skpj穿过Bp，则将Bp添加到相应的集合{Bijk}。
(4) 计算每个{Bijk}的Lijk。然后将Lijk和{Bijk}记录到EOT中。
(5) 检查每个pisk和skpj。如果它是45°或135°段，顺时针旋转45°形成一个新的水平段或竖直段。
(6) 将每条pisk和skpj的坐标记录到EST中。然后t=t+1；  如果t<n，则返回步骤(2)。否则，退出该过程。
有两点需要注意。首先，在步骤(3)中，对于障碍物Bp，仅在Bp与边界框重叠时检查它。该障碍物也称为“活动障碍物”。 图5．21是片段旋转的实例，例如，如图5．21(a)所示，对于边p1p2，只有两个引脚顶点p1和p2； b2、b6和b7是3个活动障碍物； 其余障碍物则不需要检查，因为不可能与边p1p2的任何布线选择相交。由于二维线段树(TwoDimensional Segment Tree,TDST)通常用于记录平面区域的一些属性信息，为了以有效的方式找到给定引脚对的有效障碍物集，采用TDST来组织所有障碍物。更具体地，TDST的外部线段树用于组织水平轴上的间隔，内部分段树用于组织竖直轴上的间隔。另外，根据5．1节中描述的问题模型，每个障碍物Bp具有唯一的序列号p； 因此，对于构造的TDST的任何一个区域，如果该区域被障碍物Bp覆盖，则将序列号p添加到该区域。这样，在将所有障碍物添加到TDST的相应区域之后，最终的TDST将包含关于整个布线平面上的障碍物的所有信息，并且当给出一对引脚顶点pi和pj时，可以通过查询pipj的边界框所覆盖的区域快速找到所有活动的障碍物。注意，一旦构建了TDST，它就不需要更新，并且可以为算法的所有后续步骤提供活动障碍物查询。由于线段树通常是完整的二叉树，因此每个操作都可以在对数时间内完成，例如，插入和查询。其次，对于步骤(5)中的45°或135°段采用旋转调整为水平或竖直方向。例如，如图5．21(c)所示，有4个45°段p1p2、p3p4、p5p6和p7p8。在计算线长时，需要同时考虑所有4个45°段的位置，并且路径p2p3和p6p7应仅计算一次，因为两者都是公共边。由于实际电路的输入规模可能非常大，在布线平面中可能存在相当多的45°段，并且需要相对更多的计算量来获得这些公共边(如果考虑所有可能的45°段对的位置，最坏情况下它可以达到二次复杂度)。但是，如果事先将所有45°段绕原点顺时针旋转45°，则可以轻松计算所有公共边，因为所有生成的段都是水平的(见图5．21(c))，如果两个45°段具有公共边，那么两个生成的水平线段必须具有相同的y坐标； 通过这种方式，可以首先根据其y坐标对这些旋转的段进行排序，然后通过仅扫描已排序的段一次来计算公共边的长度(排序过程主导此过程； 它可以在O(eloge)时间内完成，其中e是45°段的数量)。135°段的旋转具有类似的原理。


图5．21线段旋转


ynew=22×(yi-xi)
xnew1=22×(xi+yi)
xnew2=22×(xj+yj)(5．2)


xnew=22*(xi+yi)
ynew1=22*(yi-xi)
ynew2=22*(yj-xj)(5．3)
假设vi(xi,yi)和vj(xj,yj)是45°或135°段的两个端点。式(5．2)用于将45°段旋转到水平段，其中ynew是新段的y坐标，xnew1和xnew2分别是两个新端点的x坐标。类似地，式(5．3)用于将135°段旋转到竖直段，其中xnew是新段的x坐标，ynew1和ynew1分别是两个新端点的y坐标。
对于EOT和EST生成，将图5．21(b)作为一个简单的例子。在一般情况下，假设在X结构布线平面中存在两个引脚p1(3,4)和p2(5,3)以及7个障碍(b1~b7)。显然，在这个例子中，OFEMST只包含一条边p1p2。表5．11显示了EOT和EST的生成示例。


表5．11EOT和EST的生成示例



EOTEST

{B120}={b2},L120=sp(b2)p1s0{(3,4),(4,4)}
s0p*2{(42,-2),(42,0)}

{B121}={b2,b7},L121=sp(box({B121}))p1s*1{(7/2,-2/2),(7/2,2/2)}

s1p2{(4,3),(5,3)}

{B122}={b7},L122=sp(b7)p1s2{(3,4),(3,3)}

s2p2{(3,3),(5,3)}

{B123}={b2,b6},L123=sp(box({B123}))p1s3{(3,4),(5,4)}

s3p2{(5,4),(5,3)}


可以快速查询有关OFEMST的所有连接信息。例如，从表5.11可以看出，边p1p21穿过障碍物b2和b7。两条分段p1s1和s1p2的坐标分别为{(7/2,-2/2)、(7/2,2)/2}和{(4,3),(5,3)}。
应该注意的是，p1s*1表示p1s1旋转后的线段坐标。另外，如果一条边pipjk可以避开所有障碍物({Bijk}=)，那么Lijk=0。如果pipjk只穿过一个障碍物b({Bijk}={b})，则Lijk直接设置为b的HPWL。否则，如果pipjk经过多个障碍物，例如，p1p21通过图5．21(b)中的b2和b7({Bijk}={b2,b7})，则L121设置为边界框的HPWL({B121})，等于bl1+bl2，如图5．21(b)中实线矩形框所示。
两个查找表的功能可以总结如下。
(1) 在绕障策略中，转换过程可以根据EOT提供的信息有效地执行。
(2) 在精炼过程中，基于EOT和EST可以有效地计算各个端点的最优结构。此外，通过查找表，可以获得所需的关于冗余pseudoSteiner点消除和pseudoSteiner连接优化过程的所有连接信息。
(3) 利用EST可以有效地计算局部和全局的线长。
3． 绕障策略
1) OST生成
在该部分中，基于查找EOT，将步骤1中生成的OFEMST转换为OST。
检查OFEMST的每条边pipj。如果边pipj0或pipj1可以避开所有障碍物，直接将pipj的布线选择设置为选择0或选择1。否则，如果pipj2或pipj3可以避开所有障碍物，仍然设置(根据Lij0和Lij1的值)选择0或选择1。如果所有4个布线选择都通过障碍物，选择具有最小Lijk的布线选择。应该注意的是，所有判断都可以通过直接查找EOT来执行。因此，这个过程非常快。OST生成的伪代码在算法5．8中给出。




算法5．8OST生成


输入： OFEMST，EOT

输出： OST

for each edge pipj of OFEMST do

if {Bij0}= then //如果X结构边pipj0可以避开所有障碍物

pipjk=pipj0;//将pipj的布线选择设置为选择0

end if

else if {Bij1}= then //如果X结构边pipj1可以避开所有障碍物

pipjk=pipj1; //将pipj的布线选择设置为选择1

end if

else if{Bij2}= or {Bij3}= then//如果pipj2或pipj3可以避开所有障碍物

//根据Lij0和Lij1的值设置选择0或选择1

if Lij0<= Lij1then

pipjk=pipj0;

else

pipjk=pipj1;

end if

else//如果所有4个布线选择都通过障碍物

select_min(Lijt), t=0,1,2,3;//选择具有最小Lijt的布线选择

pipjk=pipjt;

end if

end for

具体步骤如下。

(1) 初始化t=1。
(2) 对于OFEMST的第t条边pipj，检查选择0和选择1； 如果它们中的任何一个可以避免所有障碍物，那么将pipj的布线选择设置为当前的布线选择。重复此步骤以检查第(t+1)条边，直到t+1≥n； 否则，转到步骤(3)。
(3) 如果选择2或选择3可以避免所有障碍物，请转到步骤(4)； 否则，转步骤(5)。
(4) 如果Lij0<Lij1，则将pipj的布线选择设置为0。否则，将其设置为选择1，然后t=t+1； 如果t<n，转到步骤(2)； 否则，退出流程。
(5) 选择最小的pipj(k=0,1,2,3)，并将pipj的布线选择设置为选择k。然后t=t+1；  如果t<n，转到步骤(2)； 否则，退出流程。
步骤(2)采用策略，在OST生成过程中优先选择0和选择1(见定理5．3)。另外，步骤(3)和步骤(4)意味着即使选择2或选择3可以绕开障碍物，仍然选择布线选择0或选择1作为结果(见定理5．4)。
定理5．3对于任意两个端点pipj，相比于rec(pi,pj)，oct(pi,pj)可使线长减少(2-22)×min(Δx,Δy)。
证明： 假设Δx<Δy，oct(pi,pj)=Δy-Δx+2×Δx，并且rec(pi,pj)=Δx+Δy。这样，rec(pipj)-oct(pipj)=(2-22)×Δx。对于Δx>Δy的情况也可同样证明。
引理5．5c是边pipj的中间节点，则rec(pi,pj)=rec(pi,c)+rec(c,pj)，当且仅当cbox(pi,pj)。
引理5．6c是边pipj的中间节点，然后oct(pipj)=oct(pi,c)+oct(c,pj),当且仅当cpara(pipj)，其中para(pipj)是由pi和pj形成的具有45°或135°方向的平行四边形。
根据pi，c和c，pj形成的分段之间的平行关系，可以很容易地实现引理5．5和引理5．6中的等式。因此，这里省略了证明过程。
定理5．4对于每条边pipj，如果{Bij0}≠且{Bij1}≠，但{Bij2}≠或{Bij2}≠，则在框({Bij0})或框({Bij1}的边界上选择一些pseudoSteiner点作为中间节点可以使线长减少(2-2)×min(Δx,Δy))。
证明： 图5．22是定理5．4实例，{Bij0}={Bij1}={b1，b2}，但{Bij2}=。但是，如图5．22(b)所示，如果选择pseudoSteiner点c作为中间节点，将得到oct(pj,c)≤rec(pj,c)和oct(c,pj)≤rec(c,pj)，当且仅当pi、c和pj共线时，等式才成立。根据引理5．5，如果cbox(pipj)，则rec(pj,c)+rec(c,pj)=rec(pi,pj)。因此，有oct(pi,c)+ oct(c,pj)≤rec(pipj)。最好情况下，根据定理5．3得到(2-2)×min(Δx,Δy)×(oct(pi,c)+oct(c,pj))=rec(pipj)。
注意，在最坏的情况下，pic和cpj都可以通过仅使用选择2或选择3来避免所有障碍，然后线长减小为零。


图5．22定理5．4实例


2) OAOST生成
显然，根据OST生成方法，OST的某些边可能会穿过障碍物。实际上，可以通过直接查找EOT来识别这些边。但它可能需要更多的技术支持以绕开障碍物。因此，提出了一种pseudoSteiner点选择方法，它可以有效地帮助所有边绕开障碍物。
参照图5．23(a)所示的每个点p，将平面划分为8个区域； 每个区域不包括图5．23(b)所示的两条边界线。显然，图5．23(a)中的每条边界线(d1~d8)是布线平面中点p的合法布线路径。
在选择pseudoSteiner点之前，首先扫描OST的所有边，对于每条边pipjk(k是OST中的布线选择)； 如果xi>xj，则改变点pi和pj的位置，即将pipjk变换为pipjk*，其中相应的k*值如图5．23(c)所示。这样，对于每条边，可以确保起点位于终点的左侧，从而简化了边的可能场景。在变换之后，当检查边pipjk时，只需要考虑点pi的X形分区的右半轴和点xj的X形分区的左半轴。
接下来，检查转换后的OST的每条边pipjk； 如果它穿过了障碍物，则直接删除pipjk，并计算{Bijk}的直线边界框bx。然后沿着5个方向将pi投影到它的右半轴。图5．23是合法路径划分这5个方向，包括图5．23(a)中的d1~d5。假设pidx和bx之间的第一个交点是tx(x=1，2，3，4，5)； 应该注意，tx可能不存在，因为pidx没有与bx相交。此外，计算直线pidx和pipj之间的角度ax，然后选择具有最小ax的tx作为pseudoSteiner点，因为s可能不能直接连接到pi，所以需要选择更多的pseudoSteiner点，以便pi和pj可以连接。为了实现这个目标，检查bx的每个拐角点cy(y=1，2，3，4)，并选择一个使得rec(s，cy)+rec(cy,pj)最小且具有较大的rec(s,cy)的拐点作为另一个pseudoSteiner点c。最后，计算边pis、sc和cpj的连接信息，并将这些信息添加到EOT和EST中。此时，可以通过直接查找表来生成边pisk1、sck2和cpjk3。
考虑到集合{Bijk}的障碍物可能在布线平面中广泛分散，在这种情况下，pi和pj之间新生成的布线路径可能很长，因为它沿着{Bijk}的边界框绕行。因此，为了确保高布线质量，在以下两种情况下采用其他pseudoSteiner点选择策略。
(1) 两个选定的pseudoSteiner点之间的布线路径穿过障碍物。
(2) 如果将pi和pj之间新生成的路径的长度除以rec(pi，pj)并且得到的值大于β(在实验中β设置为2)。然后，根据pi与障碍物之间的距离按递增顺序对{Bijk}的所有障碍物进行排序，并根据上述投影方法按顺序选择每个障碍物上的pseudoSteiner点。以这种方式，生成可以从{Bijk}的大边界框逃逸的绕障路径。
OAOST生成技术的详细步骤如下。
(1) 对于OST的每个边pipjk，如果xi>xj，则将pipjk变换为pipjk*。
(2) 初始化t=1。
(3) 对于变换后的OST的第t个直线边pipjk，如果它穿过障碍物，则转到步骤(4)。否则，继续检查第(t+1)个边沿，直到t+1≥n。
(4) 删除边pipjk。计算bx=box({Bijk})。沿d1~d5投影pi并计算每个pidx(x=1,2,3,4,5)和bx之间的第一个交点tx。
(5) 计算每个pidx和直线pipj之间的角度ax。然后选择具有最小ax的tx作为 pseudoSteiner点s。


图5．23合法路径划分


(6) 从bx中选择一个角点c，使rec(s,cy)+rec(cy,pj)最小，其中cy是bx的第y个角点，y=1,2,3,4。
(7) 计算边pis、sc和cpj的连接信息，生成边pis、sc和cpj。
(8) 如果(len(pi,s)+len(s,c)+len(c,pj))/rec(pi,pj)>β或边穿过障碍物，则对{Bijk}排序，并按顺序在每个障碍物上选择pseudoSteiner点，并生成从pi到pj的新路径。
引理5．7对于OST的边pipjk，如果{Bijk}≠，则投影(pi)∩box({Bijk})≠或投影(pj)∩box({Bijk})≠，其中投影(pi)和投影(pj)分别是pi和pj沿其5个方向在其半轴上的投影。
3) 证明
使用归谬法来证明这个引理。图5．24是引理5．7实例，图5．24(a)和图5．24(b)分别显示了根据定义的pi和pj的半轴。如果投影(pi)∩box({Bijk})=，则box({Bijk})必须完全位于pi右半轴的一个区域。类似地，如果投影(pj)∩box({Bijk})=，则box({Bijk})必须完全位于pj的左半轴的一个区域中。因此，如果投影(pi)∩box({Bijk})=和投影(pj)∩box({Bijk})=都是真的，那么在不失一般性的情况下，假设边界框({Bijk})Ri(Ri∈{R1,R2,R3,R4} of pi)和box({Bijk})Ri(Ri∈{R5,R6,R7,R8}of pj)，Ri和Rj的两个边界线必须形成一个合法的X结构布线路径，这意味着pi和pj可以直接连接而不会遇到任何障碍，这是矛盾的。例如，如图5．24(c)所示，pi的框({Bijk})R和pj的框({Bijk})R7，pi和pj可以通过路径pis1pj或pis2pj连接。


图5．24引理5．7实例


上面已经指出tx可能不存在，因为pidx在步骤(4)中不与bx相交。因此，可能存在所有5个交叉点tx都不存在的情况。在这种情况下，根据引理5．7，将沿着图5．24(a)中的5个方向(d1，d5~d8)将pj投影到其左半轴。此外，由于没有考虑其他障碍物，pi和pj之间新生成的路径仍可能遇到障碍。因此，这种OAOST生成技术可以多次操作，直到所有的边都避开所有障碍物。幸运的是，当新生成的路径穿过障碍物时，这些障碍物的直角边界框的至少两个边界通常被限制在一定范围内。例如，如图5．24(d)所示，pi和pj通过选择3连接，并且它穿过box1，s和c被选为两个pseudoSteiner点。由于已经确保s和c之间的路径可以避开所有障碍，因此只有路径pis和cpj仍然穿过障碍物。假设box2是路径pis穿过的障碍物的边界框。box2的底部必须位于pis2上方，box2的右侧受box1右侧的限制。box3也受pis2和box1的限制。显然，这种情况可以在恒定的时间内解决。其他3个选择遵循类似的原则。类似地，当在每个障碍物上选择pseudoSteiner点时，新生成的路径的边界框也在至少两个方向上受到限制。它也可以在恒定的时间内解决。应该注意，该OAOST生成过程也会生成冗余的pseudoSteiner点。
以图5．25作为一个简单的例子来进一步解释这个过程。图5．25是OAOST构建实例，图5．25(a)是原始布线图，其中p1p2穿过障碍物b1、b2和b3(即{B120}={b1，b2，b3})。删除边p1p2后，首先计算框({B120})； 结果bx在图5．25(b)中用实线矩形框显示。然后沿着它的5个方向投射p1。很明显，p1d1和p1d5不与bx相交，因此，p1沿其5个方向投射得到与bx的交叉点集T1={t2，t3，t4}。接下来，计算直线p1p2和p1的每条投影线之间的角度，得到a2=∠d2p1p2、a3=∠d3p1p2、a4=∠d4p1p2。因为a4<a3<a2，所以选择t4作为 pseudoSteiner点s。在图5．25(c)中，检查了bx的4个角点； 有rec(sc2)+rec(c1p2)=rec(sc2)+rec(c2p2)<rec(sc3)+rec(c3p3)=rec(sc4)+rec(c4p2)，因为rec(sc1)<rec(sc2)，c2被选为另一个pseudoSteiner点。最后，计算并记录边p1s、sc2和c2p2的连接信息到EOT和EST中。最终的边可以通过表查找生成(见图5．25(d))。注意，生成的OAOST可能包括一些有进一步优化的空间的布线路径。


图5．25OAOST构建实例


4． 精炼
由于生成的OAOST可能仍然包括一些次优的布线路径，因此在该部分中，提出了3种精炼策略以进一步减少线路长度。
1) 冗余pseudoSteiner点消除
在OAOST生成过程中，可以根据OAOST生成方法引入一些冗余的pseudoSteiner点。例如，如图5．19(e)所示，对于边p1p41，选择s2和c2作为两个pseudoSteiner点。但是，s2是多余的，因为p1和c2可以直接连接，而len(p1s2)+ len(s2c2)>len(p1c2)，因此，s2被删除，并且p1连接到图5．19(f)中所示的c2。为了消除这些冗余点，在OAOST中扫描每个选定的pseudoSteiner点s并检查它的两条边pisk1和spjk2，如果pipj可以直接连接并且len(pis)+len(spj)≥len(pipj)，删除pseudoSteiner点s和相关边pisk1和spjk2，然后将pi连接到pj。注意，原始边pisk1和spjk2的连接信息可以通过查找表来获得，因此，这个过程也非常快。
2) pseudoSteiner点连接优化
尽管OAOST生成技术可以使OST边避免所有障碍物，但pseudoSteiner点之间的布线路径可能不够好。例如，图5．25(d)中s和c2之间的布线路径可以进一步优化，因为在障碍物的直角边界框中存在一些未使用的布线资源。当然，如果OST边仅穿过一个障碍物，或者在每个障碍物上选择了pseudoSteiner点，则所选择的pseudoSteiner点之间的布线路径没有优化空间。另一方面，如果两个选定的pseudoSteiner点共线，则最佳布线路径是直线，并且也不能优化。因此，对于任何一对pseudoSteiner点，如果可以进一步优化，它至少应满足两点：
(1) 原始OST边穿过多个障碍物，并且在边界上选择pseudoSteiner点；
(2) 两个选定的pseudoSteiner点不共线。
对于这种pseudoSteiner点，使用一种称为滑动的操作来尝试减少线长。由于两个选定的pseudoSteiner点位于直角边界框的两侧，因此必须在此边界框的两侧存在合法的布线路径。另外，边界框的两侧必须与至少一个障碍物线接触。图5．26是对pseudoSteiner点连接优化，如图5．26(a)所示，pi和pj之间的边穿过障碍物b1、b2和b3。根据OAOST生成技术，选择点s和角c2作为两个pseudoSteiner点。在这种情况下，s和c2只能通过选择3连接。此外，b1、b2和b3分别与t1t2、t4t5和c2t3之间的直角框线接触。然而，如果沿着s和c2之间的布线路径滑动两个pseudoSteiner点并且在线接触的障碍角t5处停止每个点，则t5是距离原始pseudoSteiner点最远的一个。然后，这两个角可以通过选择0或选择1连接，因为可以使用未使用的布线资源。例如，将s滑动到t2和c2到t5，然后t2和t5可以形成一个边t2t50。因此，与先前的结果相比，线长减小。图5．26(b)显示了图5．25(d)中的结果优化后的布线图。当然，当两个所选择的t5之间存在其他障碍物，或者这两个tis彼此重叠时，也没有优化线长的空间。


图5．26pseudoSteiner点连接优化


3) 布线选择优化
除了前两点，还没有考虑一个重要问题，即公共边。换句话说，可以进一步优化所获得的布线树。对于OAOST的任何一个引脚pi，其互连至少有一个最佳结构。
通过只讨论2度引脚，其他度的引脚遵循相似的原理。由于每条边有4个布线选择，对于一个2度引脚，总共有16个子结构。图5．27(a)显示了无障碍平面中的2度端点p3，其中p1和p2连接到p3。在不失一般性的情况下，假设两个引脚之间存在Δx>Δy。图5．27是布线选择优化的实例，当p2在s1和p3之间时，其中s1是边p1p31的pseudoSteiner点，图5．27(a)是p3的唯一最佳结构。当p2在p1和s1之间(见图5．27(b))时，如果p2e+es1<p2d或es1>ed，则图5．27(c)成为最佳结构。否则，图5．27(d)是最优的。障碍物存在的平面也遵循类似的原理。但是由于障碍物的存在，最优结构可能成为16个子结构中的任意一个。例如，如图5．27(e)所示，p2只能通过选择3连接到p3。因此，图5．27(e)是存在障碍物时的最佳结构。当然，p1也可以通过图5．27(e)中的选择0连接到p3。总之，无论引脚有几度，其互连至少有一个最佳结构。


图5．27布线选择优化实例


基于这一事实，提出了一种面向引脚的布线选择优化方法。首先，计算每个引脚pi的度以及与其连接的引脚列表。之后算法计算每个引脚pi的最佳结构(osi)，即pi所有布线选择组合中具有线长最佳同时满足绕障的子结构。此外，计算每个osi的公共边(sei)的长度最后，根据sei的值按降序对所有引脚进行排序，并用各引脚的osi代替其原来的布线选择组合，以构建OAOST。详细步骤如下。
(1) 扫描OAOST的边以计算每个引脚pi的度，并同时记录连接到pi的引脚作为列表。
(2) 对于每个引脚pi，如果pi的度数是d，则枚举pi的所有4d的布线选择组合。然后选择具有最小线长的且避开所有障碍物的那一个组合作为osi，同时计算每个osi的sei。
(3) 根据sei按递减顺序对OAOST的所有引脚进行排序。
(4) 对于每个引脚pi按顺序，将osi的布线选择组合应用于OAOST，直到所有OAOST边都已确定。
有两点需要注意,第一，在步骤(2)中，可以通过直接查找EOT来确定布线选择组合是否避免所有障碍物。第二，在步骤(4)中，当前osi不能改动之前已调整过的子结构。此外，可以通过直接查找EST来计算局部线长和总线长。
5．4．2复杂性分析
定理5．5该算法的时间复杂度为O((m+n)logxmlogym+nmlogm)，其中n和m分别是布线平面的顶点数和障碍物数，xm和ym分别是布线平面的最大x坐标和y坐标。
证明：  在步骤1中，可以在O(nlogn)时间中生成DT。然后可以使用Kruskal算法在O(n)时间生成OFEMST，因为DT中只有O(n)个边。
在步骤2中，TDST可以以m×(logxmlogym)时间构造。其中包括两个for循环，由于有n条边，所以O(n)支配第一个循环。对于第二个循环，其时间复杂度为常数4，即布线选择的数量。并且第二个循环内的每个查询都可以在O(logxmlogym)时间内执行。因此，步骤2的时间复杂度为O((m+n)*(logxmlogym))。
在步骤3中，OST生成需要O(n)时间，因为存在n个边并且表查找仅需要O(1)时间。对于OAOST生成过程，外部for循环由n控制。对于每个OST边，如果它穿过障碍物，在最坏情况下找到边界框需要O(m)时间。如果在每个障碍物上选择pseudoSteiner点，则对障碍物排序主导该过程，在O(mlogm)时间内完成执行。此外，当生成新路径的连接信息时，每个查询需要O(logxmlogym)时间。因此，步骤3的时间复杂度是O(n×(mlogm+logxmlogym))。
在步骤4中，由于存在n条边并且需要计算新边的连接信息，冗余pseudoSteiner消除和pseudoSteiner连接优化都需要O(n(logxmlogym))时间。在布线选择优化过程中，扫描OAOST的每条边需要O(n)时间。当计算每个引脚pi的osi时，两个for循环分别由n和4d支配。另外，所有引脚都可以使用快速排序算法在O(nlogn)时间内进行排序。而将每个引脚的最优结构应用于OAOST也需要O(n)时间，因此，布线选择优化由O(nlogn)支配。步骤4的时间复杂度是O(n(logxmlogym+logn))。
总之，在最坏情况下，该算法的时间复杂度是O((m+n)logxmlogym+nmlogm)。
5．4．3实验结果
所有算法都已用C语言实现和执行。此外，MATLAB被用于模拟最终的布线图。实验在具有2．9GHz CPU和2GB存储器的PC上进行。共有17个基准电路。ind1~ind5是Synopsys的工业测试用例。rc01~rc12是绕障问题的基准。另外，一些随机生成的电路用于进一步测试所提出的算法的可扩展性。在所有这些测试案例中，引脚和障碍物的数量分别为10~1000和10~10 000。
1． 精炼策略的有效性
精炼过程对于算法的最终布线质量非常重要。它通过尽可能多地增加公共边的线长来构建最终的OAOSMT，同时充分利用布线资源生成更多的对角线段。为了研究优化线长的精炼过程的有效性，通过比较使用该方法之前和之后的线长来说明精炼的效果。表5．12显示了精炼前后的线长比较结果。从表5．12可以看出，在使用精炼后可以实现2．74％~9．76％的线长减小。此外，平均线长减少也可达到6．16％。


表5．12精炼前后的线长比较结果



测试用例引脚数障碍物数精炼前精炼后优化率/%

ind110325845682．74

ind210431006695485．15

ind310596015744．49

ind42579117910699．33

ind53371140213344．85

rc01101027716250849．50

rc02301043758394889．76

rc03501056048541773．34

rc04701064011596436．82

rc051001079844727388．90

rc0610050083842775927．45

rc072005001135281054807．09

rc082008001229171131107．98

rc0920010001200481106427．84

rc105001001613461555793．57

rc1110001002221322164012．58

rc121000100007268377025443．34

均值6．16

2． 与最好的OAOSMT算法对比
到目前为止，文献［28］的算法是解决OAOSMT问题的最佳方案。其提出了一个基于PSO的框架，可以在合理的时间内产生出色的OAOSMT。为了验证OAOSI构造的快速四步启发式算法（a Fast FourStep Heuristic for ObstacleAvoiding Octilinear Steiner Tree Construction,FHOAOS）的有效性，将本节算法与文献［28］提出的算法在上述基准电路中进行了比较，表5．13显示了两个算法的线长和运行时间的比较结果。从实验数据可以观察到，当输入电路的规模很大时(即具有许多障碍的较大规模网)，FHOAOS产生了更好的结果。例如，对于测试用例rc06~rc12，FHOAOS的线长小于文献［28］的线长。此外，从表5．13可以看出，与文献［28］相比，可以减少-4．18％~3．10％的线长。平均而言，FHOAOS的表现与文献［28］中所述表现相当。FHOAOS的线长仅比文献［28］提及的线长长0．36％。分析这个结果主要有两个原因。第一，当输入电路的规模很小时(即只有少量障碍物的小规模网络)，文献［28］可以通过适度增加PSO算法的迭代次数来搜索出色的结果，同时保持合理的运行时间。此外，文献［28］引入了两个遗传算法的算子，可以进一步提高PSO算法的搜索能力。第二，当输入电路的规模变大时，如果在文献［28］中适度增加迭代次数，效果有限。如果在文献［28］中大大增加迭代次数，虽然它可能会得到很好的结果，但运行时间将变得不可接受； 因此，需要在线长和运行时间之间进行折中。
表5．13的第7列和第8列中提供了两种算法的运行时间。尽管文献［28］的算法得到的线长结果看起来相当不错，但其运行时间并不令人满意。这主要是由于该算法的性质，它是一种基于粒子群的算法，需要更多的迭代次数来搜索解空间。此外，文献［28］的算法中候选边数量是O(n2)。因此，它需要更多的时间来计算这种边信息。表5．13的最后一行在FHOAOS上标准化。可以看出，FHOAOS算法速度很快。例如，rc12包括1000个引脚顶点和10 000个障碍物，FHOAOS能在仅仅0．41s内产生很好的效果，而文献［28］的算法需要13．12s。平均而言，FHOAOS比文献［28］的方法快66．39倍。因此在工业生产中更实用。


表5．13与文献［28］的线长和运行时间的比较结果



测试用例引脚数障碍物数线长

FHOAOS［28］

优化率/%
CPU时间/s

FHOAOS［28］


ind11032568562-1．070．000．02

ind2104395489431-1．240．000．02

ind310505745740．000．000．02

ind4257910691033-3．480．000．02

ind5337113341288-3．570．000．05

rc0110102508424717-1．340．000．02

rc02301039488407513．100．000．02

rc0350105417752033-4．120．000．10

rc0470105964357250-4．180．000．17

rc051001072738727380．000．000．26

rc0610050077592786431．340．020．57

rc072005001054801055420．060．021．91

rc082008001131101162042．660．032．93

rc0920010001106421113850．070．033．20

rc105001001555791575201．230．025．42

rc1110001002164012190371．200．039．33

rc121000100007025447244253．020．4113．12

均值(优
化率(%))
/合计(时间)-0．360．5637．18

比率(时间)-1．0066．39

3． 与λGeometry算法对比
下面对FHOAOS与文献［18］提出的λ几何算法进行比较。根据定义，当λ设置为2时，文献［18］的算法可以生成OARSMT； 当λ设定为4时，文献［18］的算法可以生成OAOSMT。表5．14显示了线长和运行时间的比较结果。可以看出，FHOAOS优于文献［18］所提出的算法。对于λ=2的所有测试用例，平均线长减少可达到27．83％。另外，对于λ=4的情况，当问题的规模很小时，文献［18］具有与该算法相似的表现(rc01~rc05)。然而，当问题的规模很大(rc06~rc12)时，特别是当障碍物的数量大于引脚数时，本书算法具有显著的优势，线长减少-3．37％~55．09％。平均改善率也可达到19．53％。换句话说，文献［18］算法生成的最终布线树相对较差，主要原因是文献［18］的算法可能会引入更多的冗余点，以及文献［18］的布线树不能尽可能地共享相同的布线路径。此外，最后3列显示了两种算法的运行时间。可以看出，FHOAOS比文献［18］的算法平均快5．79倍和6．34倍(当λ=2,λ=4时)。很明显，文献［18］的算法比文献［28］的算法在运行时间方面好。但是，对于最终布线树的质量，文献［28］的算法比文献［18］的算法好。因此，FHOAOS弥补了文献［18］和文献［28］两个算法的缺点。


表5．14与文献［18］的线长和运行时间的比较结果



测试

用例引脚数障碍
物数FHOAOS

［18］优化率/%CPU 时间/s

λ=2λ=4λ=2λ=4FHOAOSλ=2λ=4


rc01101025084304102727917．518．050．000．000．00

rc02301039488456404122213．484．210．000．000．00

rc0350105417758570524327．50-3．330．000．000．01

rc0470105964363340576995．84-3．370．000．000．01

rc051001072738831507309012．520．480．000．000．01

rc061005007759214972513545448．1842．720．020．060．07

rc0720050010548018147016276241．8735．190．020．060．08

rc0820080011311020274118205644．2137．870．030．100．12

rc09200100011064221485019322848．5042．740．030．130．15

rc1050010015557919801017649721．4311．850．020．030．03

rc11100010021640125057022275813．642．850．030．043．03

rc121000100007025441723990156417059．2555．090．412．823．03

均值 27．8319．530．563．243．55

比例 1．005．796．34

4． 与最新的3个OARSMT算法对比
为了进一步验证这一事实，即与直角结构相比，X结构对于线长优化有巨大的优势，在这一部分将本文算法与近年来提出的3种最新的OARSMT算法进行了比较。表5．15显示比较结果。表5．15的第4列显示了本节算法的线长。文献［32］是最新的关于OARSMT文献，它提出了借助GPU的并行方法，并以有效的方式取得了巨大的成果。与此并行算法相比，线长优化提高了-0．51％~8．25％，平均减少了3．96％，只有一个测试用例(ind2)比它差。此外，本节算法比文献［31］的算法优4．23%，比文献［12］的算法优6．77%。虽然45°和135°布线方向的引入增加了问题的复杂度，但本节算法也比OARSMT算法更快。在表5．15中提供不同算法的运行时。可以看出，与OARSMT算法相比，比文献［32］的算法快44．18倍，比文献［12］的算法快12．77倍。文献［31］提出的算法实现了3种算法中最快的运行时间，因为它是基于预计算的查找表的算法。与之相比，本节算法的平均速度依然提高了2．52倍。
此外，为了进行各方面一一对应的比较，尝试通过对FHOAOS进行以下更改来生成OARSMT。首先，从整个算法中删除选择0和选择1。因此，算法的步骤3将生成的OFEMST转换为直角Steiner树(RST)。然后从布线平面中选取一些pseudoSteiner点，生成OARST。应该注意，在步骤3中，布线平面参照每个点p被划分为4个直角区域(即，图5．24的d1、d3、d5和d7是可用方向)。其次，pseudoSteiner点连接优化过程基于X结构，因此变得不可用，在布线选择优化过程中每个点只应考虑直角组合。此外，由于只有直线路径，冗余pseudoSteiner点消除也不能减少线长，这是因为它被设计成尽可能用合法的X结构边来代替冗余直角边。可以看出，在选择0和选择1被删除之后，精炼过程几乎没有效果。这主要是因为X结构和直角结构的优化技术不是通用的。例如，文献［30］算法中的边替换法和“U形图案细化”法被广泛用于优化直角结构，但不适用于X结构。
表5．15为与3个文献的算法关于线长和运行时间的比较结果，可以看出，FHOAOS的性能平均比文献［32］的算法差2．66%，比文献［31］的算法差2．38%，比文献［12］的算法优0．36%。此外，对于VLSI布线的另一个重要指标，即运行时间，FHOAOS仍然具有巨大的优势。FHOAOS比文献［31］、［32］、［12］的算法分别快2．52倍、44．18倍和12．77倍。


表5．15与3个文献的算法关于线长和运行时间的比较结果



测试
用例引脚数障碍
物数线长

FHOAOS［32］
优化率/%
CPU时间/s

FHOAOS［32］


ind11032568(618)6096．73(-1．48)0．00(0．00)0．05

ind210439548(9800)9500-0．51(-3．16)0．00(0．00)0．06

ind31050574(613)6004．33(-2．17)0．00(0．00)0．05

ind425791069(1146)10922．11(-4．95)0．00(0．00)0．09

ind533711334(1412)13450．82(-4．98)0．00(0．00)0．08

rc01101025084(27630)259803．45(-6．35)0．00(0．00)0．05

rc02301039488(43290)417405．40(-3．71)0．00(0．00)0．06

rc03501054177(56940)555002．38(-2．59)0．00(0．00)0．07

rc04701059643(61990)601200．79(-3．11)0．00(0．00)0．06

rc051001072738(75685)753903．52(-0．39)0．00(0．00)0．09

rc0610050077592(84662)813404．61(-4．08)0．02(0．02)0．38

rc07200500105480(113598)1109524．93(-2．38)0．02(0．02)0．31

rc08200800113110(119177)1156632．21(-3．04)0．03(0．02)0．46

rc092001000110642(117074)1142753．18(-2．45)0．03(0．02)0．61

rc10500100155579(167219)1678307．30(0．37)0．02(0．01)0．20

rc111000100216401(234107)2358668．25(0．75)0．03(0．02)0．34

rc12100010000702544(775263)7620897．81(-1．73)0．41(0．36)21．78

均值(优化率/%)/合计(时间)3．96(-2．66)0．56(0．47)24．74

比率(时间)—1．00(1．00)44．18(52．64)续表


测试
用例引脚数障碍
物数
线长优化率/%CPU时间/s

［31］［12］［31］［12］［31］［12］


ind110326046395．96(-2．32)11．11(3．29)0．000．01

ind21043950010000-0．51(-3．16)4．52(2．00)0．000．01

ind310506006234．33(-2．17)7．87(1．61)0．000．01

ind42579112911265．31(-1．51)5．12(-1．78)0．000．02

ind53371136413792．20(-3．52)3．26(-2．39)0．000．02

rc01101025980275403．45(-6．35)8．92(-0．33)0．000．01

rc02301042110419306．23(-2．80)5．82(-3．24)0．000．01

rc03501056030541803．31(-1．62)0．00(-5．09)0．000．01

rc04701059720590500．13(-3．80)-1．00(-4．98)0．000．02

rc051001075000756303．02(-0．91)3．82(-0．07)0．000．02

rc0610050081229863814．48(-4．23)10．17(1．99)0．030．13

rc072005001107641170934．77(-2．56)9．92(2．98)0．030．15

rc082008001160471223062．53(-2．70)7．52(2．56)0．050．27

rc0920010001155931193084．28(-1．28)7．26(1．87)0．060．36

rc105001001682801679787．55(0．63)7．38(0．45)0．020．08

rc1110001002344162323817．69(0．13)6．87(-0．74)0．030．14

rc121000100007569988426897．19(-2．41)16．63(8．00)1．195．88

均值(优化率(%))/合计(时间)4．23(-2．38)6．77(0．36)1．417．15

比率(时间) -—2．52(3．00)12．77

(15．21)

5． 与最优的OARSMT算法对比
文献［33］中提出的算法是一种精确的算法，它可以通过在障碍物中连接完整的Steiner树来构建最优的OARSMT。表5．16展示了与文献［33］的算法得到的线长和运行时间的比较结果。表5．16第4列显示，FHOAOS平均优于文献［33］的方法2．35％。这些结果进一步证明，对于降低VLSI设计中的布线成本，X架构具有很大的优势。此外，第6列显示FHOAOS比文献［33］的方法快267387．53倍，这主要是因为文献［33］的方法具有指数最坏情况时间复杂度。


表5．16与文献［33］的算法的线长和运行时间的比较结果



测试用例线长

FHOAOS文献［33］
优化率/%
CPU时间/s

FHOAOS文献［33］


ind15686045．960．000．11

ind295489500-0．520．000．25

ind35746004．330．000．19

ind4106910861．570．000．87

ind5133413410．520．001．09

rc0125084259803．450．000．16
续表


测试用例线长

FHOAOS文献［33］
优化率/%
CPU时间/s

FHOAOS文献［33］


rc0239488413504．500．000．52
rc035417754160-0．030．000．68

rc045964359070-0．970．000．95

rc0572738740701．800．001．31

rc0677592797142．660．02335

rc071054801087403．000．02541

rc08113110112564-0．490．0324170

rc091106421110050．330．0314174

rc101555791641505．220．02176

rc112164012308376．250．03706

均值(优化率(%) )/合计(时间)2．350．1540108．13

比率(时间)—1．00267387．53

6． OSMT生成的比较
OSMT可视为OAOSMT的特例，实际上，FHOAOS可以生成OSMT而无须任何修改。在删除障碍后，本节算法对现有的基准测试进行了实验。如表5．17所示，将结果与文献［28］的算法进行比较，其中FHOAOS*表示使用精炼方法之前的线长。表5．17是与文献［28］的算法的关于线长和运行时间的比较结果可以看出，精炼方法平均减少了1．79％的线长。此外，本节的线长结果也优于文献［28］的算法。与文献［28］的算法相比，本节算法可以实现-2．19％~1．87％的线长减小，平均线长减少为0．27％。在运行时间方面，本节算法比文献［28］的算法快201．38倍。


表5．17与文献［28］的算法的关于线长和运行时间的比较结果



测试

用例引脚数障碍

物数FHOAOS

线长优化率/%CPU时间/s

FH
OAOS*文献［28］FH
OAOS*文献［28］FH
OAOS文献［28］


ind110325635785592．60-0．720．000．01

ind210438814883888140．270．000．000．01

ind310505475595472．150．000．000．01

ind425799559759632．050．830．000．01

ind533711152116311470．95-0．440．000．02

rc0110102409824311241230．88-0．100．000．01

rc0230103573436450362031．961．300．000．01
续表


测试

用例引脚数障碍

物数FHOAOS

线长优化率/%CPU时间/s

FH
OAOS*文献［28］FH
OAOS*文献［28］FH
OAOS文献［28］


rc0350104855349816488192．540．540．000．07

rc0470105173752992506272．37-2．190．000．13

rc05100106781469358691052．231．870．000．20

rc061005007224773479729961．681．030．000．22

rc0720050098341100137975411．79-0．820．001．02

rc082008001012391030021014791．710．240．001．23

rc09200100098724100193997741．471．050．001．37

rc105001001500801527131514431．720．900．022．29

rc1110001002148412194842140732．12-0．360．034．35

rc121000100006981647121547079931．961．390．035．15

均值(优化率(%))/合计(时间)1．790．270．0816．11

比率(时间)—-1．00201．38

7． 随机生成电路及仿真结果实验
此外，为了研究本节算法的可扩展性，还测试了一些随机生成的具有额外障碍的情况。在这些情况下，障碍物的数量远远超过引脚的数量。这些情况更类似于实际布线应用程序，例如详细布线或工程更改指令布线。如表5．18的仿真实验结果所示，本节算法可以为所有测试用例高效地生成OSMT和OAOSMT。


表5．18仿真实验结果



测试用例引脚数障碍物数
线长CPU时间/s

OSMTOAOSMTOSMTOAOSMT


random110500171023200．000．01

random25050041948460130．000．01

random3100500708482350．000．02

random410010007190122330．000．03

random5200200040257500370．000．13

5．4．4小结
随着VLSI制造技术的快速发展，在一条直线布线平面上可以允许45°和135°的对角线段。本节基于X结构设计了一种高效的绕障算法，即OAOSMT和OSMT构造的快速四步启发式算法。与几种最先进的算法相比，实验结果表明，本节算法在线长和运行时均取得了很好的效果，在VLSI布线过程中非常实用和有效。
5．5本章总结
本章主要介绍了4种有效的单层绕障X结构Steiner最小树构造算法。首先，由于离散粒子群在全局优化问题上的独特优势能够使布线结果有着较好的优化，本章基于离散粒子群优化算法构造X结构Steiner最小树； 其次，介绍了快速绕障来构造X结构Steiner最小树以及提出了一种高效、有效的OAOSMT构建算法； 最后，介绍了四步构建算法： OFEMST的构建、查找表的生成、绕障策略、精炼。本章通过实验展示了所提出算法的有效性，对未来的研究提供了新的思路以及方向。
参 考 文 献


［1］Coulston C S. Constructing exact octagonal Steiner minimal trees［C］//Proceedings of the 13th ACM Great Lakes symposium on VLSI.2003：  16.

［2］Chiang C,Chiang C S.Octilinear Steiner tree construction［C］//The 2002 45th Midwest Symposium on Circuits and Systems，2002.MWSCAS2002.IEEE，2002，1：  I603.

［3］Chang Y T,Tsai Y W，Chi J C，et al.ObstacleAvoiding rectilinear steiner minimal tree construction［C］//2008 IEEE International Symposium on VLSI Design，Automation and Test(VLSIDAT).IEEE，2008：  3538.

［4］Li L，Young E F Y.Obstacleavoiding rectilinear Steiner tree construction［C］//2008 IEEE/ACM International Conference on ComputerAided Design.IEEE，2008：  523528.

［5］Li L，Qian Z,Young E F Y.Generation of optimal obstacleavoiding rectilinear Steiner minimum tree［C］//2009 IEEE/ACM International Conference on ComputerAided DesignDigest of Technical Papers.IEEE，2009：  2125.

［6］Chuang J R,Lin J M.Efficient multilayer obstacleavoiding preferred direction rectilinear Steiner tree construction［C］//16th Asia and South Pacific Design Automation Conference(ASPDAC 2011).IEEE，2011：  527532.

［7］Liu C H,Chen I C，Lee D T.An efficient algorithm for multilayer obstacleavoiding rectilinear Steiner tree construction［C］//Proceedings of the 49th Annual Design Automation Conference.2012：  613622.

［8］Eberhart R,Kennedy J.A new optimizer using particle swarm theory［C］//MHS′95.Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Ieee，1995：  3943.

［9］Clerc M. Discrete particle swarm optimization，illustrated by the traveling salesman problem［M］//New optimization techniques in engineering.Springer，Berlin，Heidelberg，2004：  219239.

［10］Liu G，Chen G,Guo W.DPSO based octagonal steiner tree algorithm for VLSI routing［C］//2012 IEEE Fifth International Conference on Advanced Computational Intelligence(ICACI).IEEE，2012：  383387.

［11］Lin C W,Chen S Y，Li C F，et al.Obstacleavoiding rectilinear Steiner tree construction based on spanning graphs［J］.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2008，27(4)：  643653.

［12］Long J，Zhou H,Memik S O.EBOARST：  An efficient edgebased obstacleavoiding rectilinear Steiner tree construction algorithm［J］.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2008，27(12)：  21692182.

［13］Liu C H，Yuan S Y,Kuo S Y，et al.An O(n log n) pathbased obstacleavoiding algorithm for rectilinear Steiner tree construction［C］//Proceedings of the 46th Annual Design Automation Conference.2009：  314319.

［14］Liu C H，Yuan S Y,Kuo S Y，et al.Obstacleavoiding rectilinear Steiner tree construction based on Steiner point selection［C］//2009 IEEE/ACM International Conference on ComputerAided DesignDigest of Technical Papers.IEEE，2009：  2632.

［15］Shi Y，Eberhart R C. Parameter selection in particle swarm optimization［J］.In： Porto V.W.，Saravanan N.,Waagen D.,Eiben A.E.(eds) Evolutionary Programming VII.Lecture Notes in Computer Science 1998,447： 591600.

［16］Shi Y，Eberhart R C. Empirical study of particle swarm optimization［C］//Proceedings of the 1999 Congress on Evolutionary ComputationCEC99(Cat.No.99TH8406).IEEE，1999，3：  19451950.

［17］Ratnaweera A,Halgamuge S K，Watson H C.Selforganizing hierarchical particle swarm optimizer with timevarying acceleration coefficients［J］.IEEE Transactions on evolutionary computation，2004，8(3)：  240255.

［18］Jing T T，Feng Z,Hu Y,et al.λOAT：  λGeometry ObstacleAvoiding Tree Construction With O(nlogn) Complexity［J］.ComputerAided Design of Integrated Circuits and Systems，IEEE Transactions on，2007，26(11)： 20732079.

［19］Liu C H,Yuan S Y，Kuo S Y，et al.Highperformance obstacleavoiding rectilinear steiner tree construction［J］.ACM Transactions on Design Automation of Electronic Systems(TODAES)，2009，14(3)：  45.

［20］Liu C H,Kuo S Y，Lee D T，et al.Obstacleavoiding rectilinear Steiner tree construction：  A Steinerpointbased algorithm［J］.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2012，31(7)：  10501060.

［21］Hanan M.On Steiner’s problem with rectilinear distance［J］.SIAM Journal on Applied Mathematics，1966，14(2)：  255265.

［22］Teig S L. The X architecture：  Not your fathers diagonal wiring［C］//Proceedings of the 2002 international workshop on Systemlevel interconnect prediction.2002：  3337.

［23］Huang H H,Chang S P，Lin Y C，et al.Timingdriven nonrectangular obstaclesavoiding routing algorithm for the Xarchitecture［C］//WSEAS International Conference.Proceedings.Mathematics and Computers in Science and Engineering.World Scientific and Engineering Academy and Society，2009(8).

［24］Yan J T.Timingdriven octilinear Steiner tree construction based on Steinerpoint reassignment and path reconstruction［J］.ACM Transactions on Design Automation of Electronic Systems(TODAES)，2008，13(2)：  118.

［25］Fortune S. A sweepline algorithm for Voronoi diagrams［J］.Algorithmica，1987，2(1)：  153174.

［26］Preparata，F.P.M.I.Shamos.Computational Geometry：  an Introduction［M］.Springer Verlag，1985.

［27］Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem［J］.Proceedings of the American Mathematical Society，1956，7(1)：  4850.

［28］Huang X，Liu G,Guo W，et al.Obstacleavoiding algorithm in Xarchitecture based on discrete particle swarm optimization for VLSI design［J］.ACM Transactions on Design Automation of Electronic Systems(TODAES)，2015，20(2)：  24.

［29］Berg M D. Computational Geometry：  Algorithms and Applications［M］.Springer Publishing Company，Incorporated，2000.

［30］Borah M,Owens R M,Irwin M J.An edgebased heuristic for Steiner routing［J］.IEEE Transactions on ComputerAided Design of Integrated Circuits，and Systems，1994，13(12)： 15631568.

［31］Ajwani G，Chu C,Mak W K.FOARS：  FLUTE based obstacleavoiding rectilinear Steiner tree construction［J］.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2011，30(2)：  194204.

［32］Chow W K，Li L,Young E F Y，et al.Obstacleavoiding rectilinear Steiner tree construction in sequential and parallel approach［J］.Integration the VLSI Journal，2014，47：  105114.

［33］Huang T，Young E F Y. ObSteiner：  an exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles［J］.IEEE Trans ComputAided Des Integr Circuits Syst，2013，32：  882893.