一個(gè)通道布線問題的圖論算法

周曉娜，耿顯亞

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

一個(gè)通道布線問題的圖論算法

周曉娜，耿顯亞

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

圖論的思想方法在大規(guī)模集成電路布線中有廣泛的應(yīng)用。通道布線的線網(wǎng)結(jié)構(gòu)可以用水平約束圖和垂直約束圖來描述，利用圖論的思想可以處理布線軌道高度問題。研究運(yùn)用圖論的方法來解決超大規(guī)模集成電路布線中的軌道高度問題。通過尋找并消除臨界網(wǎng)的方法給出布線的一個(gè)新的算法，該算法能夠得到軌道高度的一個(gè)下界，并對在含有一個(gè)狗腿的情況下如何布線進(jìn)行了描述，并設(shè)計(jì)出能運(yùn)用到實(shí)際布線工藝中的兩層具有曼哈頓模型的通道布線算法。

通道布線；臨界網(wǎng)；狗腿

1 通道布線的線網(wǎng)關(guān)系

布線的首要目標(biāo)是百分之百的完成模塊間的互連，其次是完成布線的前提下進(jìn)一步優(yōu)化布線結(jié)果。在70年代，逐步提出了“通道區(qū)布線”與“分級布線”的概念。布線方法由面向線網(wǎng)轉(zhuǎn)為面向通道區(qū)，從而引出了通道布線，常見的通道布線算法有Hashimoto和Steven提出的左邊算法、Yoshimura和Kuh提出的合并算法以及貪婪算法和匹配算法等。根據(jù)通道區(qū)域的劃分，通道布線算法又可以分為單層布線算法、雙層布線算法及多層布線算法，其中，對于雙層通道區(qū)域的研究較為透徹一些。許多通道布線的研究集中在設(shè)計(jì)能夠減少通道面積的高效的啟發(fā)式方法。這些算法大部分都能對一些有名的布線問題提供最優(yōu)軌道數(shù)的布線解決方法。然而，對于估算所需軌道數(shù)的下界問題關(guān)注的較少。

通道布線在超大規(guī)模集成電路(VLST)芯片結(jié)構(gòu)中起重要作用，雙層通道是一個(gè)芯片上的一個(gè)網(wǎng)格矩形區(qū)域，芯片由一個(gè)水平流向的金屬層和一個(gè)垂直方向的多晶硅組成，水平層的金屬層稱為軌道，豎直層的金屬層稱為列，在頂部和底部分布著固定的節(jié)點(diǎn)，通道的左右兩邊都流動(dòng)著接線端子，每組都需要通過電力連接起來，稱為線網(wǎng)，一個(gè)線網(wǎng)可以將通道頂部和底部的節(jié)點(diǎn)連接起來，從左邊和右邊退出通道。

圖論的思想方法在超大規(guī)模集成電路布線中有著被廣泛地應(yīng)用, 近年來國內(nèi)外學(xué)者做了大量的研究工作, 也得到了許多好的成果[1-6]。 2 層通道布線是一類很普遍并且研究的比較多的布線類型，見文獻(xiàn)[7-9]。對于2層通道布線問題，有很多比較好的啟發(fā)式算法解決這類問題[10-12]。 另外還有很多理論上比較好的改進(jìn)結(jié)果[13-16]。

在通道中，大部分線網(wǎng)布線時(shí)只需要占據(jù)一個(gè)軌道，稱占據(jù)兩個(gè)不同軌道的線網(wǎng)為狗腿。對于一個(gè)通道布線問題，令S*表示需要軌道的最小數(shù)量，如果lb≤S*≤ub，那么稱lb為一個(gè)下界，ub為一個(gè)上界。顯然，lb(ub)應(yīng)該盡可能大(小),以使lb=S*=ub。 考慮兩層通道布線問題，本文的主要目標(biāo)是尋找含有一個(gè)狗腿通道布線的S*的下界。

一個(gè)通道布線問題(CRP)，可以由兩種類型的約束表示，水平約束圖和垂直約束圖。在水平層兩個(gè)網(wǎng)不重復(fù)的約束稱為水平約束，即li為網(wǎng)i最左邊的列，ri為網(wǎng)i最右邊的列，一個(gè)網(wǎng)i的第c列滿足li≤c≤ri, 那么組列[li,ri]稱為網(wǎng)i的度，若網(wǎng)i與網(wǎng)j之間的度重復(fù)，則存在一個(gè)水平約束。水平約束可以由一個(gè)無向圖(HCG)來表示，稱為水平約束圖。在圖中邊表示水平約束，頂點(diǎn)表示網(wǎng)。

在垂直層兩個(gè)網(wǎng)不重復(fù)的約束稱為垂直約束。如果網(wǎng)i連接最高行的第c列，網(wǎng)j連接最底行的第c列，i≠j，則存在一個(gè)從i到j(luò)的垂直約束。垂直約束可以由一個(gè)定向圖(VCG)表示，稱為垂直約束，在圖中，邊表示垂直約束，頂點(diǎn)表示網(wǎng)。

垂直約束具有傳遞性，如果從網(wǎng)i到網(wǎng)j存在一個(gè)垂直約束，而且從網(wǎng)j到網(wǎng)k在一個(gè)垂直約束，那么從網(wǎng)i到網(wǎng)k也必定有一個(gè)垂直約束。如果垂直約束圖中出現(xiàn)了圈，即循環(huán)約束，那么就需要加入狗腿來破除它。

如果一個(gè)垂直約束是從網(wǎng)i到網(wǎng)j的，那么網(wǎng)i和網(wǎng)j之間一定存在一個(gè)水平約束，因?yàn)樗鼈冎辽俟蚕硪粋€(gè)相同的列。

本文首先介紹兩種算法LB2和LB3，其中LB3是在LB2的基礎(chǔ)上進(jìn)行了改進(jìn)，最后考慮含有垂直約束圖有圈的通道布線，利用圖論的思想，給出一個(gè)新的算法LB4，并對如何布線進(jìn)行了描述。

2 LB2和LB3算法

在討論垂直約束圖有圈的通道布線問題之前，先介紹垂直約束圖無圈情況下的兩種最小軌道算法，其中LB3是對LB2的一種改進(jìn)。

LB2算法[1]：令G為一個(gè)定向的非循環(huán)圖，如果在G內(nèi)有一個(gè)從i到j(luò)的邊，那么i就稱為j的一個(gè)母輩，j就稱為i的子輩；如果在G內(nèi)有一個(gè)從i到j(luò)的路，那么稱i就是j的一個(gè)祖輩，j稱為i的孫輩，祖輩用Ai表示，孫輩用Di表示，如果Ai為空集，那么稱頂點(diǎn)i為一個(gè)首點(diǎn)，如果Di為空集，稱頂點(diǎn)j為一個(gè)尾點(diǎn)。如果每個(gè)頂點(diǎn)i的費(fèi)用ci是1，那么一個(gè)路P(∑i∈pci)的費(fèi)用為路中頂點(diǎn)個(gè)數(shù)。頂點(diǎn)集合為V的G的導(dǎo)出子圖用G[V]表示。為了方便，添加2個(gè)假點(diǎn)O和X(費(fèi)用為0)到G中，添加一條邊從O到i的邊，如果i是首點(diǎn)，添加一條邊從i到X的路，如果i是一個(gè)尾點(diǎn)，那么G就成為一個(gè)單入口和單出口的DAG。

LB3算法[1]：如果網(wǎng)i和網(wǎng)j之間有一個(gè)平行約束或一個(gè)垂直約束。那么稱兩個(gè)網(wǎng)i和j是不相容的。

顯然，不相容的網(wǎng)不能被分配到同一個(gè)軌道，構(gòu)造一個(gè)非定向圖，即ICG，其中頂點(diǎn)表示網(wǎng)，邊緣表示網(wǎng)之間的不相容關(guān)系，ICG中極大團(tuán)的基數(shù)是S*的下界，如果網(wǎng)i與其他所有網(wǎng)是不相容的，稱網(wǎng)i是臨界的。

LB3算法主要是將垂直約束圖中的臨界網(wǎng)分離出來，由于臨界網(wǎng)只能占據(jù)一個(gè)軌道，因此臨界網(wǎng)的最小軌道數(shù)為其頂點(diǎn)數(shù)之和|S|，之后畫出分離臨界網(wǎng)之后的垂直約束圖(VCG)和水平約束圖(HCG)，利用算法LB2算出它們的lb2。繼而求出lb3=|S|+lb2。

如圖1所示，CRP的VCG和HCG在(a)和(b)中被展示，很容易看出在(a)中dmax是4，(b)中的vmax是3，網(wǎng)1,2,3是臨界網(wǎng)，因此，S={1,2,3}，(c)和(d)為消除臨界網(wǎng)1,2,3之后的HCG和VCG，注意到，對VS({4,5,6})中每對網(wǎng)，在臨界網(wǎng)被消除之前和之后，水平約束和垂直約束是相同的，也就是說對VS中每一對網(wǎng)(b)中有一個(gè)從i到j(luò)的路當(dāng)且僅當(dāng)在d中有一個(gè)i到j(luò)的路，在(a)中有一個(gè)i到j(luò)的邊，當(dāng)且僅當(dāng)有一個(gè)i和j之間的邊，則d中vmax為2，dmax為2，因此，CRP的下界可以表示為3+max{2,3}=5。

圖1 VCG中不含圈情況

則LB3也CRP是的一個(gè)下界,即對于垂直約束圖不含圈的CRP，其下界可通過|S|+lb2來計(jì)算。

3 垂直約束圖含圈的圖論算法LB4

若CRP中垂直約束圖含圈，布線時(shí)必須要含有一個(gè)狗腿，那么它會(huì)多占有一個(gè)軌道。如果一個(gè)CRP中含有一個(gè)狗腿，而且它含有臨界網(wǎng)，那么該狗腿必定在臨界網(wǎng)中，那么其下界為CRP4=|S|+max{C(HCG′),P(VCG′)}+1。

LB4的步驟為:

(1)根據(jù)結(jié)點(diǎn)之間的關(guān)系，構(gòu)造出其對應(yīng)的水平約束圖和垂直約束圖。

(2)根據(jù)臨界網(wǎng)的定義，任意考慮一個(gè)點(diǎn)。如果該點(diǎn)與其它結(jié)點(diǎn)有水平約束或者垂直約束，則該點(diǎn)屬于臨界網(wǎng)集合；否則，該點(diǎn)就不屬于臨界網(wǎng)集合。

(3)考慮剩下的點(diǎn)，再從中任意選取一個(gè)點(diǎn)，判斷該點(diǎn)與其它點(diǎn)關(guān)系。如果該點(diǎn)與其它結(jié)點(diǎn)有水平約束或者垂直約束，則該點(diǎn)屬于臨界網(wǎng)集合。否則，該點(diǎn)就不屬于臨界網(wǎng)集合。

(4)按照步驟3的方法，依次考慮每個(gè)點(diǎn)，找出臨界網(wǎng)的集合S。

(5)從原來的水平約束圖中去掉臨界網(wǎng)集合中的點(diǎn)，得到新的水平約束圖，記為HCG′.HCG′的最大團(tuán)數(shù)記為C(HCG′)。

(6)從原來的垂直約束圖中去掉臨界網(wǎng)集合中的點(diǎn)，得到新的垂直約束圖，記為VCG′，VCG′的最長路數(shù)記為P(VCG′)。

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

下面用一個(gè)例子來說明：如圖2所示，a和b為CRP的水平約束圖和垂直約束圖，在垂直約束圖中出現(xiàn)一個(gè)圈，那么就需要一個(gè)狗腿(線網(wǎng)3)，而且線網(wǎng)3與其它線網(wǎng)之間存在水平約束或垂直約束，即其在臨界網(wǎng)中，同樣，網(wǎng)1,2也為臨界網(wǎng)，即S={1,2,3}，將臨界網(wǎng)消除后，得到c′和d′，這兩個(gè)圖中沒有邊，則C(HCG′)和P(VCG′)均為1，則從而它需要的最小軌道數(shù)為

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

現(xiàn)在來分析算法的復(fù)雜性:當(dāng)在選擇臨界網(wǎng)時(shí)，每次選擇一個(gè)點(diǎn)，需要固定的時(shí)間來確定該點(diǎn)是否在臨界網(wǎng)里面；當(dāng)去點(diǎn)臨界網(wǎng)布線時(shí)，需要求最長路的長度，同樣需要固定的時(shí)間，所以這個(gè)算法能在線性時(shí)間內(nèi)完成。

圖2 VCG中含圈情況

含有一個(gè)狗腿的通道布線:如果網(wǎng)i到網(wǎng)j有一個(gè)垂直約束，那么在布線的時(shí)候，網(wǎng)i必須在網(wǎng)j的上面。如果在網(wǎng)i和網(wǎng)j之間既沒有水平約束，也沒有垂直約束，那么它們可以分布在同一層。而對于臨界網(wǎng)，它只能單獨(dú)占據(jù)一層軌道。根據(jù)以上敘述，在布線的時(shí)候可以先根據(jù)垂直約束圖對臨界網(wǎng)進(jìn)行布線，然后再對沒有水平約束和垂直約束的網(wǎng)進(jìn)行布線，最后再根據(jù)垂直約束圖對剩下的網(wǎng)進(jìn)行布線。

布線的步驟如下：

(1)對臨界網(wǎng)進(jìn)行布線(先不考慮狗腿)。根據(jù)臨界網(wǎng)的定義，找出臨界網(wǎng)，觀察垂直約束圖，若點(diǎn)i到點(diǎn)j有一個(gè)垂直約束，那么將點(diǎn)i布在點(diǎn)j的上層。

(2)對狗腿(記為c)進(jìn)行布線。由于狗腿需要占據(jù)兩層軌道，根據(jù)垂直約束圖，如果a到c有一個(gè)垂直約束，那么c有一層在a的下面，如果c到b有一個(gè)垂直約束，那么c有一層在b的上面。

(3)對既沒有垂直約束也沒有水平約束的網(wǎng)進(jìn)行布線。依次考慮非臨界網(wǎng)中任意兩點(diǎn)d,e,如果它們之間既沒有垂直約束，也沒有水平約束，那么它們將分布在同一層。

(4)對剩下的網(wǎng)進(jìn)行布線。剩下的網(wǎng)肯定屬于非臨界網(wǎng)，但其只能占據(jù)一層軌道，只需觀察垂直約束圖類似于步驟一中的描述對其進(jìn)行布線。

通過一個(gè)例子來說明：

圖3 布線之前的CRP

如圖3所示，一個(gè)還沒有布線的CRP，并根據(jù)節(jié)點(diǎn)的關(guān)系構(gòu)造出CRP的HCG和VCG，其中網(wǎng)1和網(wǎng)3為臨界網(wǎng)，圖c,d為消除網(wǎng)1和網(wǎng)3后的HCG′和VCG′，可計(jì)算出最小軌道的下界為6，則需要6個(gè)軌道對其進(jìn)行布線，首先對臨界網(wǎng)進(jìn)行布線，在VCG中，可看到網(wǎng)3為狗腿，并且它所占有的軌道一層在網(wǎng)2的下面，一層在網(wǎng)1的上面，將網(wǎng)1布在第2層，網(wǎng)3在第1層和第4層，那么網(wǎng)2自然就在第3層，然后網(wǎng)5到網(wǎng)6有一個(gè)垂直約束，那么網(wǎng)5必須在網(wǎng)6的上面，由于網(wǎng)2和網(wǎng)5之間存在水平約束，所以它們不能分布在同一層，那么將網(wǎng)5布在第5層，網(wǎng)6布在第6層，最后就剩下網(wǎng)4，由于網(wǎng)4和網(wǎng)5，網(wǎng)6既沒有垂直約束，又沒有水平約束，所以它可以和網(wǎng)5或網(wǎng)6布在一層，那么將網(wǎng)4布在第5層。因此，布線后CRP如圖4所示。

圖4 布線之后的CRP

綜上所述，含有一個(gè)狗腿是通道布線的最小軌道的一個(gè)下界為lb4=|S|+max{C(HCG′),P(VCG′)}+1，這種算法可以將復(fù)雜的問題轉(zhuǎn)化為幾個(gè)分問題進(jìn)行研究，簡化了計(jì)算。該算法能處理垂直約束圖包含一個(gè)有向圈的情況，改進(jìn)了前人的算法。

[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

國家自然科學(xué)基金(11401008);中國博士后基金面上項(xiàng)目(2016M592030)

周曉娜(1989-)，女，河南三門峽人，在讀碩士，研究方向：圖論及其應(yīng)用。

O157.6

A

1672-1098(2016)06-0047-05