基于多子群竞争PSO的限制长度的X结构Steiner最小树构建方法

摘要

本发明提供了一种基于多子群竞争PSO的限制长度的X结构Steiner最小树构建方法，包括步骤如下：步骤1：加载电路数据；步骤2：进入MSCPSO搜索阶段；步骤3：使用极限穿障策略；步骤4：使用双精炼策略：步骤5：输出LRXSMT作为布线方案，结束算法。应用本技术方案可实现以充分利用障碍内部的可布线资源，从而有效缩短布线长度。

说明书

技术领域

本发明涉及集成电路计算机辅助设计技术领域，特别是一种基于多子 群竞争PSO的限制长度的X结构Steiner最小树构建方法。

背景技术

随着超大规模集成电路(Very Large Scale Integration,VLSI)问题 规模的扩大，芯片密度急剧增加，功能愈发复杂，越来越多的组件(如知识 产权保护模块、宏单元、预布线线网等)集成到一个芯片上。在VLSI物理 设计的总体布线阶段，这些在布线过程中无法移动的组件被视为障碍，成 为无法忽视的因素。以往不考虑障碍物的布线算法已经难以满足实际的芯 片设计需求。一些学者研究绕障布线，即布线边完全绕开障碍物并连通线网。然而，在实际的多层布线中，障碍只占据了设备层以及某些底层金属 层，即障碍内部仍然存在可布线区域，并不会完全阻断布线。但是，障碍 内部的导线过长会引起噪音问题，信号在其中传输可能因此衰减或失真。 为避免信号的衰减或失真，一般需要使用中继器对信号进行再生和放大。 又由于障碍已经占据了设备层，故障碍内部无法放置中继器，为此，需要 限制障碍内部的导线长度，使信号在失真之间到达障碍外部。综上，研究 限制长度的布线问题能够保证时序收敛，有效缩短布线总线长，节约布线 资源，从而提高芯片质量。

总体布线多端线网的最佳连接模型是Steiner最小树(Steiner Minimum Tree,SMT)。而SMT的构造中，布线边的互连模型通常为直角结 构，即只能以0°或90°方向布线。然而，直角结构的布线方向过于单一， 限制了SMT问题的解空间，在线长这一重要指标上的优化能力已步入瓶颈 期。相较于传统的直角结构，以X结构为代表的新兴的非直角结构允许从0°、 90°、45°及135°四个方向进行布线，扩大了SMT解方案的搜索空间，更 有利于减少布线资源冗余，优化总线长，降低互连线时延。目前，随着VLSI 芯片制造工艺的进步，X结构已被成功应用于SMT的构造中，成为总体布线 算法的研究热点。然而，目前仅有少量工作研究限制长度的X结构Steiner 最小树(Length-Restricted X-architecture SteinerMinimum Tree, LRXSMT)。

以往的研究工作常用精确算法构造SMT。精确算法能够保证求得准确的 最优解，然而其复杂度过高，难以求解大规模布线问题。后有学者尝试使 用传统启发式算法构造SMT，但多使用贪心策略，算法极易陷入局部最优， 难以找到更高质量的解，无法满足复杂性呈指数增长的VLSI物理设计的发 展需求。因此，学者们将目光聚焦于群智能算法。自然界中，个体通过简 单的交互行为往往能实现群体的智能行为，群智能(SwarmIntelligence, SI)算法即是模拟这种生物现象所提出的智能计算技术，为复杂的优化问题 提供了新的解决思路。其中，粒子群优化算法(Particle Swarm Optimization,PSO)作为SI的代表之一，由于控制参数少，实现简单，寻 优能力强，在众多SI技术中脱颖而出，被用于解决VLSI布线问题，以期 突破传统布线算法的瓶颈。然而将PSO应用于LRXSMT问题的工作中，PSO 存在因多样性丧失而过早收敛的问题，且未能充分利用障碍内部的布线空间，算法的性能有很大的提升空间。

发明内容

有鉴于此，本发明的目的在于提供一种基于多子群竞争PSO的限制长 度的X结构Steiner最小树构建方法，以充分利用障碍内部的可布线资源， 从而有效缩短布线长度。

为实现上述目的，本发明采用如下技术方案：基于多子群竞争PSO的 限制长度的X结构Steiner最小树构建方法，其特征在于包括步骤如下：

步骤1：加载电路数据；

步骤2：进入MSCPSO搜索阶段；

步骤3：使用极限穿障策略；

步骤4：使用双精炼策略：

步骤5：输出LRXSMT作为布线方案，结束算法。

在一较佳的实施例中，所述步骤2包括：

步骤2.1：基于X结构，使用Prim算法生成初始布线树作为初始种群；

步骤2.2：若mod(it,t)＝＝0，则子群处于新一轮迭代子周期，进入步 骤2.3，否则进入步骤2.4；

步骤2.3：根据公式(1)-(2)确定子群个数以及子群规模，并随机挑选 种群中的粒子构成子群；

子群规模size计算公式如下：

其中，size表示子群规模，its代表设定的最大迭代次数，it代表当前迭 代次数，t为预先设定的子群迭代的子周期；确定子群规模后，子群个数k 按照如下公式计算：

步骤2.4：若mod(it,R)＝＝0，则需要进行子群间信息交流，则进入步 骤2.5，否则进入步骤2.6；使用线性递减信息共享率R控制子群间的信息 交流，其计算公式如下：

其中，R

步骤2.5：对子群进行打乱重组，且子群个数和规模不变；

步骤2.6：对每个子群，随机挑选子群内的两个粒子进行竞争，选择适 应值较小的为赢家，适应值较大的为输家；

更新粒子个体最优pbest；

步骤2.7：更新种群最优gbest；

步骤2.8.若满足MSCPSO的终止条件，即达到设定的最大迭代次数， 则进入步骤3，否则，继续MSCPSO搜索。

在一较佳的实施例中，所述步骤3包括：

步骤3.1：对于MSCPSO得到的gbest，遍历其布线树中的每条边，若 存在某条边违反约束，则进入步骤3.2，否则进入步骤4；

步骤3.2：拆除违反约束的边，在障碍内部或边缘选择PS点并连接构 成新的布线边；若每条边都满足约束，则进入步骤4。

在一较佳的实施例中，所述步骤3包括：

步骤4.1：对于每个引脚，找到以该引脚为根，深度为2的子树，对其 使用点精炼，得到使公享长度最长的PS点组合；

步骤4.2：根据共享长度由短到长对每棵子树排序；

步骤4.3：对于前50％的子树，对其使用边精炼，得到使布线树线长最 短且满足约束的新结构。

与现有技术相比，本发明具有以下有益效果：

1.引入多子群的思想，把种群随机划分为多个子群，又使用线性递增 子群规模的策略，使子群个数随迭代次数增加而变少，到迭代后期，融合 为一个种群。通过这种子群划分的方式，使算法前期注重探索能力，后期 加强开发能力。提出线性递减信息分享策略，在子群独立搜索的过程中， 通过线性递减信息分享率控制子群打乱重组，从而保持子群内部粒子的“活 力”，使子群之间能够及时分享各自内部的信息。

2.在多子群PSO的基础上结合竞争机制的思想，提出MSCPSO策略。该 策略首先让子群内部的粒子进行配对竞争，判断输家与赢家。随后重新定 义粒子更新公式，针对两类粒子设置不同的学习对象，从而避免由于学习 对象过于单一而导致的多样性缺失的问题。

3.考虑到LRXSMT是一个离散问题，通过加入针对Steiner点和边结构 的变异交叉算子，从而实现MSCPSO的离散化，以更有效地构建LRXSMT。此 外，对输家粒子和赢家粒子使用不同的学习方式，以实现探索与开发的良 好平衡。

4.针对MSCPSO求得的布线树，设计极限穿障策略，拆除其中违反约束 的布线边，在障碍边缘或内部选择合适的伪Steiner点作为中间节点并连 接以构成新的布线边。布线边或绕开障碍或穿过障碍并在违反约束前到达 障碍外部，从而保证布线树完全满足长度限制，且最大化在障碍内部的长 度，以充分利用障碍内部的布线空间。

5.提出双精炼策略。首先通过精炼Steiner树中的点选择，调整每条 边的走线方式，在满足约束的前提下，通过最大化布线边之间的共享长度 (总线长不重复计算共享边线段)，从而进一步缩短总线长；在此基础上， 若布线树中的局部拓扑结构无法达到点精炼的目的，则对其进行针对边结 构的精炼，即尝试拆除该局部拓扑中的布线边，并重新生成边结构不同的 新的布线树，在保证满足约束的同时，得到线长最小化的XSMT。

附图说明

图1为本发明优选实施例的竞争机制示意图；

图2为本发明优选实施例的4种走线方式示意图；

图3为本发明优选实施例的针对边学习的变异操作示意图；

图4为本发明优选实施例的针对边学习的交叉操作示意图；

图5为本发明优选实施例的针对点学习的变异操作示意图；

图6为本发明优选实施例的针对点学习的交叉操作示意图；

图7为本发明优选实施例的违反约束布线边示意图；

图8为本发明优选实施例的极限穿障策略示意图，其中，(a)表示连 接pb

图9为本发明优选实施例的点精炼策略示意图，其中，(a)表示ac的 4中PS点选择，(b)表示ac与ab的共享边；

图10为本发明优选实施例的边精炼策略示意图，其中，(a)表示布线 树，(b)表示精炼PS点选择，(c)表示精炼边结构；

图11为本发明优选实施例的流程图。

具体实施方式

下面结合附图及实施例对本发明做进一步说明。

应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的 说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属 技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非 意图限制根据本申请的示例性实施方式；如在这里所使用的，除非上下文 另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的 是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、 步骤、操作、器件、组件和/或它们的组合。

基于多子群竞争PSO的限制长度的X结构Steiner最小树构建方法， 参考图1至11，包括步骤如下：

步骤1：加载电路数据；

步骤2：进入MSCPSO搜索阶段；

步骤3：使用极限穿障策略；

步骤4：使用双精炼策略：

步骤5：输出LRXSMT作为布线方案，结束算法。

以下为具体说明：

1.多子群策略：

PSO的一个挑战性任务是如何平衡探索和开发能力，这也是提升PSO 寻优能力的关键。由于探索会抑制种群的收敛，而开发往往会导致种群在 非最优区域内匆忙聚集，故而二者都不能过分强调。然而传统PSO常常因 为多样性缺少而探索能力不足，导致无法搜索到最优解所在的区域，也就 无法开发最优解区域。为增强探索能力，本发明引入多子群的思想，将整 个种群划分为k个规模相同的子群S＝{S

然而，若在整个迭代过程种，算法一直以多子群的形式进行寻优，那么 迭代后期，当算法已经找到最优解所在区域，却无法结合所有子群的力量 开发最优解，会导致开发能力不足，依然无法找到一个更好的解。为了平 衡探索和开发能力，本发明提出线性递增子群规模的策略。该策略随迭代 次数的增加扩大子群的规模。种群粒子数量不变，子群内的粒子越多，自 然子群数量也就减小了。子群规模size计算公式如下：

其中，size表示子群规模，its代表设定的最大迭代次数，it代表当前迭代次 数，t为预先设定的子群迭代的子周期。为避免子群规模过小，子群数量过 多，导致算法过度探索，本发明设定its为800，t为200。确定子群规模后， 子群个数k按照如下公式计算：

然而，在迭代子周期内，子群独立地搜素解空间可能会导致子群之间信 息交流的不充分，从而使得算法没能充分利用搜寻到的优秀信息。为此， 本发明使用线性递减信息共享率R[29]控制子群间的信息交流，其计算公式 如下：

其中，R

2.竞争机制：

传统PSO存在容易陷入局部最优的痛点，这很大一部分原因在于种群在 信息共享的过程中，让所有粒子都向同一个全局历史最优(gbest)学习，若 gbest在局部最优附近，当所有粒子都在gbest的带领下向局部最优区域靠 近，那么种群将很容易地陷入局部最优且难以跳出。为了规避这个风险， 本发明在多子群的基础上加上竞争机制的思想。通过竞争将子群划分为赢 家和输家两类粒子，并赋予两者不同的社会学习对象，从而避免了由于学 习对象过于单一而过早收敛的情况。种群多样性大大增加，有利于算法寻 找到真正的全局最优解。

具体地，设种群S＝{s

使用竞争机制后，种群中有一半的粒子(输家)会通过向其所在子群中质 量更好的粒子学习(赢家)以实现其社会认知，从而提高了种群的多样性，迭 代前期能够减缓粒子向全局最优的收敛的速度，从而有利于避免算法过早 地陷入局部最优，而种群中的另一半粒子不受子群的领域限制，仍旧向gbest 学习，每个子群能够在独立迭代的过程中保持与全局最优的联系，从而保 证了收敛性。

3.MSCPSO离散化：

(1)目标函数

LRXSMT的优化目标是在满足长度约束的情况下最小化总线长代价。总 线长为一棵Steiner树中所有边线段的长度之和，其计算公式如下：

其中e

考虑到MSCPSO的随机性，在迭代过程中，Steiner树可能会存在违反 约束的布线边，即布线边线长超过长度限制，为了在迭代过程中尽可能地 避免违约的情况发生，算法在计算线长代价时对违反约束的边加以惩罚并 设计如下适应度函数：

p

其中n表示该Steiner树中违反约束的边的总数，p

(2)粒子编码

为了更有效地用粒子表示对应的XSMT，本发明选择边点对编码方式 对粒子进行编码。现有一棵包含n个引脚、n-1条布线边的Steiner树，其 中，树的每条边由其起始引脚、终止引脚和连接两引脚的PS点选择(如图2 所示，4种PS点选择对应X结构4种走线方式)表示，布线树的质量由适 应度值反映。故一个粒子完整的编码长度为3×(n-1)+1。一棵Steiner树根据 边点对编码可以表示如下。

56267272274073213321

其中，根据长度为3的子串对应Steiner树中的一条边，如‘

(3)更新过程

由于本发明在PSO中引入了多子群和竞争机制的思想，粒子的更新与传 统PSO有很大的不同。此外，本发明算法让质量较差的输家进行探索，让 质量较优的赢家进行开发，从而通过两类粒子不同的更新操作实现子群乃 至整个种群的探索与开发的动态平衡。同时，连续型的更新公式不再适用 于离散LRXSMT问题，需要进行离散化操作。为此，本发明提出新的更新 公式。

具体地，本发明对赢家使用针对点的更新操作，对输家使用针对边的更 新操作。离散化后赢家更新公式如(7)所示，输家更新公式如(8)所示:

其中，ω为惯性权重，c

1)输家更新过程

a.惯性分量

本发明通过引入针对边的变异操作实现WF

其中，M

当随机数r

b.个体认知分量

本发明通过引入针对边的交叉操作实现LF

其中，C

当随机数r

c.社会认知分量

本发明通过引入针对点的交叉操作实现LF

其中，C

2)赢家更新过程

a.惯性分量

本发明通过引入针对边的交叉操作实现WF

其中，C

当随机数r

b.个体认知分量

本发明通过引入针对边的交叉操作实现WF

其中，C

当随机数r

c.社会认知分量

本发明通过引入针对边的交叉操作实现WF

其中，C

4.极限穿障策略：

为了使布线树完全满足长度限制，同时尽可能利用障碍内部的布线空间， 本发明设计了极限穿障策略。对于图7中的违约布线边pq，算法首先拆除 pq，以p为起始节点s，按障碍中心与s的距离由近到远对障碍进行排序， 并按顺序处理障碍。

接着，选择O

其次，处理障碍O

5.双精炼策略：

(1)点精炼

MSCPSO的随机性同样导致其找到的gbest离最优解可能还有一段距离。 此外，为了减少线长，本发明在构建布线边的时候优先选择PS 0或PS 1 的走线方式。然而，并非所有情况下，基于X结构的走线方式都会优于直 角结构。如图9(a)所示，一个三引脚线网包含引脚a、b和c，其布线树包 含边ab与ac，ab以PS 3的走向方式连接，而ac之间可有四种走线方式， 即图9(a)中的虚线段。若不考虑ab，则ac以PS 0或PS 1的方式布线可以 获得更短的线长。然而，事实上，考虑到ab边，则ac边以PS 3的走线方 式进行布线可以更有效地优化线长。这是因为以PS 3布线时，ac与ab则 会共享一段布线边线段，即图9(b)中的加粗虚线段。由于共享边线段不会 重复计入线长代价，故该布线树可以获得更短的线长。因此，本发明设计 点精炼策略，通过调整Steiner树中每条边的PS点选择，以最大化布线共 享度。

首先，对于布线树中每个引脚P＝{P

接着，根据排序，遍历调整引脚P

最终，通过选择最优的PS点选择组合，最大化布线树中的每棵子树的 共享长度，总线长因此得到优化。

(2)边精炼

点精炼只调整布线边的走线方式，无法摆脱原有拓扑结构的限制。若 原有拓扑结构不是最优拓扑，那么无论怎么精炼PS点选择，算法得到的布 线解方案仍然与最优解有一段无法缩短的距离。以图10中的布线树为例， 该树中包含3条互连边，分别是ab、bd、dc，经过点精炼后，算法得到的 最优PS点组合如图所示，即将bd与dc的PS点选择从PS 3和PS 2改为 PS 0和PS 1。从图10中可以发现，(b)图布线线长优于(a)图，证明点精炼 有一定的线长优化效果。但精炼边结构后，树的拓扑改变，如图所示，新 的互连边为ab、bd、bc，且(c)图布线线长优于(b)，改变树的拓扑有机会进 一步缩短线长。

因此，在点精炼的基础上，本发明又设计边精炼。

首先，按照点精炼阶段得到的局部子树的共享长度按照升序对每个引脚 排序。对于前50％的引脚，算法认为点精炼策略无法有效优化其子树线长， 对其进行边精炼。

接着，对于每个引脚P

通过对点选择与边结构的双重精炼，Steiner树从局部的互连细节乃至整 体的拓扑结构都得到了优化，从而实现线长的最小化，得到最终的LRXSMT。

6.总体：

本发明所提出的基于多子群竞争PSO的限制长度的X结构Steiner最小 树构建方法在满足长度限制的前提下优化了布线总线长。本发明总体流程 图如图11所示，步骤如下：

步骤1.加载电路数据

步骤2.进入MSCPSO搜索阶段

步骤2.1.基于X结构，使用Prim算法生成初始布线树作为初始种 群

步骤2.2.若mod(it,t)＝＝0，则子群处于新一轮迭代子周期，进入步 骤2.3，否则进入步骤2.4；

步骤2.3.根据公式(1)-(2)确定子群个数以及子群规模，并随机挑选 种群中的粒子构成子群；

步骤2.4.若mod(it,R)＝＝0，则需要进行子群间信息交流，则进入步 骤2.5，否则进入步骤2.6；

步骤2.5.对子群进行打乱重组(子群个数和规模不变)；

步骤2.6.对每个子群，随机挑选子群内的两个粒子进行竞争，选择 适应值较小的为赢家，适应值较大的为输家，根据公式(9)-(11)对输家进行 更新，根据公式(12)-(14)对赢家进行更新，并更新粒子个体最优pbest。

步骤2.7.更新种群最优gbest。

步骤2.8.若满足MSCPSO的终止条件(达到设定的最大迭代次数)， 则进入步骤3，否则，继续MSCPSO搜索；

步骤3.使用极限穿障策略；

步骤3.1.对于MSCPSO得到的gbest，遍历其布线树中的每条边， 若存在某条边违反约束，则进入步骤3.2，否则进入步骤4。

步骤3.2.拆除违反约束的边，在障碍内部或边缘选择PS点并连接构 成新的布线边。若每条边都满足约束，则进入步骤4。

步骤4.使用双精炼策略：

步骤4.1.对于每个引脚，找到以该引脚为根，深度为2的子树，对 其使用点精炼，得到使公享长度最长的PS点组合；

步骤4.2.根据共享长度由短到长对每棵子树排序；

步骤4.3.对于前50％的子树，对其使用边精炼，得到使布线树线长 最短且满足约束的新结构。

步骤5.输出LRXSMT作为布线方案，结束算法。