基于分層布線算法集成電路通道布線最優策略

顧家暢 黃 鑫 鄧 譙

(湖南農業大學信息與智能科學技術學院,湖南 長沙410128)

1 概述

集成電路在生產生活的方方面面都有著十分重要的作用，隨著技術的發展，其內部的元器件數量已達到了十億級別，需借助電子設計自動化（EDA）工具才能完成電路的設計與實現。“物理設計”是其中一個重要階段，先將器件擺放在合適的位置，然后用金屬線連接器件實現連接關系，后者稱為“布線”，布線可用區域由nxm個方格組成，金屬線允許沿著直線或直角（方格）放置。由于金屬線引入的寄生電阻會影響電路性能，所以需要最小化布線長度。本文重點考慮“布線”問題中的一個特例：“通道布線”，“通道”是指一個橫向的布線區域，區域的頂部和底部分布著需要連接的方格，需用金屬線將相應的引腳連通起來。

2 問題分析

本文通過對一層通道布線圖的分析，可知依據原方格圖會存在求解復雜的缺點，因此將用無網格布線算法[2]對通道布線圖變線寬、變線距問題進行優化，以此提高了布線的速度，也得到較好的效果。基于附件測例數據及一層通道布線原則，將對各上、下引腳坐標進行分析，上引腳坐標、下引腳坐標中的i的變化將暴露其造成短路的問題，其中如果i>i+1則此測例無解。從而會得到一層金屬通道布線問題的答案，并且在以上分析的基礎上，盡力消除寄生電阻的影響保持電路性能較好的前提下，可利用曼哈頓公式求得引腳布線的曼哈頓距離最小，即為最小化布線長度。

在上述分析的基礎上可知：在何種情況下，一層金屬通道布線問題無解，此時將考慮多個金屬層情況，以3層金屬通道布線為例，在測例3數據的基礎上，根據上下引腳坐標中i的變化規律進行動態規劃，在上引腳坐標i依次遞增的前提下確保下引腳坐標i盡量遞增，再將上下引腳坐標i變化較大的進行層層篩選，通過計算機軟件的處理可得到分成3部分的引腳對數，此時可將數據最多的一部分作為基礎層，將依據i值變化的大小得到第二、三層的引腳對數。接下來,可以通過分層布線算法[3]，依據靠左或靠右原則連接每對引腳為其合理布線，在合法域內為必要的部分增加通孔連通，再利用曼哈頓公式求解模型，從而可得到測例三數據中符合要求的3層金屬通道布線的最小布線長度。

3 模型建立

根據無網格布線算法，對測例1數據進行了處理，得到的測例1無網格布線圖如下圖1所示。

圖1 測例1一層通道布線無網格布線圖

其中每個點代表每原方格的中心，相鄰兩點間的距離為單位1，由上圖可知測例1中每對引腳都可以成功布線，且不會短路。

同樣的方法，我們對測例2、3的數據進行一層通道布線圖擬合，如附錄圖所示，可發現這兩種情況均會出現同一個點有不同路線經過的情況，不滿足題目條件，也即該情況一層通道布線問題無解。

對于測例1數據有解情況，由平移定理可知：在每個引腳對的合法區域中，當行駛不重復方向時，最短路徑為合法區域的垂線邊界與水平線邊界，又因寬度相同，因此我們可利用曼哈頓距離公式進行最小化布線長度求解，假設在最新無網格布線圖中每個引腳對的上引腳坐標為（Ai，Aj），下引腳坐標為（Bi，Bj），則可用曼哈頓距離公式求得引腳布線長度為：

在此基礎上，問題一的最小布線長度為d1，設總的引腳數為K，k代表第k個引腳，則測例1的一層通道布線最短長度為：

在對測例數據的分析后，可得在何種情況下，一層金屬通道布線問題無解。同時將測例1的引腳坐標數據代入曼哈頓距離公式，通過計算我們可以求得，布線長度為16，即16個網格。

通過網格點化并建立直角坐標系得到上下引腳的坐標，從第一層開始，從左到右地將引腳進行連接，并保證連線盡可能地靠左連接，另一邊盡可能的靠右連接，得到兩條極端路徑，分別稱為這對引腳的左合法邊界和右合法邊界，兩條邊界共同圍成的閉合區域我們稱為合法域，具體如下圖2所示。當第n對引腳對的左合法邊界同時與第i對的右合法邊界和左合法邊界相交時，這時我們認為第n對和第i對引腳對不能在同一層完成金屬布線。兩個引腳對的合法域的相交區間，稱為共有域。同時在引腳對合法域內，每一條從上引腳全程向著下引腳走的任何一條通路都是該引腳對連接的最短路徑。對則需要在可用布線空間最下方留出α行空白網格。

圖2 合法區域概念圖

（6）第一層通道布線完成后，將前面數據篩選過后的其它層的引腳對路徑按照同樣的方式進行排列。

（7）在除去第一層單都其它層引腳對集合進行通道布線時，需要選擇通孔的位置，通孔的位置優先在每對引腳對的合法域內進行選擇，若無合適位置則優先考慮在距離合法域最近的無干擾布線區域進行選擇。

（8）通道布線長度的距離計算公式：

4 模型求解

本文采用多個金屬層來進行通道布線，我們以測例3的引腳數據為例來進行模型的建立與求解。通過計算機軟件將測例3的36對引腳分成三組，以上引腳次序依次遞增的前提下盡量保證下引腳坐標依次增大，再將不符規律的分為二、三組，且把上下引腳坐標跨度最大的作為第三組，分組后的數據如下：

第 一 組 （1,3），（2,4），（3,5），（5,6），（9,7），（10，9），（11,10），（12,14），（13,15），（14,16），（16,17），（20，18），（21,20），（22,21），（23,25），（24,26），（25,27），（27,28），（31,29），（32,31），（33,32），（34,36）,（35,37），（36,38），（38,39），（42,40），（43,42），（44,43）

第二組（6,8），（17,19），（28,30），（39,41）

第三組（4，11），（15,22）,（26,33），（37,44）

其中，第一層布線為實線，第二層為虛線，第三層為粗線，最上層點和最下層的點為上下引腳所在位置，黑色的點為布線空間

圖3 三層通道布線圖

（1）令初始的引腳對集合為：

依據Aki從大到小進行排列。

并將其它引腳對儲存到第一層引腳對集合中：

（3）重復上述數據篩選步驟，將D0篩選的數據剔出放入D1中，將D1的數據篩選后繼續提出放入新的引腳對集合中，直到所有集合中沒有無干擾布線。

基于該測例數據，按照上述的模型二，我們可以找到測例3的最優通道布線，并通過優化的曼哈頓距離計算公式可求得最小化布線長度為160。

5 后續研究

新通孔制造工藝要求任意兩個通孔的間距必須大于等于2個格點，通過對分層布線和合法區域的判斷，能夠找出通孔可選擇區域，在可選擇區域內增添通孔設置區域的條件為大于等于2個格點。因此，增加在合法區域內所有未占用點為圓心，以2為半徑畫圓，而在此圓外或邊界上的點，可以成為此引腳對可選擇設定通孔的位置，最后利用曼哈頓公式求解模型，將得到符合要求的最小布線長度。