基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線新算法

廖海濤，史 崢，張 騰

(浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，杭州 310027)

基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線新算法

廖海濤，史 崢，張 騰

(浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，杭州 310027)

在超大規(guī)模集成電路設(shè)計(jì)中，全局布線是非常重要的步驟。工業(yè)界普遍采用經(jīng)典的迷宮算法及其改進(jìn)算法解決全局布線問題。隨著工藝節(jié)點(diǎn)的減小，傳統(tǒng)迷宮算法復(fù)雜度高的缺點(diǎn)越來越明顯。針對(duì)傳統(tǒng)迷宮算法的復(fù)雜度會(huì)隨著布線規(guī)模的擴(kuò)大而迅速增加的問題，借助于邊界擴(kuò)張的概念，提出一種新的點(diǎn)對(duì)點(diǎn)布線路徑的搜索算法。摒棄了迷宮算法低效率的逐個(gè)節(jié)點(diǎn)擴(kuò)張的思想，通過自由節(jié)點(diǎn)的定義對(duì)節(jié)點(diǎn)邊界進(jìn)行迅速擴(kuò)張并不斷地找到新的自由節(jié)點(diǎn)，直到找出路徑或確定無解時(shí)結(jié)束。將該算法與經(jīng)典的布線算法進(jìn)行理論和實(shí)驗(yàn)比較，結(jié)果表明在大多數(shù)情況下該算法使用經(jīng)典算法7%～14%的運(yùn)行時(shí)間即可完成路徑搜索。

超大規(guī)模集成電路；全局布線；迷宮算法；點(diǎn)對(duì)點(diǎn)布線；邊界擴(kuò)張；自由節(jié)點(diǎn)

1 概述

全局布線是物理設(shè)計(jì)中布局之后的重要步驟，布局確定了模塊在芯片上的位置以及模塊上各引腳的分布，并通過網(wǎng)表提供了各引腳間的互連信息。布線過程就是實(shí)現(xiàn)各模塊間的連接。全局布線作為布線過程的第一步，目的就是把每條線網(wǎng)的各個(gè)部分合理地分配到各個(gè)布線通道中去，為之后的詳細(xì)布線提供初始布線走向，這一階段布線結(jié)構(gòu)的好壞決定芯片的整體性能。

現(xiàn)有超大規(guī)模集成(Very Large Scale Inte grated, VLSI)電路計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)大多是基于統(tǒng)一標(biāo)準(zhǔn)的網(wǎng)格模型。這種模型的布線算法大致分為2類：迷宮算法和線搜索算法[1]。迷宮算法常見的是窮舉回溯的深度優(yōu)先搜索方法和層層推進(jìn)式的廣度優(yōu)先搜索方法。文獻(xiàn)[2]算法作為最原始的迷宮算法，采用的就是廣度優(yōu)先搜索方法。這類算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，并且總能夠保證找到最短路徑，而缺點(diǎn)在于其時(shí)間和空間復(fù)雜度都比較高[3]。為了降低復(fù)雜度，出現(xiàn)了許多改進(jìn)版本[4-6]，其中，A*[6]算法是目前工業(yè)界普遍使用的啟發(fā)式搜索算法，它通過選擇合適的啟發(fā)函數(shù)，使其尋找最優(yōu)路徑的搜索范圍比原始算法更小。國內(nèi)關(guān)于迷宮算法的研究[7-9]主要是針對(duì)原始迷宮算法加入啟發(fā)條件來改進(jìn)搜索效率。這些改進(jìn)算法并沒有改變傳統(tǒng)迷宮算法逐個(gè)節(jié)點(diǎn)的搜索方式，只是通過加入啟發(fā)條件來縮小搜索范圍，并沒有從根本上改變迷宮算法的復(fù)雜度。

為擺脫逐個(gè)節(jié)點(diǎn)搜索的限制，人們提出了線搜索算法?；舅枷胧菢?gòu)造一個(gè)比原始網(wǎng)格更加稀疏的子圖，通過在子圖中尋找最短路徑得到原格點(diǎn)中的路徑。較早的線搜索算法[10]被提出后，又有學(xué)者引入了新的連接圖來代替原始網(wǎng)格[11-12]，甚至有學(xué)者引入了一種新的迷宮驅(qū)動(dòng)型線搜索算法[13]。這些算法在理論上都比原始的迷宮算法復(fù)雜度要低，然而實(shí)際應(yīng)用中由于集成電路規(guī)模巨大，構(gòu)造這種子圖的時(shí)間代價(jià)往往非常大，因此這類算法并沒有被普遍采用，而只是在設(shè)計(jì)初期障礙數(shù)目較少時(shí)使用；此外一些線搜索算法甚至還無法保證搜索到布線路徑，即使這條路徑的確是存在的。國內(nèi)學(xué)者受到線搜索法的啟發(fā)也相應(yīng)提出用于VLSI二維布線的新方法[14]，也有學(xué)者將線搜索法與迷宮算法結(jié)合并將其應(yīng)用于三維電氣網(wǎng)絡(luò)的自動(dòng)布線中[15]。

本文提出一種新的算法，與線搜索算法類似，沒有使用逐個(gè)節(jié)點(diǎn)擴(kuò)散的搜索方式，而是給出了一種新的搜索方式。

2 基本概念和定義

2.1 網(wǎng)格模型

一般來講，全局布線問題可以建模為一個(gè)網(wǎng)格圖G=(V, E)，如圖1所示，圖中位于每個(gè)網(wǎng)格中心的點(diǎn)(用黑色圓點(diǎn)表示)V( vi, vj)={(vi, vj)|0≤i＜m∩0≤j＜n}就對(duì)應(yīng)代表了這個(gè)網(wǎng)格，而兩點(diǎn)之間的虛線則對(duì)應(yīng)代表了2個(gè)網(wǎng)格之間所夾的邊緣。

圖1 劃分成m×n的版圖和與之對(duì)應(yīng)的網(wǎng)格模型

2.2 自由節(jié)點(diǎn)的邊界

定義1(自由節(jié)點(diǎn)的邊和邊界) 如圖2所示，假設(shè)點(diǎn)A為自由節(jié)點(diǎn)，以A為原點(diǎn)向4個(gè)方向作垂線，遇到第1個(gè)障礙物時(shí)到達(dá)的節(jié)點(diǎn)為垂足，則與每條垂線垂直且經(jīng)過對(duì)應(yīng)垂足點(diǎn)的連續(xù)障礙節(jié)點(diǎn)構(gòu)成的線段稱為節(jié)點(diǎn)在該方向上的一條邊；以這4條邊確定的矩形區(qū)域稱為自由節(jié)點(diǎn)A的邊界。圖2中的加粗實(shí)線表示自由節(jié)點(diǎn)的邊界，加粗虛線表示自由節(jié)點(diǎn)到相應(yīng)方向邊上的垂線。

定義2(節(jié)點(diǎn)相對(duì)于邊界的內(nèi)與外) 是指該節(jié)點(diǎn)與另外某節(jié)點(diǎn)邊界的相對(duì)位置。如圖2所示，P1位于A點(diǎn)的邊界內(nèi)部，而P2與P3位于A點(diǎn)的邊界外部。

圖2 自由節(jié)點(diǎn)A的邊界示意圖

2.3 閉合邊、半開放邊與開放邊

定義3(閉合邊、半開放邊與開放邊) 本文提到的3種邊都是相對(duì)于某個(gè)節(jié)點(diǎn)而言的，同樣提到某條邊是閉合或者開放時(shí)，也是相對(duì)于某個(gè)確定節(jié)點(diǎn)而言的。圖3中點(diǎn)A的右側(cè)邊與點(diǎn)B的左側(cè)邊均為邊CD，但是C點(diǎn)左側(cè)有障礙點(diǎn)存在，形成一個(gè)向左下方向的直角(如圖中C點(diǎn)區(qū)域內(nèi)的拐角線標(biāo)注)這2條以點(diǎn)C為端點(diǎn)和射線構(gòu)成的區(qū)域把點(diǎn)A包含在內(nèi)，因此定義邊CD的上部端點(diǎn)C相對(duì)于點(diǎn)A來說是閉合的，但是相對(duì)于點(diǎn)B是開放的；同理邊CD的下部端點(diǎn)D相對(duì)于點(diǎn)A是開放的，但相對(duì)于點(diǎn)B卻是閉合的。然而無論是對(duì)點(diǎn)A還是點(diǎn)B，都只有一個(gè)開放端點(diǎn)和一個(gè)閉合端點(diǎn)，這種一個(gè)端點(diǎn)開放而另一個(gè)端點(diǎn)閉合的情況稱此邊為半開放邊。節(jié)點(diǎn)B的右邊界FG的2個(gè)端點(diǎn)旁邊都沒有其他的障礙點(diǎn)與之構(gòu)成能夠包含節(jié)點(diǎn)B的直角，它們相對(duì)于節(jié)點(diǎn)B都是開放的。這種2個(gè)端點(diǎn)相對(duì)于該節(jié)點(diǎn)都開放的邊稱作開放邊。同樣可以分析，節(jié)點(diǎn)A的上邊界EC 的2個(gè)端點(diǎn)相對(duì)于節(jié)點(diǎn)A都是閉合的。這種2個(gè)端點(diǎn)都閉合的邊稱作閉合邊。圖3中的加粗實(shí)線表示自由節(jié)點(diǎn)邊界上的拐角，加粗虛線表示自由節(jié)點(diǎn)到相應(yīng)方向邊上的垂線。

圖3 3種不同類型的邊

性質(zhì)1整個(gè)網(wǎng)格模型的4條邊框中的每一條對(duì)任意節(jié)點(diǎn)都是閉合的。這是由任何節(jié)點(diǎn)(包括空白節(jié)點(diǎn)和障礙節(jié)點(diǎn))都必須在網(wǎng)格內(nèi)部決定的。

定義4(邊的有效長度) 是指一條邊的非閉合部分長度。

定義5(開放端點(diǎn)) 開放邊與半開放邊中非閉合一端的端點(diǎn)稱為開放端點(diǎn)。一條開放邊有2個(gè)開放端點(diǎn)，而半開放邊只有1個(gè)開放端點(diǎn)。

定義6(完全閉合) 是指一個(gè)自由節(jié)點(diǎn)的4條邊界均為閉合邊。

2.4 自由節(jié)點(diǎn)

定義7(自由節(jié)點(diǎn)) 是指可以逃離邊界的點(diǎn)。自由節(jié)點(diǎn)必須同時(shí)滿足以下2點(diǎn)：(1)必須是在前一級(jí)自由節(jié)點(diǎn)的邊界外部且與邊界鄰接；(2)必須是前一級(jí)自由節(jié)點(diǎn)的開放邊端點(diǎn)的鄰近點(diǎn)。一個(gè)實(shí)例如圖4所示，節(jié)點(diǎn)P1和P2即為新的自由節(jié)點(diǎn)。圖中的加粗實(shí)線表示自由節(jié)點(diǎn)的邊界，加粗虛線表示自由節(jié)點(diǎn)2個(gè)自由節(jié)點(diǎn)間的連接線。

圖4 節(jié)點(diǎn)P1與P2為新的自由節(jié)點(diǎn)實(shí)例

性質(zhì)2自由節(jié)點(diǎn)與它對(duì)應(yīng)的上一級(jí)自由節(jié)點(diǎn)之間可以通過一條固定路徑的Z型路徑或者L型路徑相連。

證明：以圖4中的節(jié)點(diǎn)P2和它的上一級(jí)節(jié)點(diǎn)A來證明。設(shè)A點(diǎn)坐標(biāo)為(x1,y1)，P2點(diǎn)坐標(biāo)為(x2,y2)。由于P2點(diǎn)處于A點(diǎn)的邊界鄰接位置，則可以找到這樣一點(diǎn)N(x3,y3)，使得N與P2可以直接以直線相連。

下面證明點(diǎn)N與點(diǎn)A可以簡單連接(反證法)：由于點(diǎn)N處于邊P1P2的端點(diǎn)處，假設(shè)點(diǎn)N與點(diǎn)A之間不能簡單連接，則必然有一個(gè)障礙存在于A到邊P1P2之間或者A到該邊的垂足與點(diǎn)N之間，若該障礙存在于A到邊P1P2之間，則A點(diǎn)下邊界將會(huì)改變而不再是P1P2，與已知條件沖突；若該障礙存在于A到該邊的垂足與點(diǎn)N之間，則A點(diǎn)下邊界的右端點(diǎn)將不再是開放邊，也與已知條件沖突。故假設(shè)不成立，即點(diǎn)N與點(diǎn)A可以簡單連接。同樣對(duì)于點(diǎn)A處于下邊界的位置時(shí)，點(diǎn)N與點(diǎn)A可以直接進(jìn)行簡單連接。

由以上2點(diǎn)可知，節(jié)點(diǎn)P2和它的上一級(jí)節(jié)點(diǎn)A之間可以通過一條固定路徑的Z型路徑或者L型路徑相連，證畢。

定義8(簡單連接) 如果兩點(diǎn)之間可以通過直線或L型路徑相連，即2個(gè)節(jié)點(diǎn)具有相同的橫坐標(biāo)或縱坐標(biāo)且與該節(jié)點(diǎn)之間沒有障礙，或者可以找到一個(gè)新的節(jié)點(diǎn)，使得該節(jié)點(diǎn)分別與2個(gè)原來的節(jié)點(diǎn)有相同的橫坐標(biāo)和縱坐標(biāo)且與該節(jié)點(diǎn)之間都沒有障礙。定義兩點(diǎn)之間的這種連接為簡單連接。如圖5中的2幅圖，節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的連接都屬于簡單連接。

圖5 2種簡單連接

3 算法的基本思想、實(shí)現(xiàn)與分析

3.1 算法的基本思想

對(duì)于兩點(diǎn)間布線路徑查找問題，本文算法的基本指導(dǎo)思想是從源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)開始，通過節(jié)點(diǎn)的邊界找到新的下一級(jí)節(jié)點(diǎn)，再通過下一級(jí)節(jié)點(diǎn)的邊界擴(kuò)張找到新的子節(jié)點(diǎn)，直到從源節(jié)點(diǎn)擴(kuò)散出的子節(jié)點(diǎn)與從目標(biāo)節(jié)點(diǎn)擴(kuò)散出的子節(jié)點(diǎn)可以通過簡單連接實(shí)現(xiàn)互連為止。

可以將本文算法思想抽象理解為樹的結(jié)構(gòu)，如圖6所示，源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)T分別是2棵樹的根節(jié)點(diǎn)，讓這2棵樹不斷向下生長直到2棵樹的葉節(jié)點(diǎn)有相交部分為止。圖中所示為通過節(jié)點(diǎn)Sm與節(jié)點(diǎn)Tn的連接找到了布線路徑。

圖6 算法的抽象樹示意圖

每當(dāng)一個(gè)父親節(jié)點(diǎn)產(chǎn)生新的子節(jié)點(diǎn)時(shí)，就表明通過自由節(jié)點(diǎn)的邊界擴(kuò)張找到了新的自由節(jié)點(diǎn)。樹的高度相當(dāng)于節(jié)點(diǎn)擴(kuò)散的效率，高度越大說明迷宮地形越復(fù)雜。在每一級(jí)父親節(jié)點(diǎn)產(chǎn)生子節(jié)點(diǎn)之前都會(huì)對(duì)2棵樹進(jìn)行比較，取節(jié)點(diǎn)較少的樹進(jìn)行生長以保證查找效率。

3.2 算法的實(shí)現(xiàn)

給定網(wǎng)格G=(V, E)及源節(jié)點(diǎn)S=(Si, Sj)和目的節(jié)點(diǎn)T=(Ti,Tj)，增加集合FREEPOINTSA與FREEPOINTB分別存放起點(diǎn)和終點(diǎn)引出的最新的自由節(jié)點(diǎn)；增加標(biāo)志位DETOUR表示是否存在迂回節(jié)點(diǎn)；用四點(diǎn)集合CLOSED表示發(fā)生完全閉合時(shí)自由節(jié)點(diǎn)的邊界范圍。

算法1基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線算法

步驟1初始化，令FREEPOINTSA={S}, FREEPOINTSB= {T}，迂回標(biāo)志位DETOUR=0，集合CLOSED={0,0,0,0}，并以FREEPOINTSA為起始集合進(jìn)入步驟2。

步驟2從傳入此步驟的集合(以下稱為起始集合，而另一個(gè)集合則稱作目標(biāo)集合)開始，對(duì)集合中的每個(gè)自由節(jié)點(diǎn)進(jìn)行邊界擴(kuò)張，獲取新的自由節(jié)點(diǎn)，直到算法終止。

(1)判斷起始集合與目標(biāo)集合中是否有節(jié)點(diǎn)可以通過直線或者L型路徑進(jìn)行簡單連接，若有，則轉(zhuǎn)步驟3。

(2)從起始集合開始，利用算法2檢測(cè)每個(gè)節(jié)點(diǎn)的4個(gè)邊界，獲取4條邊的有效長度，對(duì)開放邊和半開放邊，記下開放端點(diǎn)的標(biāo)記位，保證每個(gè)開放邊只有一個(gè)自由節(jié)點(diǎn)。

(3)判斷目標(biāo)集合中是否有自由節(jié)點(diǎn)存在于起始集合自由節(jié)點(diǎn)的邊界內(nèi)部。若不存在，以起始集合為輸入轉(zhuǎn)步驟(4)；若存在，以目標(biāo)集合為輸入轉(zhuǎn)步驟(4)。

(4)判斷傳入的起始集合中每個(gè)自由節(jié)點(diǎn)的邊界是否為完全閉合，若是完全閉合，判斷閉合原因，如果是障礙引起的完全閉合，則轉(zhuǎn)移節(jié)點(diǎn)到可以使邊界改變的邊，刪掉原節(jié)點(diǎn)，增加符合條件的新節(jié)點(diǎn)；若是由前一級(jí)節(jié)點(diǎn)的邊界引起的完全閉合，則利用算法2重新計(jì)算該節(jié)點(diǎn)的邊界。

(5)記下此時(shí)的邊界4點(diǎn)值并與CLOSED中的4個(gè)值相比較，若相同，說明發(fā)生循環(huán)，此節(jié)點(diǎn)無法通過新的自由節(jié)點(diǎn)逃離邊界。若起始集合每個(gè)自由節(jié)點(diǎn)均無法逃離，則無路可走，算法結(jié)束；否則將DETOUR置1，并以目標(biāo)集合為輸入轉(zhuǎn)步驟(1)。

(6)獲取起始集合中新的自由節(jié)點(diǎn)，更新起始集合，并讓集合中的每個(gè)自由節(jié)點(diǎn)通過指針指向能夠得到該節(jié)點(diǎn)的前一級(jí)自由節(jié)點(diǎn)。例如，若自由節(jié)點(diǎn)P1通過邊界擴(kuò)張得到了新的自由節(jié)點(diǎn)P2，則通過指針讓P2指向P1(即P2→P1)，目的是在后面的布線步驟中可以直接找到前一節(jié)點(diǎn)。

(7)判斷起始集合與目標(biāo)集合中自由節(jié)點(diǎn)的數(shù)量，從節(jié)點(diǎn)數(shù)目少的集合作為起始集合轉(zhuǎn)到步驟(1)。

步驟3這里的輸入是分別來自2個(gè)集合中的某個(gè)自由節(jié)點(diǎn)，進(jìn)入此步說明已經(jīng)找到通路，2個(gè)集合中的自由節(jié)點(diǎn)可以由一條直線或者L型路徑相連。這一步的主要工作便是布線與迂回處理。

(1)用直線或者L型路徑連接這2個(gè)自由節(jié)點(diǎn)。

(2)對(duì)每個(gè)集合中的自由節(jié)點(diǎn)，通過步驟2中的指針連接前一級(jí)自由節(jié)點(diǎn)，直到到達(dá)S或T為止。

(3)檢測(cè)DETOUR的值，若DETOUR=1，使用算法3消除迂回路徑，算法結(jié)束；若DETOUR=0，算法結(jié)束。

算法2獲取自由節(jié)點(diǎn)的邊界算法

(1)檢查該自由節(jié)點(diǎn)是否是節(jié)點(diǎn)S或者節(jié)點(diǎn)T，若是，則轉(zhuǎn)步驟(2)；若不是，則轉(zhuǎn)步驟(3)。

(2)以自由節(jié)點(diǎn)為中心向4個(gè)方向延伸檢測(cè)，遇到障礙物時(shí)停止，記下該障礙的位置，4個(gè)方向的障礙邊圍成的邊界即為該節(jié)點(diǎn)的邊界。

(3)以節(jié)點(diǎn)為中心向4個(gè)方向延伸檢測(cè)，遇到障礙物或前一級(jí)節(jié)點(diǎn)的邊界時(shí)停止，記下該障礙或邊界的位置，4個(gè)方向的障礙或邊圍成的邊界即為該節(jié)點(diǎn)的邊界。

算法3消除迂回路徑算法

對(duì)已經(jīng)布線的所有非起始自由節(jié)點(diǎn)(即，除了點(diǎn)S與點(diǎn)T之外的自由節(jié)點(diǎn))進(jìn)行檢查，一個(gè)正常的自由節(jié)點(diǎn)會(huì)有2條相互垂直的布線路徑，而迂回節(jié)點(diǎn)則只有一條。對(duì)于每個(gè)迂回節(jié)點(diǎn)：

(1)將此節(jié)點(diǎn)移動(dòng)到布線路徑方向的相鄰節(jié)點(diǎn)，并刪除與原節(jié)點(diǎn)間的路徑。

(2)對(duì)新節(jié)點(diǎn)進(jìn)行檢查是否為迂回節(jié)點(diǎn)，若是迂回節(jié)點(diǎn)，則轉(zhuǎn)步驟(1)；若不是，算法結(jié)束。

消除迂回路徑算法的示意圖如圖7所示，圖中X標(biāo)記的部分將被消除，P2會(huì)移動(dòng)到?jīng)]有迂回路徑的節(jié)點(diǎn)。

圖7 迂回路徑的消除

3.3 算法的復(fù)雜度分析

由于本文算法從2個(gè)需要連線的起點(diǎn)開始以邊界向外擴(kuò)張，因此算法的復(fù)雜度與障礙物的分布和障礙物的邊長有關(guān)，整個(gè)算法有2個(gè)主要耗時(shí)部分：第1部分是邊界擴(kuò)張和查找新的自由節(jié)點(diǎn)；第2部分是每次邊界擴(kuò)張之前進(jìn)行的自由節(jié)點(diǎn)間是否可以由簡單路徑相連的判斷。

先分析第1部分的復(fù)雜度：假設(shè)整個(gè)搜索路徑的過程中所使用到的開放端點(diǎn)數(shù)為e(并不是所有的開放端點(diǎn)都會(huì)被使用到)，這些開放端點(diǎn)都是自由節(jié)點(diǎn)；且與每一個(gè)使用到的開放端點(diǎn)iP對(duì)應(yīng)的邊界周長為Ci，該節(jié)點(diǎn)邊界所在的4條邊在邊界內(nèi)部的有效長度之和為Si，該節(jié)點(diǎn)邊界所在的4條邊的實(shí)際長度之和為Li那么有Si≤Li，且整個(gè)算法過程中搜索的節(jié)點(diǎn)總數(shù)為：自由節(jié)點(diǎn)的4條邊界長度與其實(shí)際長度不一定相等，方便起見取兩者近似相等，有ii

L?C，于是式(1)可得到：

在最壞的情況下，需要把所有遇到的障礙邊都搜索到而且每條障礙邊都會(huì)被它兩側(cè)的自由節(jié)點(diǎn)搜索一遍，也就是說每條障礙邊都會(huì)被搜索2次。假設(shè)所遇到的障礙物邊的總長度為L，于是有：

由式(2)與式(3)可以知道：T=3L，即該算法的邊界擴(kuò)張部分的時(shí)間復(fù)雜度為O( L)。

第2部分的復(fù)雜度主要是由2個(gè)源節(jié)點(diǎn)擴(kuò)散出來的新的自由節(jié)點(diǎn)間是否可以通過簡單路徑相連，這里所有判斷的2個(gè)節(jié)點(diǎn)都是確定位置的，而且簡單路徑的路徑判斷也最多只有2種情況，所需要的時(shí)間也與2個(gè)節(jié)點(diǎn)的位置有關(guān)。取最壞的情況來分析，假設(shè)所有自由節(jié)點(diǎn)都存在于整個(gè)網(wǎng)格G的對(duì)角上(實(shí)際當(dāng)然不可能如此，但這2個(gè)節(jié)點(diǎn)必定位于網(wǎng)格G中且距離不可能比對(duì)角距離更遠(yuǎn))，那么對(duì)于一般情況而言，必然存在一個(gè)值k∈(0,1]，使得對(duì)于所有e個(gè)自由節(jié)點(diǎn)進(jìn)行判斷花費(fèi)的時(shí)間為ke( m+n)2，那么對(duì)于整個(gè)算法中所有自由節(jié)點(diǎn)間是否可以用簡單路徑相連判斷的復(fù)雜度就是O( e( m+n))。

綜上所述，該算法總的時(shí)間復(fù)雜度為O( L+e( m+n))，由于僅需要保存新的自由節(jié)點(diǎn)，算法空間復(fù)雜度為O( e)。

4 實(shí)驗(yàn)結(jié)果與分析

將本文算法與經(jīng)典迷宮算法和A*算法應(yīng)用于具體實(shí)例中，其中A*算法使用當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的Manhattan距離作為啟發(fā)條件，迷宮由隨機(jī)產(chǎn)生障礙節(jié)點(diǎn)的程序隨機(jī)生成。針對(duì)不同規(guī)模的迷宮，對(duì)3種算法獲取布線路徑所需要時(shí)間和與經(jīng)典算法運(yùn)行時(shí)間之比分別作統(tǒng)計(jì)，見表1。

表1 3種算法的實(shí)驗(yàn)比較

從表中數(shù)據(jù)可以看出，A*算法與本文算法都能夠明顯減少運(yùn)行時(shí)間。在規(guī)模最小的8×8迷宮中，A*算法使用了經(jīng)典算法64.7%的運(yùn)行時(shí)間，本文算法則使用了41.2%；在其他5組較大規(guī)模的迷宮中，A*算法使用的時(shí)間在經(jīng)典算法的36%～60%之間，而本文算法則僅僅使用了7%～14%的時(shí)間，可見本文算法要明顯優(yōu)于另外2種算法。在相同疏密度(即障礙與路徑比)的迷宮中，隨著迷宮規(guī)模的增大，經(jīng)典迷宮算法需要查找的節(jié)點(diǎn)成倍增加，導(dǎo)致運(yùn)行時(shí)間迅速增長；A*算法的性能略有提升，說明加入啟發(fā)條件之后對(duì)于大規(guī)模迷宮查找路徑確實(shí)有一定的指導(dǎo)作用；而本文算法的運(yùn)行時(shí)間相比于迷宮規(guī)模的增長速度來看相對(duì)穩(wěn)定，線性效果明顯，因此，在規(guī)模較大的迷宮中運(yùn)行的整體效率比規(guī)模較小的迷宮有所提高。

由第3節(jié)中得出的時(shí)間復(fù)雜度可以看出，本文算法的復(fù)雜度與障礙物的數(shù)量和分布相關(guān)。在迷宮的疏密度較低時(shí)，后續(xù)實(shí)驗(yàn)表明運(yùn)行時(shí)間可以進(jìn)一步減少到5%甚至更低，然而在迷宮的疏密度較高且障礙分布雜亂時(shí)算法的效率會(huì)隨之降低，說明在迷宮的疏密度很高并且障礙分布雜亂時(shí)算法的效率會(huì)比較低。這是因?yàn)楸疚乃惴ǖ闹笇?dǎo)思想是讓拐線盡量少來快速地找到路徑，障礙分布雜亂時(shí)產(chǎn)生的新自由節(jié)點(diǎn)會(huì)更多，復(fù)雜度隨之增加。

5 結(jié)束語

本文提出一種新的點(diǎn)對(duì)點(diǎn)布線的算法，算法的創(chuàng)新點(diǎn)在于：(1)提出了自由節(jié)點(diǎn)和節(jié)點(diǎn)邊界等新的概念，每一個(gè)自由節(jié)點(diǎn)的出現(xiàn)都以逃離與它對(duì)應(yīng)的上一級(jí)自由節(jié)點(diǎn)的邊界為目的。(2)算法通過節(jié)點(diǎn)邊界的擴(kuò)張實(shí)現(xiàn)自由節(jié)點(diǎn)的轉(zhuǎn)移，從而快速地從源節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)擴(kuò)散，大大提高了搜索效率。該算法的優(yōu)點(diǎn)是既克服了傳統(tǒng)迷宮算法基于遍歷網(wǎng)格的高復(fù)雜度的缺點(diǎn)，也無需在龐大的網(wǎng)格中搜索障礙構(gòu)造子圖。通過對(duì)自由節(jié)點(diǎn)邊界的擴(kuò)張不斷搜索路徑，理論分析和實(shí)驗(yàn)結(jié)果表明，該算法可以很好地解決點(diǎn)對(duì)點(diǎn)的布線問題且復(fù)雜度較低。以后的工作可考慮加入啟發(fā)條件，以降低迷宮疏密度較高的特殊情況出現(xiàn)時(shí)算法的復(fù)雜度。

[1] Alpert C J, Mehta D P, Sapatneka r S S. Handbook of Algorithms for Physical Design A utomation[M]. [S. l.]: Auerbach Publications, 2009.

[2] Lee C Y. A n Algorithm for Path Connection and Its Applications[J]. IRE Transactions on Electronic Computers, 1961, 10(3): 346-365.

[3] 周 智, 蔣承東. Ma nhattan空間有障礙的最短路徑和3-Steiner樹算法[J]. 軟件學(xué)報(bào), 2003, 14(9): 1503-1514.

[4] Akers S. A Modification of Lee’s Path Connection Algorithm[J]. IEEE Transactions on Electronic Computers, 1967, 16(2): 97- 98. [5] Soukup J. Fast Maze Router[C]//Proc. of t he 15th Design Automation Conference. Piscataway, USA: IEEE Press, 1978: 100-102.

[6] Hart P E. A Formal B asis for the H euristic Determination o f Minimum Cost Paths in Graphs[J]. IEEE T rans. on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[7] 胡湘萍, 陳利軍. 迷宮算法的改進(jìn)與動(dòng)態(tài)實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù), 2007, 2(8): 490-491.

[8] 陳傳波, 胡誼東, 何 力, 等. 目標(biāo)驅(qū)動(dòng)的迷宮布線算法及優(yōu)化[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2004, 32(1): 49-51.

[9] 權(quán)建洲, 韓明晶, 李 智. 基于改進(jìn)A*算法的電子制造裝備布線方法研究[J]. 中國科技論文在線, 2009, 4(8): 555-559.

[10] Hightower D W. A Solution to Line-routing Problems on the Continuous Plane[C]//Proc. of the 6th Annual Conference on Design Automation. New York, USA: ACM Press, 1969: 1-24.

[11] Zheng Siqing, Lim J S. Finding Obstacle- avoiding Shortest Paths Using Implicit Connection Graphs[J]. IE EE Transactions on Computer Aided Design, 1996, 15(1): 103-110.

[12] Wu Y F, Widmayer P. Rectilinear Shortest Paths and Minimum Spanning Trees i n the Presence of Rectilinear O bstacles[J]. IEEE Transactions on Computers, 1987, 36(3): 321-331.

[13] Zheng Siqing, Lim J S, Iyengar S S. Efficient Maze-running and Line-search Algorithms for VLSI Layout[C]//Proc. of Southeastcon’93. Charlotte, USA: IEEE Press, 1993: 275-282.

[14] 楊瑞元. 無網(wǎng)格線探索布線算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1998, 10(3): 200-207.

[15] 蔡 毅, 王彥偉, 黃正東. 基于UG的三維電氣自動(dòng)布線技術(shù)研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(8): 68-72.

編輯 顧逸斐

New Algorithm for Point-to-Point Wiring Based on Boundary Expansion

LIAO Hai-tao, SHI Zheng, ZHANG Teng

(Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China)

Global wiring is a very important step in the Very Large Scale Inte grated(VLSI) cir cuits design. Cla ssic maze routing algorithm and its improved versions are widely used to deal with global routing pr oblems in the in dustrial sector. With the dec reasing process node, the shortcoming of the high complexity of the maze routing algorithm becomes increasi ngly evident. By means of a new concept boundary expansion, this paper presents a new point-to-point wiring path search algorithm to solve the high complexity problem of rapidly increase with the expansion of the scale of routing. With the definition of free node, the new algorithm abandons the inefficient node by node expansion method. Instead, this algorithm expands the bo undary and finds ne w free nodes and will not terminat e until find out a path or determine that no solution is available. The theoretical and experimental comparisons are conducted between the proposed algorithm and classic routing algorithms. Experimental results show that the proposed algorithm can complete the routing wit h the runtime of 7%～14% of the classic algorithm in most cases.

Very Large Scale Integrated(VLSI) circuits; global wiring; maze routing algorithm; point-to-point wiring; boundary expansion; free node

10.3969/j.issn.1000-3428.2014.05.062

國家自然科學(xué)基金資助項(xiàng)目(61204111)。

廖海濤(1988－)，男，碩士研究生，主研方向：超大規(guī)模集成電路，計(jì)算機(jī)輔助設(shè)計(jì)；史 崢，副研究員、博士；張 騰，碩士研究生。

2013-04-15

2013-05-14E-mail：liaoht@vlsi.zju.edu.cn

1000-3428(2014)05-0299-05

A

TP312