一个通道布线问题的图论算法

周晓娜，耿显亚

(安徽理工大学理学院，安徽 淮南 232001)

一个通道布线问题的图论算法

周晓娜，耿显亚

(安徽理工大学理学院，安徽 淮南 232001)

图论的思想方法在大规模集成电路布线中有广泛的应用。通道布线的线网结构可以用水平约束图和垂直约束图来描述，利用图论的思想可以处理布线轨道高度问题。研究运用图论的方法来解决超大规模集成电路布线中的轨道高度问题。通过寻找并消除临界网的方法给出布线的一个新的算法，该算法能够得到轨道高度的一个下界，并对在含有一个狗腿的情况下如何布线进行了描述，并设计出能运用到实际布线工艺中的两层具有曼哈顿模型的通道布线算法。

通道布线；临界网；狗腿

1 通道布线的线网关系

布线的首要目标是百分之百的完成模块间的互连，其次是完成布线的前提下进一步优化布线结果。在70年代，逐步提出了“通道区布线”与“分级布线”的概念。布线方法由面向线网转为面向通道区，从而引出了通道布线，常见的通道布线算法有Hashimoto和Steven提出的左边算法、Yoshimura和Kuh提出的合并算法以及贪婪算法和匹配算法等。根据通道区域的划分，通道布线算法又可以分为单层布线算法、双层布线算法及多层布线算法，其中，对于双层通道区域的研究较为透彻一些。许多通道布线的研究集中在设计能够减少通道面积的高效的启发式方法。这些算法大部分都能对一些有名的布线问题提供最优轨道数的布线解决方法。然而，对于估算所需轨道数的下界问题关注的较少。

通道布线在超大规模集成电路(VLST)芯片结构中起重要作用，双层通道是一个芯片上的一个网格矩形区域，芯片由一个水平流向的金属层和一个垂直方向的多晶硅组成，水平层的金属层称为轨道，竖直层的金属层称为列，在顶部和底部分布着固定的节点，通道的左右两边都流动着接线端子，每组都需要通过电力连接起来，称为线网，一个线网可以将通道顶部和底部的节点连接起来，从左边和右边退出通道。

图论的思想方法在超大规模集成电路布线中有着被广泛地应用, 近年来国内外学者做了大量的研究工作, 也得到了许多好的成果[1-6]。 2 层通道布线是一类很普遍并且研究的比较多的布线类型，见文献[7-9]。对于2层通道布线问题，有很多比较好的启发式算法解决这类问题[10-12]。 另外还有很多理论上比较好的改进结果[13-16]。

在通道中，大部分线网布线时只需要占据一个轨道，称占据两个不同轨道的线网为狗腿。对于一个通道布线问题，令S*表示需要轨道的最小数量，如果lb≤S*≤ub，那么称lb为一个下界，ub为一个上界。显然，lb(ub)应该尽可能大(小),以使lb=S*=ub。 考虑两层通道布线问题，本文的主要目标是寻找含有一个狗腿通道布线的S*的下界。

一个通道布线问题(CRP)，可以由两种类型的约束表示，水平约束图和垂直约束图。在水平层两个网不重复的约束称为水平约束，即li为网i最左边的列，ri为网i最右边的列，一个网i的第c列满足li≤c≤ri, 那么组列[li,ri]称为网i的度，若网i与网j之间的度重复，则存在一个水平约束。水平约束可以由一个无向图(HCG)来表示，称为水平约束图。在图中边表示水平约束，顶点表示网。

在垂直层两个网不重复的约束称为垂直约束。如果网i连接最高行的第c列，网j连接最底行的第c列，i≠j，则存在一个从i到j的垂直约束。垂直约束可以由一个定向图(VCG)表示，称为垂直约束，在图中，边表示垂直约束，顶点表示网。

垂直约束具有传递性，如果从网i到网j存在一个垂直约束，而且从网j到网k在一个垂直约束，那么从网i到网k也必定有一个垂直约束。如果垂直约束图中出现了圈，即循环约束，那么就需要加入狗腿来破除它。

如果一个垂直约束是从网i到网j的，那么网i和网j之间一定存在一个水平约束，因为它们至少共享一个相同的列。

本文首先介绍两种算法LB2和LB3，其中LB3是在LB2的基础上进行了改进，最后考虑含有垂直约束图有圈的通道布线，利用图论的思想，给出一个新的算法LB4，并对如何布线进行了描述。

2 LB2和LB3算法

在讨论垂直约束图有圈的通道布线问题之前，先介绍垂直约束图无圈情况下的两种最小轨道算法，其中LB3是对LB2的一种改进。

LB2算法[1]：令G为一个定向的非循环图，如果在G内有一个从i到j的边，那么i就称为j的一个母辈，j就称为i的子辈；如果在G内有一个从i到j的路，那么称i就是j的一个祖辈，j称为i的孙辈，祖辈用Ai表示，孙辈用Di表示，如果Ai为空集，那么称顶点i为一个首点，如果Di为空集，称顶点j为一个尾点。如果每个顶点i的费用ci是1，那么一个路P(∑i∈pci)的费用为路中顶点个数。顶点集合为V的G的导出子图用G[V]表示。为了方便，添加2个假点O和X(费用为0)到G中，添加一条边从O到i的边，如果i是首点，添加一条边从i到X的路，如果i是一个尾点，那么G就成为一个单入口和单出口的DAG。

LB3算法[1]：如果网i和网j之间有一个平行约束或一个垂直约束。那么称两个网i和j是不相容的。

显然，不相容的网不能被分配到同一个轨道，构造一个非定向图，即ICG，其中顶点表示网，边缘表示网之间的不相容关系，ICG中极大团的基数是S*的下界，如果网i与其他所有网是不相容的，称网i是临界的。

LB3算法主要是将垂直约束图中的临界网分离出来，由于临界网只能占据一个轨道，因此临界网的最小轨道数为其顶点数之和|S|，之后画出分离临界网之后的垂直约束图(VCG)和水平约束图(HCG)，利用算法LB2算出它们的lb2。继而求出lb3=|S|+lb2。

如图1所示，CRP的VCG和HCG在(a)和(b)中被展示，很容易看出在(a)中dmax是4，(b)中的vmax是3，网1,2,3是临界网，因此，S={1,2,3}，(c)和(d)为消除临界网1,2,3之后的HCG和VCG，注意到，对VS({4,5,6})中每对网，在临界网被消除之前和之后，水平约束和垂直约束是相同的，也就是说对VS中每一对网(b)中有一个从i到j的路当且仅当在d中有一个i到j的路，在(a)中有一个i到j的边，当且仅当有一个i和j之间的边，则d中vmax为2，dmax为2，因此，CRP的下界可以表示为3+max{2,3}=5。

图1 VCG中不含圈情况

则LB3也CRP是的一个下界,即对于垂直约束图不含圈的CRP，其下界可通过|S|+lb2来计算。

3 垂直约束图含圈的图论算法LB4

若CRP中垂直约束图含圈，布线时必须要含有一个狗腿，那么它会多占有一个轨道。如果一个CRP中含有一个狗腿，而且它含有临界网，那么该狗腿必定在临界网中，那么其下界为CRP4=|S|+max{C(HCG′),P(VCG′)}+1。

LB4的步骤为:

(1)根据结点之间的关系，构造出其对应的水平约束图和垂直约束图。

(2)根据临界网的定义，任意考虑一个点。如果该点与其它结点有水平约束或者垂直约束，则该点属于临界网集合；否则，该点就不属于临界网集合。

(3)考虑剩下的点，再从中任意选取一个点，判断该点与其它点关系。如果该点与其它结点有水平约束或者垂直约束，则该点属于临界网集合。否则，该点就不属于临界网集合。

(4)按照步骤3的方法，依次考虑每个点，找出临界网的集合S。

(5)从原来的水平约束图中去掉临界网集合中的点，得到新的水平约束图，记为HCG′.HCG′的最大团数记为C(HCG′)。

(6)从原来的垂直约束图中去掉临界网集合中的点，得到新的垂直约束图，记为VCG′，VCG′的最长路数记为P(VCG′)。

(7)lb4=|S|+max{C(HCG′),P(VCG′)}+1。

下面用一个例子来说明：如图2所示，a和b为CRP的水平约束图和垂直约束图，在垂直约束图中出现一个圈，那么就需要一个狗腿(线网3)，而且线网3与其它线网之间存在水平约束或垂直约束，即其在临界网中，同样，网1,2也为临界网，即S={1,2,3}，将临界网消除后，得到c′和d′，这两个图中没有边，则C(HCG′)和P(VCG′)均为1，则从而它需要的最小轨道数为

lb4=|S|+max{C(HCG′),P(VCG′)}+1=3+1+1=5。

现在来分析算法的复杂性:当在选择临界网时，每次选择一个点，需要固定的时间来确定该点是否在临界网里面；当去点临界网布线时，需要求最长路的长度，同样需要固定的时间，所以这个算法能在线性时间内完成。

图2 VCG中含圈情况

含有一个狗腿的通道布线:如果网i到网j有一个垂直约束，那么在布线的时候，网i必须在网j的上面。如果在网i和网j之间既没有水平约束，也没有垂直约束，那么它们可以分布在同一层。而对于临界网，它只能单独占据一层轨道。根据以上叙述，在布线的时候可以先根据垂直约束图对临界网进行布线，然后再对没有水平约束和垂直约束的网进行布线，最后再根据垂直约束图对剩下的网进行布线。

布线的步骤如下：

(1)对临界网进行布线(先不考虑狗腿)。根据临界网的定义，找出临界网，观察垂直约束图，若点i到点j有一个垂直约束，那么将点i布在点j的上层。

(2)对狗腿(记为c)进行布线。由于狗腿需要占据两层轨道，根据垂直约束图，如果a到c有一个垂直约束，那么c有一层在a的下面，如果c到b有一个垂直约束，那么c有一层在b的上面。

(3)对既没有垂直约束也没有水平约束的网进行布线。依次考虑非临界网中任意两点d,e,如果它们之间既没有垂直约束，也没有水平约束，那么它们将分布在同一层。

(4)对剩下的网进行布线。剩下的网肯定属于非临界网，但其只能占据一层轨道，只需观察垂直约束图类似于步骤一中的描述对其进行布线。

通过一个例子来说明：

图3 布线之前的CRP

如图3所示，一个还没有布线的CRP，并根据节点的关系构造出CRP的HCG和VCG，其中网1和网3为临界网，图c,d为消除网1和网3后的HCG′和VCG′，可计算出最小轨道的下界为6，则需要6个轨道对其进行布线，首先对临界网进行布线，在VCG中，可看到网3为狗腿，并且它所占有的轨道一层在网2的下面，一层在网1的上面，将网1布在第2层，网3在第1层和第4层，那么网2自然就在第3层，然后网5到网6有一个垂直约束，那么网5必须在网6的上面，由于网2和网5之间存在水平约束，所以它们不能分布在同一层，那么将网5布在第5层，网6布在第6层，最后就剩下网4，由于网4和网5，网6既没有垂直约束，又没有水平约束，所以它可以和网5或网6布在一层，那么将网4布在第5层。因此，布线后CRP如图4所示。

图4 布线之后的CRP

综上所述，含有一个狗腿是通道布线的最小轨道的一个下界为lb4=|S|+max{C(HCG′),P(VCG′)}+1，这种算法可以将复杂的问题转化为几个分问题进行研究，简化了计算。该算法能处理垂直约束图包含一个有向圈的情况，改进了前人的算法。

[1] CHAO H Y, HARPER M P. An efficient lower bound algorithm for channel routing[J]. Integration the Vlsi Journal, 1996, 20(2):193-209.

[2] C.Y. LEE. An algorithm for connections and its applications[J]. IRE Trans on electronic computers, 1961, EC-10(3):346-365.

[3] GAO S, HAMBRUSCH S. Two-layer channel routing with vertical unit-length overlap[J]. Algorithmica, 1986, 1(1):223-232.

[4] HADLOCK. A shortest path algorithm for grid graphs[J]. Networks, 1977, 7(4):323-334.

[5] T. N.BUI, S. CHAUDURI, F. T. LEIGHTON,et al. Graph bisection algorithms with good average case behaviour[J]. Combinatorica, 1987,7(2):181-192.

[6] YOSHIMURA T, KUH E S. Efficient Algorithms for Channel Routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982, 1(1):25-35.

[7] SZYMANSKI T G. Dogleg Channel Routing is NP-Complete[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985, 4(1):31-41.

[8] WANG J S, LEE R C T. An Efficient Channel Routing Algorithm to Yield an Optimal Solution[J]. IEEE Transactions on Computers, 1990, 39(7):957-962.

[9] K. MIKAMI, K.TABUCHI. A computer program for optimal routing of printed circuit connectors[J]. IFIPS Proc., 1968: 1 475-1 478.[10] BAKER B S, BHATT S N, LEIGHTON F T. An approximation algorithm for Manhattan routing[M]. New York: Advances in Computer Research, 1984:477-486.

[11] J. HEISTERMAN, T. LENGAUER. The efficient solution of integer programs for hierarchical global routing[J]. IEEE Trans. CAD, 1991,10(6):748-753.

[12] R.C CAEDEN IV, C.K. CHENG. A global router using an efficient approximate multicommodity multiterminal flow algorithm[J]. Proc. of IEEE/ACM Design Au-tomation Conference, 1991:316-321.

[13] J. HUANG, X.L. HONG, C.K. CHENG, et al. An Efficient timing-driven global routing algorithm[J]. Proc. of IEEE/ACM Design Automation Conference, 1993: 596-599.

[14] X.L. HONG, T.X. XUE, J. HUANG, et al. An efficient timing driven global routing algorithm for gate array and standard cell design[J]. IEEE Trans. on CAD, 1997, 16(11): 1 323-1 331.

[15] RECSKI A, SALAMON G, SZESZLER D. Improving size-bounds for subcases of square-shaped switchbox routing[J]. Electrical Engineering, 2004, 48(1):55-60.

[16] GUPTA U I, LEE D T, LEUNG J Y T. An Optimal Solution for the Channel-Assignment Problem[J]. IEEE Transactions on Computers, 1979, C-28(11):807-810.

A Graph Algorithm for Routing Problem

ZHOU Xiao-na, GENG Xian-ya

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

The design of very large scale integrated circuits is one of the areas in which the methods of graph theory can be applied. The constraints of a channel routing problem can be represented by a horizontal constraint graph (HCG) and a vertical constraint graph (VCG). The width (number of tracks required for routing) is one of the areas in which the methods of graph theory can be applied. The main purpose of this paper lies in studying the channel routing problem with 2-layer Manhattan model, the width (number of tracks required for routing) of a channel being minimized. An algorithm is given using critical net when the routing problem has dogleg. Then the efficient algorithms for 2-layer Manhattan routing problem is obtained, which can be used in the actual wiring process.

channel routing; critical net; dogleg

2016-05-23

国家自然科学基金(11401008);中国博士后基金面上项目(2016M592030)

周晓娜(1989-)，女，河南三门峡人，在读硕士，研究方向：图论及其应用。

O157.6

A

1672-1098(2016)06-0047-05