一種考慮擁擠度的布線模型及其算法

陳秀華

(福建船政交通職業(yè)學(xué)院公共教學(xué)部，福建福州 350007)

0 引言

在超大規(guī)模集成電路(very large scale integration，VLSI)設(shè)計(jì)中，布線是在規(guī)定的布線區(qū)域內(nèi)實(shí)現(xiàn)電路內(nèi)部各個(gè)模塊之間的物理連接，它是VLSI物理設(shè)計(jì)(physical design)中非常關(guān)鍵的步驟之一．當(dāng)前，超大規(guī)模半導(dǎo)體芯片的主流制造技術(shù)已經(jīng)向深亞微米(very－deep－submicron，VDSM)及納米推進(jìn)，集成電路設(shè)計(jì)的集成度和復(fù)雜性越來越高，設(shè)計(jì)規(guī)則尺度縮小，使得集成電路中由器件占主導(dǎo)地位變?yōu)榛ミB線占主導(dǎo)地位．如果在設(shè)計(jì)中不能充分考慮布線問題，設(shè)計(jì)性能就會(huì)出現(xiàn)嚴(yán)重偏差，從而反復(fù)迭代，使設(shè)計(jì)的周期變長．

布線問題是NP完全問題，研究者提出許多解決布線問題的算法，這些算法通常分為三類:串行布線、并行布線和多級(jí)層次布線．串行布線主要有李氏算法(Lee－algorithm)，線探索算法(Line search)，基于Steiner樹的算法等．李氏算法［1］于1961年由Lee提出，是尋找兩點(diǎn)間連接路徑的最廣泛使用的算法，實(shí)際上就是圖論上求最短路徑的算法．許多人對(duì)該算法進(jìn)行改進(jìn)以提高其布線效率［2－3］，形成一類統(tǒng)稱為迷宮算法的布線算法．線探索算法［4］主要思想是用直線代替點(diǎn)進(jìn)行搜索．基于Steiner樹的算法［5－6］目標(biāo)是構(gòu)造一棵最小直角Steiner樹，用啟發(fā)算法求得近似最優(yōu)解．并行布線算法則考慮所有線網(wǎng)布線，通常使用基于網(wǎng)絡(luò)流和整數(shù)規(guī)劃的算法．文獻(xiàn)［7］提出一種用多商品流模型并行布線的算法，文獻(xiàn)［8］提出一種0－1整數(shù)規(guī)劃的層次式并行布線算法．而多級(jí)層次布線算法同時(shí)具有串行和并行布線的特點(diǎn)，把線網(wǎng)分成多級(jí)，每一級(jí)彼此獨(dú)立的并行布線，級(jí)間串行布線．Cong等［9］提出一種多級(jí)布線系統(tǒng)MRS，在此基礎(chǔ)上許多研究者又提出改進(jìn)的多級(jí)層次布線算法［10－14］．

傳統(tǒng)的布線算法分成兩步:總體布線和詳細(xì)布線．總體布線把線網(wǎng)分配給布線區(qū)域，為每個(gè)線網(wǎng)生成一個(gè)布線路徑．詳細(xì)布線根據(jù)設(shè)計(jì)規(guī)則確定每個(gè)線網(wǎng)實(shí)際的通道和過孔［15］．在完成所有線網(wǎng)的總體布線后進(jìn)行詳細(xì)布線．由于總體布線結(jié)果不是詳細(xì)具體的線網(wǎng)走線，建立的布線資源模型不夠精確，使得詳細(xì)布線往往不能很好地進(jìn)行．傳統(tǒng)的總體布線和詳細(xì)布線兩個(gè)步驟不能夠處理超大規(guī)模芯片上的電路，必須采用分而治之的方法，把整個(gè)芯片分成幾個(gè)部分同時(shí)進(jìn)行布線［16］．

本文提出增加總體布線和詳細(xì)布線間的交互性，使用多種策略來優(yōu)化布線結(jié)果，得到更為準(zhǔn)確的布線資源估計(jì)，最終減少擁擠度，提高布通率．采用標(biāo)準(zhǔn)的測(cè)試?yán)蛹瘜?duì)所提出的方法進(jìn)行測(cè)試，以證明該算法的有效性．

1 布線模型

1．1 問題描述

布線過程是對(duì)每一條線網(wǎng)進(jìn)行布線區(qū)域的分配．總體布線為每條線網(wǎng)生成一個(gè)寬松的解，就是為每條線網(wǎng)分配一些區(qū)域，但是不決定實(shí)際走線位置［17］．詳細(xì)布線決定每個(gè)布線區(qū)域中實(shí)際走線位置，在總體布線分配的區(qū)域中完成布線．

總體布線問題定義為［18］:給定一個(gè)網(wǎng)表N={N1，N2，…，Nn}，和一個(gè)總體布線圖G=(V，E)，對(duì)?Ni∈N，1≤i≤n，找到一棵斯坦納樹Ti，使得

布線算法的目標(biāo)是在滿足各種約束條件下，為每個(gè)線網(wǎng)分配合適的通道．算法成功后生成的是連接各線網(wǎng)的子圖［19］．

輸入:1)電路的網(wǎng)表，包括每個(gè)線網(wǎng)的源點(diǎn)和漏點(diǎn);

2)每個(gè)器件模塊和它的引腳具體位置．

輸出:所有線網(wǎng)在版圖上的具體走線．

設(shè)計(jì)目標(biāo):

1)最小化總線長和最小化通孔數(shù)量;

2)提高布通率、縮短布線時(shí)間．

1．2 布線圖的數(shù)學(xué)模型

布線問題是典型的圖論問題．每個(gè)布線區(qū)域所能容下的最大線網(wǎng)數(shù)稱為布線容量［20］，布線容量和布線區(qū)域間的關(guān)系可以抽象為一張布線圖．

本文的布線模型是將整個(gè)布線版圖抽象為一個(gè)邏輯上的布線網(wǎng)格圖，整個(gè)布線區(qū)域被分為h行、w列，得到相應(yīng)的h×w個(gè)布線單元(GRC)，每個(gè)網(wǎng)格單元組成網(wǎng)格圖(grid graph)G，如圖1所示．

1)G中的結(jié)點(diǎn)集合為V，邊的集合為E;

2)每個(gè)結(jié)點(diǎn)?v∈V都對(duì)應(yīng)版圖中某個(gè)布線區(qū)域，各線網(wǎng)的引腳都映射到這些結(jié)點(diǎn)中;

3)相鄰單元對(duì)應(yīng)的結(jié)點(diǎn)用邊連接起來，每條邊e∈E都對(duì)應(yīng)相鄰布線區(qū)域間的通路，每條邊都有一個(gè)“布線容量”，用pv表示;每條邊的長度和容量都設(shè)成相等，網(wǎng)格的大小可以變化，但如果把網(wǎng)格設(shè)得太小會(huì)增大問題規(guī)模［21］;

4)每條邊e∈E上穿過的線網(wǎng)數(shù)量稱為已占用容量，用dv表示．

圖1 網(wǎng)格圖模型Fig．1 The grid graph model

1．3 相關(guān)布線模型

總體布線是采用預(yù)先設(shè)定的模型布線．線網(wǎng)的源點(diǎn)和漏點(diǎn)如果在同一直線上，就用線模型布線;如果失敗則改用U模型布線;如果源漏點(diǎn)不在同一直線上，則使用考慮擁擠度的L模型布線(圖2(a))和Z模型布線(圖2(b))．L模型布線僅搜索兩端網(wǎng)絡(luò)邊界框的邊，再根據(jù)這些邊的成本來選擇“上L型”或“下L型”，然后進(jìn)行布線．Z模型布線需要搜索兩端邊界框的周邊及內(nèi)部邊．

圖2 布線模型Fig．2 Routing models

2 算法設(shè)計(jì)

2．1 算法思想

多級(jí)布線算法采用考慮擁擠度的多級(jí)布線策略，對(duì)每一級(jí)里的局部線網(wǎng)交替進(jìn)行總體和詳細(xì)布線，增加總體布線和詳細(xì)布線間的交互性，并且在布線后對(duì)資源重新估算，可以得到精確的資源使用結(jié)果;同時(shí)引入了擁擠度代價(jià)函數(shù)，將每條備選路徑經(jīng)過的邊的布線容量、占用容量和擁擠度等指標(biāo)通過代價(jià)函數(shù)，作為選擇布線解的依據(jù)，選取擁擠度代價(jià)最小的路徑;最終減少擁擠度，縮短布線時(shí)間，提高布通率．

2．2 代價(jià)函數(shù)

在總體布線階段應(yīng)該考慮避免某些布線區(qū)域的過度擁塞，引入擁擠度cv:

由于是多級(jí)布線，每個(gè)布線小區(qū)域會(huì)有水平擁擠度和垂直擁擠度．在本文中，水平方向布線通道擁擠度即為水平擁擠度，垂直方向布線通道擁擠度為垂直擁擠度．pv，dv分別表示結(jié)點(diǎn)v的通道容量和已占用容量．總體布線代價(jià)函數(shù)為:

用考慮擁擠度cv的代價(jià)函數(shù)來指導(dǎo)L和Z模型布線，從可行的路徑(pv＞dv)中選一條代價(jià)最小的．而U模型布線，將只考慮線長．在最短線長的情況下考慮擁擠度影響，不增加線長，使接下來的詳細(xì)布線更容易．如果詳細(xì)布線成功，dv將被更新，若不成功，則把線網(wǎng)放在最后的重新布線階段處理．

2．3 算法描述

首先，把輸入的多端線網(wǎng)，采用最小生成樹法，分成兩端線網(wǎng)進(jìn)行布線．接著，根據(jù)線網(wǎng)數(shù)量的規(guī)模設(shè)定布線的級(jí)數(shù)，把布線區(qū)域分成等高寬的布線小區(qū)域并確定局部線網(wǎng)，每一級(jí)里局部線網(wǎng)間相互獨(dú)立地進(jìn)行總體布線和詳細(xì)布線．對(duì)線網(wǎng)采用通孔最小化點(diǎn)到路徑的李氏算法進(jìn)行詳細(xì)布線，先期得到布線結(jié)果，從而降低布線規(guī)模，并使用考慮擁擠度的多級(jí)布線策略和資源重新估算策略，提高布線資源估計(jì)的準(zhǔn)確性．

2．3．1 考慮擁擠度的多級(jí)布線策略

把布線區(qū)域分成等高寬的布線小區(qū)域(小方格，tile)，如圖3中的G0所示．在G0層小區(qū)域數(shù)量多，問題規(guī)模大，難以解決．為了縮小規(guī)模，按照“把Gi層4個(gè)組成田字形的小區(qū)域合并成Gi+1的一個(gè)新區(qū)域”的策略對(duì)小區(qū)域進(jìn)行合并，得到新的G1層;如果G1規(guī)模還太大，繼續(xù)合并，直到滿足要求的Gk層．對(duì)Gi(0≤n≤k)層中的所有局部線網(wǎng)(源點(diǎn)和漏點(diǎn)都在同一個(gè)小區(qū)域里)進(jìn)行總體布線和詳細(xì)布線，根據(jù)式(1)和式(2)用考慮擁擠度cv的代價(jià)函數(shù)來指導(dǎo)L模型布線(圖2(a))和Z模型布線(圖2(b))．接著在下一級(jí)里，找出那些因?yàn)楹喜⒍黾拥木植烤€網(wǎng)進(jìn)行布線．每一級(jí)布線針對(duì)新增局部線網(wǎng)，都進(jìn)行總體布線、詳細(xì)布線和下一級(jí)布線資源的估計(jì)，直到把整個(gè)芯片的布線區(qū)域合并成為一個(gè)布線區(qū)域，最后再把那些布線失敗的線網(wǎng)重新進(jìn)行全局迷宮布線．整個(gè)過程如圖3所示．

圖3 多級(jí)布線框架圖Fig．3 Multilevel routing framework

2．3．2 資源重新估算策略

多級(jí)布線在G0級(jí)時(shí)計(jì)算每個(gè)小區(qū)域的水平通道容量和垂直通道容量．由于已布線網(wǎng)、通孔和電路模塊會(huì)占用通道容量，用掃描線法測(cè)出已占用容量．接著在總體布線過程中，每完成一條兩端線網(wǎng)，就在選擇路徑上已占用容量加一．但總體布線不是線網(wǎng)的實(shí)際走線，并不能精確反映資源使用情況，因此在每級(jí)詳細(xì)布線結(jié)束后，需要重新估計(jì)資源，再次使用掃描線法重新測(cè)量已占用容量，那些在同一水平線或垂直線上的線網(wǎng)只會(huì)占用1個(gè)單位的通道容量．重新估計(jì)資源后，可以相應(yīng)更新線網(wǎng)的擁擠度．

2．3．3 多級(jí)布線算法的偽代碼

中南大學(xué)在2016級(jí)、2017級(jí)冶金、工管、能器、機(jī)械、臨床等非計(jì)算機(jī)專業(yè)約840名學(xué)生的“數(shù)據(jù)庫技術(shù)與應(yīng)用”課程進(jìn)行了連續(xù)兩年交叉融合的教學(xué)模式的實(shí)踐，課程共48課時(shí)，為期12周，獲得了比對(duì)效果較好的應(yīng)用數(shù)據(jù)。

多級(jí)布線算法(見表1)的偽代碼描述中的步驟5～12完成局部線網(wǎng)布線，步驟9采用擁擠度優(yōu)化的總體布線方法;步驟12是詳細(xì)布線，引入了通孔優(yōu)化策略;步驟13重新估計(jì)資源，用于提供步驟9中擁擠度更新所需的數(shù)據(jù);步驟14對(duì)布線仍然失敗的線網(wǎng)進(jìn)行重新布線．

表1 多級(jí)布線算法Tab．1 Multi－level routing algorithm

(續(xù)表1)

2．4 復(fù)雜度分析

總體布線中把G0級(jí)的小區(qū)域作為布線基本單元，而詳細(xì)布線的基本單元是由線寬、線間距和通孔間距等幾何設(shè)計(jì)約束計(jì)算得出［22］．本文的總體布線采用預(yù)先設(shè)定好的模型布線，包括:線模型布線、U模型布線、L模型布線和Z模型布線．如果以上方法都失敗就用求最短路徑的李氏算法布線．李氏算法會(huì)搜索很多路徑，而這些路徑很可能在最后的結(jié)果中不會(huì)被采用，模型布線只會(huì)考慮少數(shù)幾條路徑，時(shí)間復(fù)雜度會(huì)大大減小，比如L模型布線只會(huì)考慮兩條路徑．具體選哪條，會(huì)根據(jù)代價(jià)函數(shù)計(jì)算得出．

假設(shè):一個(gè)兩端線網(wǎng)n={(x1，y1)，(x2，y2)} ，網(wǎng)格圖G=(V，E);

U模型布線時(shí)間復(fù)雜度根據(jù)劃定的布線區(qū)域不同而不同．

3 實(shí)驗(yàn)結(jié)果

在主頻1．8 GHz，內(nèi)存2 G的Linux操作系統(tǒng)下用C++實(shí)現(xiàn)了該多級(jí)布線算法．用文獻(xiàn)［9］提供的11個(gè)標(biāo)準(zhǔn)電路和設(shè)計(jì)規(guī)則進(jìn)行測(cè)試，表2列出測(cè)試電路集的具體信息．對(duì)比算法選取經(jīng)典的MRS算法［9］(運(yùn)行環(huán)境與本文算法相同)，及其改進(jìn)算法［11］(在SUN Sparc Ultra－60工作站上用C++實(shí)現(xiàn))．

表2 測(cè)試電路集Tab．2 The benchmark circuit information

表3給出幾個(gè)布線算法的實(shí)驗(yàn)結(jié)果，可以看出，本文算法布線結(jié)果在布線時(shí)間、布通線網(wǎng)數(shù)、布通率等方面比MRS布線算法［9］有明顯提高．相較于文獻(xiàn)［11］的算法，本文算法具有更好的布通線網(wǎng)數(shù)和布通率，而在布線時(shí)間方面，由于運(yùn)行環(huán)境不同，不具有可比性．

表3 布線結(jié)果Tab．3 The routing result

1)在布線時(shí)間上，對(duì)于表1中的所有實(shí)例，本文算法都比MRS算法明顯縮短．11個(gè)電路布線時(shí)間平均縮短14．5%，有6個(gè)實(shí)例縮短的布線時(shí)間超過了10%，在Mcc2、Prim1和S1320711三個(gè)電路上的布線時(shí)間縮短超過了20%，其中S1320711布線時(shí)間縮短了31．7%．

2)在布通線網(wǎng)數(shù)上，本文算法在表中所有實(shí)例的布通線網(wǎng)數(shù)相對(duì)于MRS算法都有明顯增加，在S5378、S9234和S38417三個(gè)電路上布通線網(wǎng)數(shù)的增加超過了5%，其中電路S5378增加了5．4%;相較于文獻(xiàn)［11］的算法，本文在測(cè)試電路中也獲得了更好的結(jié)果，平均布通線網(wǎng)數(shù)更高，在Mcc1、Mcc2、Struct、Prim1、Prim2五個(gè)電路上完全布通，在S5378、S9234、S38417、S38584四個(gè)電路中都明顯增加，布通線網(wǎng)數(shù)平均增加了2．4%．

3)在布通率上，本文算法所有測(cè)試電路的平均布通率為98．9%，MRS算法的平均布通率為96．5%，文獻(xiàn)［11］算法的平均布通率為98．5%．本文算法有6個(gè)電路布通率達(dá)到了100%，MRS算法只有3個(gè)電路布通率達(dá)到100%，文獻(xiàn)［11］算法只有5個(gè)電路布通率達(dá)到100%，相對(duì)文獻(xiàn)［11］算法另外有4個(gè)電路布通率明顯提高;其中在電路S5378上，本文算法的布通率相對(duì)其他兩種算法分別提高了5．2%和1．5%．

4 結(jié)語

1)在分析傳統(tǒng)布線算法的基礎(chǔ)上，提出一種總體布線和詳細(xì)布線交替進(jìn)行的多級(jí)布線算法，在每一級(jí)布線中對(duì)局部線網(wǎng)進(jìn)行總體和詳細(xì)布線，增加總體布線和詳細(xì)布線間的交互性，利用代價(jià)函數(shù)，使用多種策略來優(yōu)化布線結(jié)果，得到更為準(zhǔn)確的布線資源估計(jì)，最終減少擁擠度，提高布通率．

2)采用標(biāo)準(zhǔn)的測(cè)試?yán)蛹瘜?duì)所提出的方法進(jìn)行測(cè)試，說明了該算法的有效性．但本文的多級(jí)算法尚未考慮關(guān)鍵路徑的時(shí)延約束等方面的優(yōu)化，將在以后工作中加以研究和改進(jìn)．