楊尚霖，謝龍韜

（石河子大學(xué) 機(jī)械電氣工程學(xué)院，新疆 石河子832000）

集成電路是利用半導(dǎo)體技術(shù)把電子元件集成在一起的具有特定功能的電路，在生活中的多個方面得到廣泛運(yùn)用。集成電路內(nèi)的電子元件隨著技術(shù)的高速發(fā)展，其內(nèi)的電子元件數(shù)目已高達(dá)十億級別，因此在制作集成電路時需要依靠專業(yè)的計算機(jī)軟件，該類軟件統(tǒng)稱為電子設(shè)計自動化（EDA）工具。制作分為多步驟完成，制作過程中的一大難點是“布線”問題，即在矩形網(wǎng)格中將器件擺放合適之后，利用金屬線將其相互連接，但引線之間不能相互交叉避免造成短路。本問題主要研究“布線”中的特例“通道布線”，它是指在一個橫向的布線區(qū)域，需要連接的方格分布在區(qū)域頂部和底部，再利用金屬線將其引腳連接起來。

集成電路的通道設(shè)計一直是個NP完全問題，由于它的算法時間復(fù)雜度高，過去學(xué)者對其求解進(jìn)行過許多研究。20世紀(jì)80年代以來，Nobuo Funabiki等[1]人提出了一種并行算法來解決二層通道布線的設(shè)計問題；Jens Lienig等[2]人在此基礎(chǔ)上，采用遺傳近似算法對通道布線問題進(jìn)行了求解，降低了尋找可行解的時間；隨著集成電路的發(fā)展，Chen Y K等[3]對二層通道布線方法進(jìn)行改進(jìn)，提出了適用于三層通道設(shè)計的布線方法；褚靜[4】、周曉娜[5]研究了圖論在通道布線中的運(yùn)用；K.Madhavi等[6]、黃訓(xùn)誠[7]、徐寧[8]研究了現(xiàn)代智能算法在通道布線求解問題中的運(yùn)用。學(xué)者們對集成電路通道布線設(shè)計求解算法進(jìn)行了充分的探討，而對于通道布線問題的數(shù)學(xué)機(jī)理模型的討論較少。在上述研究的基礎(chǔ)上，本文結(jié)合網(wǎng)絡(luò)流理論構(gòu)建了用于解決集成電路通道布線問題的單目標(biāo)優(yōu)化混合整數(shù)線性規(guī)劃模型。運(yùn)用LINGO求解器對于最為常見的二層通道布線設(shè)計問題進(jìn)行求解。最后結(jié)合實例說明了模型的可行性，如圖1所示。

1 問題分析

通道布線設(shè)計是將對應(yīng)的引腳用導(dǎo)線相連，在布線的途中不出現(xiàn)串線問題的同時，使布置的導(dǎo)線總電阻值最小為目的的優(yōu)化問題。對于不同規(guī)模的網(wǎng)格，其拓?fù)浣Y(jié)構(gòu)、引腳位置對求解結(jié)果有著十分關(guān)鍵的影響。本節(jié)針對網(wǎng)格的結(jié)構(gòu)和連線約束兩個方面進(jìn)行闡述。

1.1 網(wǎng)格結(jié)構(gòu)

（1）網(wǎng)格規(guī)模大小直接限制了導(dǎo)線走線，連線不能超出網(wǎng)格。

（2）相鄰網(wǎng)格和網(wǎng)格之間才能用導(dǎo)線連接。

1.2 連線約束

（1）對應(yīng)各個引腳必須用導(dǎo)線連接。

（2）一層通道內(nèi)，每個網(wǎng)格只能有一條導(dǎo)線經(jīng)過，否則存在串線問題。

（3）導(dǎo)線在穿過兩層通道之間時，需在中間安置通孔，通孔對電路電阻有影響。

2 數(shù)學(xué)模型建立

2.1 符號含義說明

集成電路通道布線設(shè)計是將對應(yīng)的引腳通過矩形網(wǎng)格用導(dǎo)線相連，尋找連線總電阻值最小的優(yōu)化問題。為了解決此問題，首先需對一些符號進(jìn)行定義說明，見表1所示。

表1

2.2 目標(biāo)函數(shù)與約束條件

上述模型中，目標(biāo)函數(shù)式表示的是布線總路徑電阻值最?。患s束條件反應(yīng)的是：（2）式要求每條導(dǎo)線的連接是連續(xù)的；（3）式表示的是每條線只能經(jīng)過一個網(wǎng)格一次；（4）（5）式表示的是第1、2層的每個網(wǎng)格最多只能由一條導(dǎo)線經(jīng)過；（6）式表示通孔的存在條件；（7）式表示每條線的對應(yīng)引腳起點和終點必須相連；（8）（9）式表示只能用導(dǎo)線連接相鄰的網(wǎng)格；（10）（11）式表示決策變量均為0-1變量。

3 結(jié)果分析

通過將不同規(guī)模大小、不同引腳個數(shù)的集成電路代入模型進(jìn)行布線設(shè)計，通過LINGO求解，分析模型結(jié)果的可行性，見表2、圖2所示。

圖2 通過LINGO求解得到的布線效果圖

表2 算例求解結(jié)果

4 結(jié)論

本文針對集成電路通道布線問題進(jìn)行研究，以布線電阻值為布線主要因素，考慮到布線長度以及通孔個數(shù)對于線路電阻值的影響，建立設(shè)計了一個以線路電阻值最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型，通過將模型代入LINGO求解得到的結(jié)果，可以大大降低布線電阻值，提高了布線電路的性能和可靠性。

本文未考慮線路彎曲對于線路電阻值的影響，線路電阻會由于線路的彎曲而變化，它對電路性能有著很大影響。