黃昉菀, 陳志盛, 劉耿耿

(1. 福州大學(xué)至誠學(xué)院， 福建 福州 350002；(2. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州 350116)

針對VLSI布線的多層X結(jié)構(gòu)斯坦納最小樹構(gòu)建算法

黃昉菀1, 2, 陳志盛2, 劉耿耿2

(1. 福州大學(xué)至誠學(xué)院， 福建 福州 350002；(2. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州 350116)

考慮到粒子群優(yōu)化算法具有非常出色的全局優(yōu)化能力， 針對X結(jié)構(gòu)布線問題的復(fù)雜性提出了X結(jié)構(gòu)下的多層Steiner最小樹構(gòu)建算法. 實(shí)驗(yàn)結(jié)果表明， 該算法可以在合理的時(shí)間內(nèi)取得優(yōu)異的布線解.

X結(jié)構(gòu)； 多層布線； Steiner樹； 粒子群優(yōu)化

0 引言

Steiner最小樹在圖論領(lǐng)域中是最重要的數(shù)學(xué)模型之一， 已經(jīng)在許多研究領(lǐng)域中得到廣泛運(yùn)用， 并且作為X結(jié)構(gòu)下多層Steiner最小樹(multilayer X-architecture Steiner minimal tree， ML-XSMT)構(gòu)建問題的基本模型， 成為布線中多端線網(wǎng)的最佳連接模型[1-2]. 在超大規(guī)模集成電路設(shè)計(jì)中ML-XSMT問題考慮了X結(jié)構(gòu)和多層這2個(gè)條件.

此外， 近年來粒子群優(yōu)化算法成為智能計(jì)算領(lǐng)域一個(gè)非常熱門的群智能算法， 已被成功地應(yīng)用到了諸多優(yōu)化領(lǐng)域[3]. 在粒子群算法中， 每一個(gè)優(yōu)化問題的解看作是搜索空間中的一只鳥， 即“粒子”. 首先初始化種群， 在可行解的空間中隨機(jī)初始化一群粒子， 每個(gè)粒子都為優(yōu)化問題的一個(gè)可行解， 并用合適的目標(biāo)函數(shù)評價(jià)其適應(yīng)度值. 每個(gè)粒子都在解空間中運(yùn)動， 并由速度決定其飛行的方向和距離， 通常粒子追隨當(dāng)前的最佳粒子在解空間中進(jìn)行搜索. 通過每一代群體的位置更新產(chǎn)生新的群體. 這樣可以保證群體的優(yōu)良性， 并加快尋優(yōu)速度， 不斷地搜索全局最優(yōu)個(gè)體.

1 問題模型

1.1 X結(jié)構(gòu)下VLSI多層斯坦納最小樹構(gòu)建問題模型

ML-XSMT問題的數(shù)學(xué)模型可描述如下： 給定布線層的層數(shù)N和單個(gè)通孔的代價(jià)Cv， 設(shè)定P={P1,P2,P3,…,Pn}為多層布線網(wǎng)絡(luò)上需要連接的一組引腳， 其中每個(gè)引腳Pi對應(yīng)一個(gè)三維坐標(biāo)(xi,yi,zi)， 分別表示引腳的橫坐標(biāo)、 縱坐標(biāo)和層數(shù)， 如圖1所示. 本研究需要構(gòu)建一棵滿足以下條件的多層X結(jié)構(gòu)斯坦納最小樹來連接集合P中的所有引腳： 1)布線樹的每條邊需要符合X結(jié)構(gòu)的連接方式； 2)通道是用來連接兩個(gè)不同布線層的邊； 3)最終得到的布線總代價(jià)是最小的. 例如圖2所示是通孔數(shù)為2的ML-XSMT問題的一種有效連接方式.

1.2X結(jié)構(gòu)連接模型

在λ-幾何學(xué)中， 布線方向被定義為iπ/λ. 其中i是任意整數(shù)， 不同的正整數(shù)λ值表示不同的布線結(jié)構(gòu). 當(dāng)λ的值被設(shè)置為4時(shí)， 即布線方向?yàn)閕π/4， 它包括0°、 45°和90°、 135°走線方向， 被稱為八角(或X)布線結(jié)構(gòu).

圖3定義了多層芯片環(huán)境下4種不同的X結(jié)構(gòu)走線模型. 其中：P1，P2為線段的兩個(gè)端點(diǎn);S1為P1所在布線層的斯坦納點(diǎn);S2為P2所在布線層的斯坦納點(diǎn).S1和S2之間的虛線表示通孔連接， 如果P1和P2位于相同布線層， 則此時(shí)S1和S2是重合點(diǎn)， 無需用通孔連接.

2 算法實(shí)現(xiàn)

2.1 粒子編碼策略

由于要考慮X結(jié)構(gòu)和多層布線結(jié)構(gòu)這兩個(gè)條件， 因此采用邊點(diǎn)對編碼模式. 這個(gè)編碼策略可以滿足完整性和非冗余性原則[4]. 用一組生成樹的邊來表示一棵候選的Steiner樹， 生成樹的每條邊選擇一種走線方式來選取斯坦納點(diǎn)， 從而轉(zhuǎn)換成X結(jié)構(gòu)的布線邊. 走線方式spc表示邊的斯坦納點(diǎn)的選取方式， spc的值可取0， 1， 2， 3， 分別代表圖3所定義的四種走線選擇. 每條布線邊采用4位數(shù)字編碼來表示， 前三個(gè)數(shù)字(前兩位數(shù)字代表了布線邊兩個(gè)端點(diǎn)的引腳標(biāo)號， spc的第三位表示Steiner點(diǎn)的選取方式)可以表示一條布線邊， 最后一位走線狀態(tài)label表示布線邊產(chǎn)生的通孔數(shù)量， 還有一個(gè)額外的數(shù)值為粒子的適應(yīng)度值.

2.2 預(yù)處理策略

根據(jù)多層X結(jié)構(gòu)斯坦納最小樹的構(gòu)建過程， 首先構(gòu)建一棵三維的最小生成樹， 然后將這個(gè)基礎(chǔ)構(gòu)架轉(zhuǎn)換成多層X結(jié)構(gòu)斯坦納樹. 但是， 每條最小生成樹的邊有四種不同的X結(jié)構(gòu)布線走位. 因此， 需要評估哪種布線走位的選擇會使得該轉(zhuǎn)換后的邊的布線代價(jià)最小. 而且， 在算法每次的迭代過程中， 都要計(jì)算粒子的適應(yīng)度值， 這就需要重新判斷布線樹各邊的布線走位以及產(chǎn)生的通孔數(shù)量. 為此， 預(yù)先計(jì)算了三維最小生成樹的所有布線邊的X結(jié)構(gòu)走位方式的信息并存儲在數(shù)組當(dāng)中， 在算法迭代過程中直接查詢所需要的數(shù)據(jù)， 減少計(jì)算次數(shù)， 加快算法的速度.

2.3 適應(yīng)度函數(shù)的定義及計(jì)算

構(gòu)建X結(jié)構(gòu)下超大規(guī)模集成電路的多層Steiner樹的布線總代價(jià)不僅包括布線樹的總長， 還需要找到合適的位置來形成通孔并計(jì)算通孔的布線代價(jià). 本研究應(yīng)用了邊點(diǎn)對的編碼方式， 則引腳i和引腳j的距離計(jì)算如下：

(1)

(2)

在多層布線條件下， 一定會產(chǎn)生通孔的， 而通孔數(shù)量是超大規(guī)模集成電路中一項(xiàng)至關(guān)重要的優(yōu)化指標(biāo)， 但是可以采用合理而有效的策略在一定程度上減少通孔的數(shù)量. 因此， 通過運(yùn)用懲罰機(jī)制來懲罰通孔的產(chǎn)生. 懲罰函數(shù)為：

(3)

其中：P(X,Q)為懲罰函數(shù);Q×S(X)為懲罰項(xiàng);Q是懲罰因子且取值的極限為無窮大; 懲罰函數(shù)中的N(X)通常表示沒有考慮約束條件下得到的解的代價(jià);S(X)表示在約束條件下得到的解的代價(jià).N(X)和S(X)也可以表示其他的含義， 但是它們可能取值會相同.

2.4 粒子的更新公式

基本的粒子群優(yōu)化算法的粒子更新公式不再適用于解決本研究所提出的離散優(yōu)化問題. 因此本研究引入交叉和變異算子， 并結(jié)合并查集思想來構(gòu)建多層X結(jié)構(gòu)Steiner最小樹.

改進(jìn)后的粒子更新公式為：

(4)

上式中， 粒子的速度更新公式為：

(5)

其中: 慣性權(quán)重w表示粒子間變異操作的概率;r1是0至1內(nèi)的隨機(jī)數(shù);M表示變異操作.

變異操作是從生成樹中隨機(jī)選擇一條邊進(jìn)行變異， 然后再隨機(jī)生成一條能使該生成樹保持連接狀態(tài)且無環(huán)路的布線邊. 當(dāng)生成樹的一條邊被去掉時(shí)， 所有的引腳點(diǎn)也因此分到兩個(gè)集合內(nèi). 本研究應(yīng)用并查集來記錄所有點(diǎn)的情況， 然后從兩個(gè)集合內(nèi)分別隨機(jī)選擇一個(gè)點(diǎn)來相互連接從而構(gòu)建新的生成樹, 變異操作如圖4.M1是進(jìn)行刪除的邊，M2是新生成的邊.

粒子的自身經(jīng)驗(yàn)感知公式：

(6)

其中: 加速因子c1表示粒子和個(gè)體歷史最優(yōu)解進(jìn)行交叉操作的概率;r2是0至1的隨機(jī)數(shù);C表示交叉操作.

粒子的全局經(jīng)驗(yàn)感知公式：

(7)

其中: 加速因子c2表示粒子和全局最優(yōu)解進(jìn)行交叉操作的概率;r3是0至1的隨機(jī)數(shù);C表示交叉操作.

當(dāng)進(jìn)行交叉操作時(shí)， 首先運(yùn)用并查集劃分兩棵已從小到大排序好邊的生成樹, 并從中選擇相同的邊放到一個(gè)集合. 剩下的不同邊便放到另一集合內(nèi)， 第一個(gè)集合中的邊直接做為新生成樹的邊. 最后， 重復(fù)地從另一個(gè)集合內(nèi)隨機(jī)選擇一條邊來加入到新生成樹. 交叉操作如圖5所示.

2.5 精煉策略

對于Steiner樹一個(gè)度為d的結(jié)點(diǎn)P1(此處為2度頂點(diǎn))， 這d條X結(jié)構(gòu)布線路徑的組合便可以看做是結(jié)點(diǎn)P的連接結(jié)構(gòu). 每條路徑都有四種不同的X結(jié)構(gòu)走線方式， 所以對于點(diǎn)P1就存在16種不同的連接結(jié)構(gòu)， 詳見圖6. 顯而易見， 如果P1P3采用“0選擇”或者“3選擇”， 那樣就無法和邊P1P2的X結(jié)構(gòu)布線路徑共享任何的布線資源. 當(dāng)P1P3采用“1選擇”走線方式來連接時(shí)， 如果P2的橫坐標(biāo)在P1橫坐標(biāo)和S12橫坐標(biāo)之間， 則可見圖6(a)便是P1的最佳連接結(jié)構(gòu). 另外， 如圖6(b)所示， 當(dāng)P2的橫坐標(biāo)在S12橫坐標(biāo)和S22橫坐標(biāo)之間時(shí)， 點(diǎn)S22是邊P3P1為“2選擇”的X結(jié)構(gòu)連接方式時(shí)的Steiner點(diǎn). 在這種情況下，P1的最佳連接結(jié)構(gòu)取決于P2S1和P2S2+S2S12的值(這里的P2S1、P2S2和S2S12表示的是兩點(diǎn)間的距離)，S1是邊P2P1為“1選擇”的X結(jié)構(gòu)連接方式時(shí)的Steiner點(diǎn)，S2是邊P2P1為“2選擇”的X結(jié)構(gòu)連接方式時(shí)的Steiner點(diǎn). 例如， 如果P2S1

3 實(shí)驗(yàn)驗(yàn)證分析

表1給出了在算法中運(yùn)用精煉策略和未使用精煉策略在相同的運(yùn)行環(huán)境下， 通過18組不同的測試數(shù)據(jù)， 在線長優(yōu)化方面的實(shí)驗(yàn)對照情況.

表1 精煉策略的實(shí)驗(yàn)驗(yàn)證對比Tab.1 The experimental verification and comparison of refinement strategy

續(xù)表

數(shù)據(jù)(ind1～ind5)是來自于美國新思科技公司的工業(yè)測試數(shù)據(jù)， 數(shù)據(jù)(rt1～rt5)是來自于其他工業(yè)標(biāo)準(zhǔn)測試集數(shù)據(jù)， 數(shù)據(jù)(rd1～rd8)是基于二維標(biāo)準(zhǔn)測試集改進(jìn)隨機(jī)生成的. 表格的第二列為每組測試數(shù)據(jù)的引腳數(shù)和層數(shù)的設(shè)定值.

精煉策略對于本研究所提出的構(gòu)建算法的最終布線質(zhì)量具有重要作用， 通過對比在算法中運(yùn)用精煉策略前后的布線總代價(jià)， 從而可知精煉策略的高效性. 表1列舉了不同引腳數(shù)和布線層數(shù)在通孔代價(jià)都為3的條件下， 運(yùn)用和未運(yùn)用精煉策略情況下的不同的布線總代價(jià). 使用精煉策略來構(gòu)建X結(jié)構(gòu)多層Steiner最小樹能獲得1.19%～7.29%的線長優(yōu)化率. 由于精煉策略能充分利用未被使用的布線資源， 通過改變布線樹的連接結(jié)構(gòu)來極大地增加共享的布線長度， 所以能有效減少線長.

4 結(jié)論

本研究結(jié)合遺傳算法中的變異算子和交叉算子， 并基于離散粒子群優(yōu)化算法提出一個(gè)有效的算法來構(gòu)建多層X結(jié)構(gòu)Steiner最小樹. 粒子群優(yōu)化算法在算法的迭代過程生成的解能不斷自我提升并進(jìn)行信息的交互， 從而使得個(gè)體不斷向最優(yōu)解收斂并且具有較快的收斂速度. 此外， 本研究算法中引入打破傳統(tǒng)的非曼哈頓布線結(jié)構(gòu)[6]， 該結(jié)構(gòu)巧妙地通過45°和135°的走線方向極大縮短了布線長度. 實(shí)驗(yàn)結(jié)果表明, 本研究算法提出的精煉策略在原算法的基礎(chǔ)上對于布線總代價(jià)具有較好的優(yōu)化作用.

[1] 徐寧， 洪先龍.超大規(guī)模集成電路物理設(shè)計(jì)理論與算法[M]. 北京： 清華大學(xué)出版社， 2009.

[2] TEIG S.The X architecture： not your fathers diagonal wiring[C]//Proceedings of the 2002 International Workshop on System-level Interconnect Prediction. San Diego: IEEE, 2002: 33-37.

[3] EBERHART R, KENNEDY J. A new optimizer using particles warm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science. Los Alamitos: IEEE Computer Society Press, 1995: 39-43.

[4] GUO W Z, LIU G G, CHEN G L,etal. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning[J]. Front Comput Sci, 2014, 8(2): 203-216.

[5] LIN C W, HUANG S L, HSU K C,etal. Multilayer obstacle-avoiding rectilinear steiner tree construction based on spanning graphs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(4): 643-653.

[6] KOH C K, MADDEN P H. Manhattan or non-manhattan?: a study of alternative VLSI routing architectures[C]//Great Lakes Symposium on VLSI.[S.l.]: ACM, 2002: 47-52.

(責(zé)任編輯： 林曉)

Multi-layer X-architecture steiner tree construction algorithm for VLSI routing

HUANG Fangwan1, 2, CHEN Zhisheng2, LIU Genggeng2

(1. Zhicheng College， Fuzhou University， Fuzhou， Fujian 350002， China;(2. College of Mathematics and Computer Science， Fuzhou University， Fuzhou， Fujian 350116， China)

Because the complexity of X-architecture routing problem. Considering particle swarm optimization (PSO) algorithm has very excellent global optimization capability, this paper proposes a PSO based algorithm for multilayer X-architecture Steiner tree construction. Experimental results show that the proposed algorithm can achieve great results with reasonable runtime.

X-architecture； multilayer routing； Steiner tree； particle swarm optimization

10.7631/issn.1000-2243.2016.05.0639

1000-2243(2016)05-0639-05

2015-05-18

黃昉菀(1980-)， 講師， 主要從事智能信息技術(shù)研究，hfw@fzu.edu.cn

福建省教育廳科技資助項(xiàng)目(JA13356)； 國家自然科學(xué)基金資助項(xiàng)目(11501114)

TP39

A