廖海濤，史 崢，張 騰

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

基于邊界擴張的點對點布線新算法

廖海濤，史 崢，張 騰

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

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

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

1 概述

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

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

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

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

2 基本概念和定義

2.1 網格模型

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

圖1 劃分成m×n的版圖和與之對應的網格模型

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

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

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

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

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

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

圖3 3種不同類型的邊

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

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

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

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

2.4 自由節(jié)點

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

圖4 節(jié)點P1與P2為新的自由節(jié)點實例

性質2自由節(jié)點與它對應的上一級自由節(jié)點之間可以通過一條固定路徑的Z型路徑或者L型路徑相連。

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

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

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

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

圖5 2種簡單連接

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

3.1 算法的基本思想

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

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

圖6 算法的抽象樹示意圖

每當一個父親節(jié)點產生新的子節(jié)點時，就表明通過自由節(jié)點的邊界擴張找到了新的自由節(jié)點。樹的高度相當于節(jié)點擴散的效率，高度越大說明迷宮地形越復雜。在每一級父親節(jié)點產生子節(jié)點之前都會對2棵樹進行比較，取節(jié)點較少的樹進行生長以保證查找效率。

3.2 算法的實現(xiàn)

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

算法1基于邊界擴張的點對點布線算法

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

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

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

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

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

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

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

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

(7)判斷起始集合與目標集合中自由節(jié)點的數量，從節(jié)點數目少的集合作為起始集合轉到步驟(1)。

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

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

(2)對每個集合中的自由節(jié)點，通過步驟2中的指針連接前一級自由節(jié)點，直到到達S或T為止。

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

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

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

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

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

算法3消除迂回路徑算法

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

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

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

消除迂回路徑算法的示意圖如圖7所示，圖中X標記的部分將被消除，P2會移動到沒有迂回路徑的節(jié)點。

圖7 迂回路徑的消除

3.3 算法的復雜度分析

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

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

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

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

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

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

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

4 實驗結果與分析

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

表1 3種算法的實驗比較

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

由第3節(jié)中得出的時間復雜度可以看出，本文算法的復雜度與障礙物的數量和分布相關。在迷宮的疏密度較低時，后續(xù)實驗表明運行時間可以進一步減少到5%甚至更低，然而在迷宮的疏密度較高且障礙分布雜亂時算法的效率會隨之降低，說明在迷宮的疏密度很高并且障礙分布雜亂時算法的效率會比較低。這是因為本文算法的指導思想是讓拐線盡量少來快速地找到路徑，障礙分布雜亂時產生的新自由節(jié)點會更多，復雜度隨之增加。

5 結束語

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

[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]. 軟件學報, 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] 胡湘萍, 陳利軍. 迷宮算法的改進與動態(tài)實現(xiàn)[J]. 電腦知識與技術, 2007, 2(8): 490-491.

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

[9] 權建洲, 韓明晶, 李 智. 基于改進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] 楊瑞元. 無網格線探索布線算法[J]. 計算機輔助設計與圖形學學報, 1998, 10(3): 200-207.

[15] 蔡 毅, 王彥偉, 黃正東. 基于UG的三維電氣自動布線技術研究[J]. 計算機工程與應用, 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

國家自然科學基金資助項目(61204111)。

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

2013-04-15

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

1000-3428(2014)05-0299-05

A

TP312