基于分層布線算法集成電路通道布線最優(yōu)策略

顧家暢 黃 鑫 鄧 譙

(湖南農(nóng)業(yè)大學(xué)信息與智能科學(xué)技術(shù)學(xué)院,湖南 長沙410128)

1 概述

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

2 問題分析

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

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

3 模型建立

根據(jù)無網(wǎng)格布線算法，對測例1數(shù)據(jù)進(jìn)行了處理，得到的測例1無網(wǎng)格布線圖如下圖1所示。

圖1 測例1一層通道布線無網(wǎng)格布線圖

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

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

對于測例1數(shù)據(jù)有解情況，由平移定理可知：在每個引腳對的合法區(qū)域中，當(dāng)行駛不重復(fù)方向時，最短路徑為合法區(qū)域的垂線邊界與水平線邊界，又因?qū)挾认嗤?，因此我們可利用曼哈頓距離公式進(jìn)行最小化布線長度求解，假設(shè)在最新無網(wǎng)格布線圖中每個引腳對的上引腳坐標(biāo)為（Ai，Aj），下引腳坐標(biāo)為（Bi，Bj），則可用曼哈頓距離公式求得引腳布線長度為：

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

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

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

圖2 合法區(qū)域概念圖

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

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

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

4 模型求解

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

第 一 組 （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）

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

圖3 三層通道布線圖

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

依據(jù)Aki從大到小進(jìn)行排列。

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

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

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

5 后續(xù)研究

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