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

陳秀華

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

0 引言

在超大規模集成電路(very large scale integration，VLSI)設計中，布線是在規定的布線區域內實現電路內部各個模塊之間的物理連接，它是VLSI物理設計(physical design)中非常關鍵的步驟之一．當前，超大規模半導體芯片的主流制造技術已經向深亞微米(very－deep－submicron，VDSM)及納米推進，集成電路設計的集成度和復雜性越來越高，設計規則尺度縮小，使得集成電路中由器件占主導地位變為互連線占主導地位．如果在設計中不能充分考慮布線問題，設計性能就會出現嚴重偏差，從而反復迭代，使設計的周期變長．

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

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

本文提出增加總體布線和詳細布線間的交互性，使用多種策略來優化布線結果，得到更為準確的布線資源估計，最終減少擁擠度，提高布通率．采用標準的測試例子集對所提出的方法進行測試，以證明該算法的有效性．

1 布線模型

1．1 問題描述

布線過程是對每一條線網進行布線區域的分配．總體布線為每條線網生成一個寬松的解，就是為每條線網分配一些區域，但是不決定實際走線位置［17］．詳細布線決定每個布線區域中實際走線位置，在總體布線分配的區域中完成布線．

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

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

輸入:1)電路的網表，包括每個線網的源點和漏點;

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

輸出:所有線網在版圖上的具體走線．

設計目標:

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

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

1．2 布線圖的數學模型

布線問題是典型的圖論問題．每個布線區域所能容下的最大線網數稱為布線容量［20］，布線容量和布線區域間的關系可以抽象為一張布線圖．

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

1)G中的結點集合為V，邊的集合為E;

2)每個結點?v∈V都對應版圖中某個布線區域，各線網的引腳都映射到這些結點中;

3)相鄰單元對應的結點用邊連接起來，每條邊e∈E都對應相鄰布線區域間的通路，每條邊都有一個“布線容量”，用pv表示;每條邊的長度和容量都設成相等，網格的大小可以變化，但如果把網格設得太小會增大問題規模［21］;

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

圖1 網格圖模型Fig．1 The grid graph model

1．3 相關布線模型

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

圖2 布線模型Fig．2 Routing models

2 算法設計

2．1 算法思想

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

2．2 代價函數

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

由于是多級布線，每個布線小區域會有水平擁擠度和垂直擁擠度．在本文中，水平方向布線通道擁擠度即為水平擁擠度，垂直方向布線通道擁擠度為垂直擁擠度．pv，dv分別表示結點v的通道容量和已占用容量．總體布線代價函數為:

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

2．3 算法描述

首先，把輸入的多端線網，采用最小生成樹法，分成兩端線網進行布線．接著，根據線網數量的規模設定布線的級數，把布線區域分成等高寬的布線小區域并確定局部線網，每一級里局部線網間相互獨立地進行總體布線和詳細布線．對線網采用通孔最小化點到路徑的李氏算法進行詳細布線，先期得到布線結果，從而降低布線規模，并使用考慮擁擠度的多級布線策略和資源重新估算策略，提高布線資源估計的準確性．

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

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

圖3 多級布線框架圖Fig．3 Multilevel routing framework

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

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

2．3．3 多級布線算法的偽代碼

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

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

表1 多級布線算法Tab．1 Multi－level routing algorithm

(續表1)

2．4 復雜度分析

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

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

U模型布線時間復雜度根據劃定的布線區域不同而不同．

3 實驗結果

在主頻1．8 GHz，內存2 G的Linux操作系統下用C++實現了該多級布線算法．用文獻［9］提供的11個標準電路和設計規則進行測試，表2列出測試電路集的具體信息．對比算法選取經典的MRS算法［9］(運行環境與本文算法相同)，及其改進算法［11］(在SUN Sparc Ultra－60工作站上用C++實現)．

表2 測試電路集Tab．2 The benchmark circuit information

表3給出幾個布線算法的實驗結果，可以看出，本文算法布線結果在布線時間、布通線網數、布通率等方面比MRS布線算法［9］有明顯提高．相較于文獻［11］的算法，本文算法具有更好的布通線網數和布通率，而在布線時間方面，由于運行環境不同，不具有可比性．

表3 布線結果Tab．3 The routing result

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

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

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

4 結語

1)在分析傳統布線算法的基礎上，提出一種總體布線和詳細布線交替進行的多級布線算法，在每一級布線中對局部線網進行總體和詳細布線，增加總體布線和詳細布線間的交互性，利用代價函數，使用多種策略來優化布線結果，得到更為準確的布線資源估計，最終減少擁擠度，提高布通率．

2)采用標準的測試例子集對所提出的方法進行測試，說明了該算法的有效性．但本文的多級算法尚未考慮關鍵路徑的時延約束等方面的優化，將在以后工作中加以研究和改進．