新型电路版图布局布线算法设计

袁 也，王 刚，刘晓光，李雨森

(1.南开大学计算机学院，天津 300350；2.天津市网络与数据安全重点实验室(南开大学)，天津 300350)

1 引言

发达国家在集成电路领域的高新技术成果方面始终对我国形成封锁。近年来，集成电路自动化设计技术高速发展，为了推动我国迈入该领域发展的快车道，越来越多的学者开始研究电路自动化设计的相关技术。

当前我国虽然在大规模电路的布局布线方面已有许多成果，但是对于中小规模电路的布局布线研究却很少，更多的是追求快速求得整体结果和解决大规模问题的卓越能力，而暂时忽略了软件商用时用户自主设计的便捷性和舒适性以及用户使用软件时一些更具体的需求。对此本文改进了划分算法，提升了划分结果质量，提出了全新的布局算法，满足对美观度的要求，提升了A*算法的布线速度，提高了布线质量，形成一套适用于中小规模模块的布局布线方案，方便用户在实际布线前检查电路各模块的逻辑错误，填补了相关研究领域的空白。

2 相关工作

目前电路布局算法主要有2类，一类是直接布局算法，另一类是面向划分的布局算法。直接布局算法大多采用传统启发式算法如模拟退火算法[3,4]、遗传算法[5,6]和粒子群优化算法[7]等，是在一个初始布局的基础上通过尝试性改变的效果决定下一步迭代改进的方向，循环往复直至结果满足一定条件为止。这类算法的特点是布局效果较好，不易陷入局部最优，但算法运行速度慢、时间长。

随着电路元件规模达到数百甚至上千，这些元件组合成极其复杂的超图，直接布局难度较大。面向划分的布局算法将大规模的电路划分为很多小规模的部分再布局，有效降低了布局难度，还可使各个功能模块更加聚集，使得布局布线效果更好，缺点是部分算法的划分结果常常不均衡。

电路布线技术多是在A*寻路算法[8]的基础上进行设计，该算法能够在网格化空间内有效寻找最短路径，缺点是运行速度慢。

在布局阶段本文改进了Stoer-Wagner算法[9]，弥补了其划分结果不均衡的缺点，同时使用Fiduccia-Mattheyses算法[10]优化该算法的结果并形成一棵划分树，在划分树的基础上设计了二元相对移动算法，能够在兼顾布局拥挤度和布局空间大小的同时以较低的时间复杂度完成布局。在布线阶段本文改进了A*寻路算法，提高了其运行速度，并重新设计了其搜索函数，满足了中小规模电路对较少的线路交叉、线路转折以及较低的布线拥挤度的需求。

3 布局算法设计

本文设计的布局布线算法面向中小规模电路，试图实现对元件的布局布线，区别于传统的物理设计，本文设计的算法强调运行速度和布局布线结果的美观性和逻辑性，而相对忽略布线空间的耗费。

在本文中布局算法的目标有3点：(1)各元件按照功能模块划分和聚集；(2)各部分之间的割值尽量小；(3)划分的各部分节点个数相差较小；(4)布局区域尽量小。

由于面向划分的布局算法布局均匀，且相关技术较为成熟，因而本文基于面向划分的布局算法进行设计，选择Stoer-Wagner算法生成初始划分，并对算法做了改进，避免出现不平衡的划分结果，然后选择Fiduccia-Mattheyses算法对初始划分做进一步改进。

3.1 模型构建

电路图是非常典型的超图模型，其中每条线路可能联结2个以上的电路元件。本文首先建立了超图模型，将数据读入一张表中，例如表1，其中a、b、c代表超边，数字表示节点，表项表示超边与该节点联结的权重。

Table 1 Edge node matrix

随后将度为2以上的超边，即联结了2个以上节点的超边转化为节点，每个超边转化成的节点与原超边关联的每一个节点都有一条度为2的超边，这样超图中则不存在度为2以上的超边，则超图转化为图，如图1所示。数据存储在邻接矩阵中，如表2所示，数字表示节点，表项表示节点间边的权重。之后的布局算法在此邻接矩阵形式的基础上进行设计。

Figure 1 Transformation of hypergraph图1 超图的转化

Table 2 Adjacency matrix

3.2 使用Stoer-Wagner算法获得初始划分

Stoer-Wagner算法是用于搜索无向图的全局最小割的高效算法，普通的查找最小割的算法是Ford-Fulkerson算法，能在O(n2m)的时间复杂度内查找到将确定的s、t2节点划分到2部分的最小割，其中n为节点数，m为边数，在复杂网络下m甚至能达到O(n2)的复杂度，因此若使用Ford-Fulkerson算法查找全局最小割，复杂度可能会达到O(n5)，对于成百上千节点的情况，这样的时间消耗显然是无法接受的。Stoer-Wagner算法能在O(n3)的时间复杂度内得出全局最小割，时间复杂度远远优于Ford-Fulkerson算法。

Stoer-Wagner算法基于这样一种思想：对于图中任意2个节点，它们或者属于全局最小割的2个不同划分，或者属于同一个划分。如果是后者，那么合并这2个节点后并不影响全局最小割。

基于这种思路，若每次能求出将图中某2个节点s、t划分到2部分的最小割，记录下割值和划分后将这2个节点合并为1个节点，再求某2个节点的最小割，重复上述操作直至全部节点收缩为1个，此时记录中割值最小的划分就是所求的划分。

其中在每次求将s、t划分到2部分的最小割时基于一种贪心的策略：首先任选某一节点作为原点，从剩余节点中找出和原点相连的边权重最大的一个，暂时将其与原点合并，重复此操作直至除原点外仅剩余一个节点为止，这个节点和最后一个与原点合并的节点即为上述的s、t，该节点和原点当前的相连边权重即为求得的割值。

如图2所示节点3号和节点4号即为s、t，最小割值为2。详细证明见参考文献[11]。

Figure 2 Stoer-Wagner algorithm图2 Stoer-Wagner算法

Stoer-Wagner算法能在O(n3)的时间复杂度内得出有效解，效果远远好于传统的最小割算法，但却很少应用于布图算法，原因在于：(1)时间复杂度较高，难以用于大规模电路设计；(2)Stoer- Wagner算法求出的最小割是理论最小割，这样的结果往往忽视了划分的平衡要求，也就是说Stoer-Wagner算法常常会得出1∶99的元件比例的划分结果，这样的结果显然不适合用于电路划分。

但是，本文主要研究中小规模电路布局，因而虽然Stoer-Wagner算法时间复杂度较高，但仍能在较短时间内获得结果。因此，本文对Stoer-Wagner算法进行修改使其能用于获得高质量的初始划分。为了兼顾平衡约束和割值最小，对算法进行如下修改：在每次选取与原点关联最多的节点并入原点时，若并入后满足平衡条件，则记录下此时原点中包含的节点以及原点不包含的节点作为划分结果。在算法运行结束时并不直接选择割值最小的划分，而是在记录的割值与划分结果中选择割值最小的划分作为初始划分。

3.3 使用Fiduccia-Mattheyses算法优化初始划分

Fiduccia-Mattheyses算法的主要思想是：首先将图随机二等分，每次从2部分中选择1个节点划分到另一部分来最大程度地减小二划分的割值，重复此过程直至划分结果优于某一限度并且满足平衡条件。这里的平衡条件按式(1)计算：

n/2·(1-p)

(1)

其中,p为根据需求自定义的平衡参数，根据对运行效果和运行速度的需求进行调整。评价当前划分的优度时既考虑使割值较小，又要保证划分出的2部分元件数量之差小于某一范围。

Fiduccia-Mattheyses算法能在O(n2)的时间复杂度和O(n)的空间复杂度内对初始划分进行有效优化，优化结果见第5节。

3.4 二元相对移动算法

本文使用Fiduccia-Mattheyses算法和Stoer-Wagner算法将全部元件划分为一棵二叉划分树，提出了一种二元相对移动算法对划分树进行布局。

二元相对移动算法是在网格上布局元件并搜寻最优布局的算法，因此首先需对元件进行网格化建模，暂时忽略元件的电路表示形式，用数个网格构成的长方形代表元件。

在介绍算法的详细步骤之前先给出优度值的计算公式如式(2)所示：

gdegree=α·cd+(1-α)·pl/maxl

(2)

其中，α是根据具体算法对布线长度和布线拥挤度的相对侧重程度确定的参数；cd为空间拥挤程度，是区域section(A,B)内被占用方格占全部方格的比重，区域section(A,B)是由A、B的8个顶点中位于最左上的顶点与最右下的顶点分别沿横向和纵向做延伸线所围成的区域，如图3所示；maxl表示元件间布线长度的最大值；pl为元件之间布线长度的估计值，此处用元件中心坐标间的曼哈顿距离表示，如式(3)所示：

pl=|(Asx+Aex)/2-(Bsx+Bex)/2|+

|(Asy+Aey)/2-(Bsy+Bey)/2|

(3)

Figure 3 Moving process of binary moving algorithm图3 二元移动算法的移动过程

布局时先使用Stoer-Wagner算法和Fiduccia-Mattheyses算法组合成的划分算法对全部元件进行递归划分：先将元件划分为2个割值较小且相对平衡的部分，再对割出的2个部分运行此划分算法，重复此操作直至所有的元件均处于相互孤立的叶节点中，同时构建出一棵二叉划分树，如图4所示。

Figure 4 Partition tree图4 划分树

从二叉划分树的叶节点开始对任意2个兄弟叶节点的元件测试在不同相对位置下排布的优度，找出优度值最大的排布方式，按照此排布确定2个元件的相对位置，组合成一个新的元件返回给父节点作为父节点的元件，再对父节点及其兄弟节点重复上述操作直至返回根节点，则获得全部元件的整体布局情况。

二元相对移动算法存在一些不足，在运行二元相对移动算法时会导致布局空间的浪费，因为环绕排布的方式会导致元件间有空隙，因此本文在此基础上对布局空间进行自顶向下的规划，从根节点开始对左右子树根据其中的元件数和连线数设置矩形布局空间的长和宽的上限。在运行二元相对移动算法时不得越过上述界限。

此外在运行二元相对移动算法时，为了给布线留出足够的空间，在元件外层套上一层空白层后再移动位置，如图5所示，图中sectionAC表示元件A及其外围包裹的空白网格构成的空间，sectionBC表示元件B及其外围包裹的空白网格构成的空间。

Figure 5 Extended A* algorithm图5 扩张后的A*算法

4 布线算法设计

本节设计并改进了布线算法，在第1节布局结果的基础上根据各个元件之间的联结关系使用A*寻路算法布置线路，随后针对A*算法的一些不足进行了改进。

4.1 A*寻路算法

A*算法的基本思想是在当前搜索空间的基础上选取较优方向的网格加入搜索空间，而不是将所有方向的网格都加入搜索空间从而限制了搜索空间的膨胀，加快了搜索速度。

A*算法的基本流程是：建立一个开表和闭表，先将起点网格放入开表，每次从开表中选取与终点曼哈顿距离值f最小的网格放入闭表，并将其周围的空白网格放入开表，重复此操作直至选取出的网格为终点网格为止，此时则搜索到了一条起点到终点的路径。其中若即将加入开表的空白网格已在开表中，则比较其原本前驱网格与当前选出网格与起点的距离，选取距离较小者作为其前驱网格。

4.2 A*寻路算法改进

在面对成百上千的元件时，A*算法的时间开销在数分钟到数十分钟之间，时间开销是影响A*算法实用性的重要因素。分析4.1节A*算法的流程可知，A*算法的时间主要消耗在从开表中选出f值最小的网格，若使用排序算法查找最优网格则每次查找的时间复杂度为O(mNum·logmNum)，其中mNum为开表中网格数量。这里用L表示网格区域的边长，平均情况下的复杂度为O(L)，开表搜索的运行次数也为O(L)量级，则布线一次的时间复杂度平均情况下为O(L2·logL)。因此，本文改进A*算法在选择最优f时不使用排序算法，而是维护一个最小堆，每次从堆顶直接取出f值最小的网格后再整堆，则布线一次的时间复杂度由O(L2·logL)降为O(logL)。

传统A*算法的目标在于找到最短距离，但本文的布线需求除了距离较短外还追求美观度，而使用本网格到终点网格的曼哈顿距离来估计值，忽略了布线对布局拥挤程度的影响，因此在进行较大规模的布线运算时，较晚布置的线路会因为较早布置的线路对可布线网格的占用而无法布通。因此，为了兼顾距离最短、拥挤度和美观程度本文选择构造式(4)来满足本算法的需求：

f=(μ·c+(1-μ)d)dis

(4)

其中,μ为一个小于1的参数;c为本网格的拥挤程度，拥挤程度越大值越大，这样就使得走线时尽量选择拥挤度较低的方向，从而减小拥挤度，提高布通率。此处用此网格周围5层网格中障碍网格的占比表示：在图6中，浅色灰度网格的c值为黑色障碍网格数除以黑色方框区域内的网格数。d为网格类型惩罚值，为了保证布线结果的美观，应尽量避免出现线路交叉或转折，因此本文根据走线类型将网格分为3类，对3类不同的网格赋予不同的惩罚值，使得走线时尽量选择惩罚值较小的网格，从而保证美观程度。如图7所示，类型1的惩罚值为0.5，类型2的惩罚值为1，类型3的惩罚值为0.3。另外走线类型是根据网格与父网格、祖先网格的相对关系以及布线次数确定的：对于类型1的网格，本网格与父网格的父网格的横纵坐标都不相同；对于类型2的网格，是根据布线数为2这一特征确定网格类型的；对于类型3的网格，本网格与父网格的横纵坐标中有且仅有一对不相同。dis为本网格与终点网格的曼哈顿距离。

Figure 6 Calculation of c value图6 c值的计算

经过上述改进，A*算法时间复杂度降为O(L2)，布线结果更加美观，布通率大大提升。

Figure 7 Grid types图7 网格类型

5 实验和结果分析

实验环境为如下配置的虚拟机：单核CPU，主频2.8 GHz，内存1 GB，操作系统为CentOS 6.4-64 bit。

本文使用C++语言实现并测试整个布局布线算法，包括布局阶段的Fiduccia-Mattheyses算法、Stoer-Wagner算法、二元相对移动算法、模拟退火算法和布线阶段A*算法的实现。电路信息如表3所示。

Table 3 Circuit information

5.1 布局算法测试

在表4中，括号中的数据是3.4节的改进方法实现前的划分算法和布局算法的效果，括号外的数据为改进后的算法效果。可以看出，改进后的算法运行速度提升了数倍到数十倍，拥挤度降低了数倍到数十倍，节点数越多提升越大。此外布局面积大幅减小，为布线算法降低了搜索难度。由表4可以看出，布局区域形状均匀，在保证拥挤度小于0.5的前提下布局区域较小。划分时间与节点数呈正相关，布局时间和线路数呈正相关，对于数百节点，上千条线路的电路图，本文使用的算法均能在0.5 s内得出划分和布局结果。

Table 4 Layout results

5.2 布线算法测试

由表5可以看出，4.2节的改进方法实现后的布线算法相对于改进前速度有了近百倍的提升，交叉数、转折数、拥挤度和布线总长度大幅缩小。本文提出的改进策略实现了较好的效果，在尽量保证较低拥挤度的前提下减少了布线总长度，使得布线总长度随着线路数的增加近似保持线性增长，同时尽量减少了交叉数和转折数，使得交叉数和转折数大约保持在布线总长度的10%，保证了布局布线结果的美观性。此外表5中电路的布通率均为100%。

在运行速度方面，本文算法在布线数小于500时，布线时间不超过0.5 s；布线数超过1 000时布线时间大约需要20 s～1 min，本文算法的运行速度能够满足数十到数百电路元件的布局布线需求。图8展示了电路17的最终布局布线效果。

6 结束语

本文在当前电路布局布线相关研究的基础上设计并实现了一个布局布线方案，用于满足大规模电路设计软件中用户对于中小规模模块的快速排查错误的需求。在设计布局算法时本文使用Stoer-Wagner算法生成初始划分，用Fiduccia-Mattheyses算法优化划分结果，提出并改进了二元相对移动算法生成布局结果。在设计布线算法时本文在A*寻路算法的基础上实现并优化了布线算法。整个设计的布局布线结果较为美观，在控制布局面积和布线总长度的前提下拥挤情况较为良好，元件和线路分布较为均匀，对于规模小于数百元件、数千线路数的电路能在0.1 s～1 min内得出结果，满足了用户对中等规模电路功能模块的快速定位和排查错误的需求。

Table 5 Wiring results