葉福玲,朱偉大,徐賽娟,劉耿耿

(1.福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350108；2.福州大學(xué)網(wǎng)絡(luò)信息安全與計算機(jī)技術(shù)國家級實驗教學(xué)示范中心,福建 福州 350108;3.福建商學(xué)院信息工程系,福建 福州 350012)

0 引言

隨著集成電路技術(shù)的迅猛發(fā)展與成熟，其設(shè)計尺寸進(jìn)入了超深亞納米時代，可以在一個芯片集成數(shù)億的晶體管甚至更多，使得芯片具有微型化、高性能、高集成等優(yōu)點(diǎn).同時，隨著集成電路的集成度和設(shè)計復(fù)雜性的提高,布線的難度也隨之提高[1-2].而總體布線是整個物理設(shè)計中極其重要的一個環(huán)節(jié)，總體布線的結(jié)果將決定后面詳細(xì)布線的質(zhì)量，從而影響到整個物理設(shè)計的結(jié)果[3].

一般的總體布線算法都是以直角結(jié)構(gòu)為模型基礎(chǔ)，其布線的方向只能是水平和垂直.在通常情況下，每一層只有一種布線方向，不同層之間通過通孔連接，這樣限制了研究人員優(yōu)化布線可能性.因此,為了改變傳統(tǒng)的直角布線結(jié)構(gòu)，有些研究人員開始嘗試以八角形結(jié)構(gòu)為基礎(chǔ)模型進(jìn)行布線[4-5]，并實現(xiàn)了一些資源的優(yōu)化，比如線長的縮短，通孔數(shù)的減少，提升了芯片整體性能.但是絕大數(shù)針對八角形布線結(jié)構(gòu)的研究基于貪心策略，易陷入局部極值，無法得到最優(yōu)解，所以并不能有效地發(fā)揮八角形結(jié)構(gòu)所帶來的優(yōu)勢.

斯坦納樹在圖論中是極其重要的數(shù)學(xué)模型之一，是八角形結(jié)構(gòu)下布線問題的基本模型[6]，也是超大規(guī)模集成電路物理設(shè)計的布線階段中多端線網(wǎng)的最佳連接模型，被證明是NP難問題.此外，作為一種比較優(yōu)秀的算法，文化基因算法[7]于1989年由Pablo Moscato首次提出，并逐漸引起各國研究人員的興趣和關(guān)注.文化基因算法的這種全局搜索和局部搜索的結(jié)合機(jī)制使其搜索效率在某些問題領(lǐng)域比傳統(tǒng)遺傳算法高效，并在NP難問題的求解中展現(xiàn)出良好的應(yīng)用前景.近年來文化基因算法已被成功地應(yīng)用到了諸多自動化控制、工程優(yōu)化、機(jī)器學(xué)習(xí)等領(lǐng)域并取得令人滿意的結(jié)果[8-12].

本研究主要分析基于文化基因算法的八角形斯坦納樹構(gòu)建問題，首先，使用Prim算法預(yù)處理種群，產(chǎn)生初始種群，避免了因引腳數(shù)過多而無法收斂的情況.然后，通過修改文化基因的編碼形式和相應(yīng)操作，使其能應(yīng)用于八角形斯坦納樹這一離散問題，解決超大規(guī)模集成電路中布線問題.最后，調(diào)整權(quán)重因子，使其能在一定迭代次數(shù)下，快速得到一個最優(yōu)或者較優(yōu)的拓?fù)浣Y(jié)果.

1 問題模型

1.1 八角形斯坦納樹問題描述

給定一組未布線的線網(wǎng)N={N1，N2，…，Nm},對于每個線網(wǎng)Ni,都有n個需要完全連接的引腳，即Ni={P1，P2，…,Pn}，而對于每一個引腳Pi在二維圖中都對應(yīng)一個坐標(biāo)(xi,yi).八角形斯坦納樹問題是以最小的線長代價，將每個線網(wǎng)Ni對應(yīng)的所有引腳都連接起來，形成一棵斯坦納樹[13].

1.2 拐點(diǎn)與走線模式定義

定義 1(拐點(diǎn))假設(shè)源點(diǎn)和終點(diǎn)之間連接過程方向發(fā)生了改變，出現(xiàn)了額外的點(diǎn)，則稱這個點(diǎn)為拐點(diǎn).如圖1所示.

定義 2(VX模式)從源點(diǎn)沿垂直線向上至拐點(diǎn)，再從拐點(diǎn)沿45度方向至終點(diǎn)，則稱為VX模式.

定義 3(XV模式)從源點(diǎn)沿45度方向至拐點(diǎn)，再從拐點(diǎn)沿垂直線向上至終點(diǎn)，則稱為XV模式.

定義 4(VH模式)從源點(diǎn)沿垂直線向上至拐點(diǎn)，再從拐點(diǎn)沿水平線向右至終點(diǎn)，則稱為VH模式.

定義 5(HV模式)從源點(diǎn)沿水平線向右至拐點(diǎn)，再從拐點(diǎn)沿垂直線向上至終點(diǎn)，則稱為HV模式.

圖1 走線模式圖Fig.1 Routing pattern

1.3 編碼方式

編碼是算法和模型之間的映射關(guān)系.在斯坦納樹的構(gòu)建過程中，連接方式以走線模式的編碼方式來決定.對于一個線網(wǎng)，需要連接n個引腳，則需要生成n-1條邊，每條邊有4種走線模式，因此需要用一個四元組來確定一條邊，則一個個體的編碼長度為4(n-1)+1.例如對一個有3個引腳的線網(wǎng)來說，需要生成兩條邊.因此，其個體的編碼可能為[1,1,2,VX,1,2,3,HV,8.5].其中，前4位代表第一個四元組，5到8位代表第二個四元組.四元組第一位代表的是個體所屬的線網(wǎng)，第二位和第三位是當(dāng)前選中的引腳，引腳以第四位的走線模式相連，所以，第一個四元組[1,1,2,VX]表達(dá)的意思就是線網(wǎng)1的引腳1和引腳2以VX模式相連.編碼的最后一位代表的是這個個體的適應(yīng)度函數(shù)值.

2 本研究算法

2.1 文化基因算法

文化基因算法是一種基于種群的全局搜索和基于個體局部啟發(fā)式搜索的結(jié)合體[7].與一般遺傳算法不同的是在遺傳操作中的對象是通過局部區(qū)域搜索出來的優(yōu)秀種群，而不是一般種群.這樣避免了一些迂回的無用搜索，使其能避免陷入局部極值，得到全局最優(yōu).文化基因算法的這種全局搜索和局部搜索的結(jié)合機(jī)制使其搜索效率在某些問題領(lǐng)域比傳統(tǒng)遺傳算法高效.

2.2 本研究算法描述

本算法是基于文化基因算法，通過使用Prim算法進(jìn)行預(yù)處理，產(chǎn)生初始個體，并修改文化基因算法中的個體編碼方式，同時修改相關(guān)操作來實現(xiàn)八角形斯坦納樹問題的解決.個體的更新如下式所示.

(1)

以下為基于文化基因的八角形斯坦納樹算法框架描述:

算法1 基于文化基因的八角形斯坦納樹算法: 遍歷所有的線網(wǎng)NStep1 用Prim算法產(chǎn)生初始種群Step2 遍歷種群中每個個體并計算其適應(yīng)度函數(shù)值 Step3 算法終止條件內(nèi) 1) 基于最大并集的交叉操作 2) 雙重變異操作 3) 局部搜索 4) 計算適應(yīng)度函數(shù)值 5) 選擇下一次迭代的個體遍歷結(jié)束

2.2.1初始化種群

初始的種群一般是隨機(jī)產(chǎn)生的，也可以利用已知問題所含的信息，人為選取一些比較優(yōu)質(zhì)的種群個體加入.在基于文化基因的八角形斯坦納樹算法中，使用Prim算法初始化種群.這種預(yù)處理策略，能加速算法的收斂，并能在一定程度上輔助算法優(yōu)化拓?fù)浣Y(jié)構(gòu).

2.2.2適應(yīng)度函數(shù)

在八角形斯坦納樹問題中，優(yōu)化斯坦納樹的拓?fù)浣Y(jié)構(gòu)，使其線長最短是首要目標(biāo).在一個線網(wǎng)中，有n個需要連接的引腳，需要n-1條邊和n-1個拐點(diǎn).則對一個種群而言，其目標(biāo)函數(shù)值應(yīng)該是2n-2條邊的長度之和，計算公式如下式所示：

(2)

其中：Ni代表第i個線網(wǎng)，ej屬于八角形斯坦納樹的一條邊.

適應(yīng)度函數(shù)值的大小往往代表著個體的優(yōu)劣，目標(biāo)函數(shù)值越小，表示該個體越優(yōu)秀.因此，在八角形斯坦納樹算法中，個體的適應(yīng)度函數(shù)是一個非零常數(shù)和目標(biāo)函數(shù)值之和的倒數(shù)，其計算公式如下：

F(Ni)=[C+L(Ni)]-1

(3)

其中，C是一個非零常數(shù)，代表的是線網(wǎng)中的單位長度.這樣做的目的是為了防止出現(xiàn)目標(biāo)函數(shù)值為0的情況，即引腳重合 .

2.2.3混合優(yōu)化的遺傳算子

遺傳操作的結(jié)果是選出那些適應(yīng)性強(qiáng)的優(yōu)秀代表,同時也產(chǎn)生一些交叉作用后新的個體,這些新個體可能屬于一些新的區(qū)域,在下一代的局部搜索中會被優(yōu)秀個體取代,然后再進(jìn)行進(jìn)一步的全局進(jìn)化.這種局部的啟發(fā)式搜索與全局尋優(yōu)搜索的混合搜索機(jī)制在進(jìn)化效率上顯然要比單純在普通個體間搜索高得多.本研究使用混合優(yōu)化遺傳算子，分別是基于最大并集的交叉操作和雙重變異操作.

1)基于最大并集的交叉操作.為了加快算法的收斂速度，基于文化基因的八角形斯坦納樹算法采用最大并集的策略來實現(xiàn)交叉操作，選擇當(dāng)前最優(yōu)的個體和迭代過程中最優(yōu)的個體進(jìn)行交叉.初始階段是得到兩個個體的交集，第二個階段是將剩下未連接到斯坦納樹上的引腳，隨機(jī)選擇前兩者中的一種連接方式連接起來，最終得到交叉操作的結(jié)果,詳見圖2所示.

2)雙重變異操作.為了降低造成局部收斂的可能性，避免種群選擇的局限性.本算法采用雙重變異操作，即兩種變異方式來拓展文化基因算法的搜索.第一種是拐點(diǎn)的變異,第二種是引腳選取方式的變異.

拐點(diǎn)的變異是改變四元組的最后一位的走線模式，從四個走線模式中隨機(jī)選擇一種走線模式.例如，線網(wǎng)1的個體[1,2,1,HV]變異成為[1,2,1,HX]，從而得到了更優(yōu)的個體.如圖3所示.

圖3 雙重變異操作Fig.3 Double mutation operation

引腳的變異是多點(diǎn)變異，改變了八角形斯坦納樹的拓?fù)浣Y(jié)構(gòu).通過不同的拓?fù)浣Y(jié)構(gòu)來尋優(yōu)，讓基于文化基因的八角形斯坦納樹算法有較強(qiáng)的搜索能力，使其得到更好的結(jié)果.

2.3 局部搜索

局部搜索的目的是得到局部區(qū)域內(nèi)最優(yōu)秀的個體[8].若不采用局部搜索算法，可能會導(dǎo)致算法的局部搜索能力變差，無法得到最優(yōu)或者較優(yōu)的結(jié)果.在八角形斯坦納樹算法中，局部搜索的領(lǐng)域是個體所有邊的所有走線模式，從VX模式到HV模式.最終得到局部搜索領(lǐng)域中最優(yōu)的個體，更新種群.局部搜索算法流程描述如下：

算法2 局部搜索算法: for 遍歷所有的邊f(xié)or 遍歷四種走線模式 計算當(dāng)前走線模式的適應(yīng)度值 if 當(dāng)前走線模式的適應(yīng)度值大于最大的適應(yīng)度值 更新當(dāng)前的最大適應(yīng)度值

2.4 選擇種群

合并父代和子代個體，計算所有個體的適應(yīng)度值，按照適應(yīng)值大小排序，選擇與種群規(guī)模大小相同的優(yōu)秀個體組成新種群.

2.5 終止條件

同其他優(yōu)化算法一樣，為了避免陷入極端，基于文化基因的八角形斯坦納樹算法也設(shè)置了一個迭代閾值和迭代結(jié)果要求精度鄰域，當(dāng)滿足兩者之一時，算法會終止.

3 實驗驗證

3.1 實驗基本設(shè)置

為了驗證基于文化基因的八角形斯坦納樹算法的有效性和優(yōu)越性，本研究開展了一系列實驗對比.實驗環(huán)境：window 10 操作系統(tǒng)、i5-6500處理器、3.20 GHz主頻、8.00 GB內(nèi)存.算法采用C++實現(xiàn)，用Visual Studio 2015編寫與運(yùn)行，分別對單個線網(wǎng)和多個線網(wǎng)兩種測試用例進(jìn)行實驗.

3.2 預(yù)處理策略的有效性證明

表1 驗證預(yù)處理策略的有效性Tab.1 Verify the effectiveness of the preprocessing strategy

為了驗證算法所使用的預(yù)處理策略的有效性，設(shè)置種群規(guī)模為50，最大的迭代次數(shù)為200，驗證預(yù)處理有效性的10組測試用例是單個線網(wǎng)數(shù)據(jù)集，其引腳數(shù)最少的為8，最多的是1 000，每個測試用例均運(yùn)行10次并取線長的平均值.

在相同的運(yùn)行環(huán)境下使用Prim算法和未使用Prim算法預(yù)處理種群，通過10組測試用例，對比線長方面的優(yōu)化效果(見表1).使用Prim算法預(yù)處理種群生成一個最小生成樹，避免了因為引腳數(shù)過多造成的解空間過大而不能得到一個收斂結(jié)果的情況.正如表1的實驗結(jié)果所示，第三列是未使用預(yù)處理策略得到的線網(wǎng)線長，第四列是使用預(yù)處理策略得到的線網(wǎng)線長，對于任何一個測試用例，預(yù)處理策略都發(fā)揮了優(yōu)化的效果，并且隨著引腳數(shù)量的增加，使用Prim算法預(yù)處理得到的結(jié)果優(yōu)化率顯著提高.對于這10組數(shù)據(jù)，使用了預(yù)處理方案的結(jié)果比未使用預(yù)處理的結(jié)果平均優(yōu)化了50.74%的布線線長.

3.3 與其他算法的實驗對比

驗證算法優(yōu)越性的測試用例是ISPD98的9組多線網(wǎng)數(shù)據(jù)集,其中線網(wǎng)數(shù)目從11 507個增長到64 227個，引腳總數(shù)從44 266個增長到269 000個.本研究中每個測試用例均運(yùn)行10次該算法并取線長的平均值，最后與K近鄰算法(K-nearest neighbour,KNN)[14]和偽布爾SAT的算法(A pseudo boolean SAT,SAT)[15]進(jìn)行比較.本研究算法對于每個測試用例在線長方面都有較大的優(yōu)化，幾乎每個測試用例都優(yōu)化了10%以上.最終，本算法分別比SAT和KNN平均減少了11.52%和10.24%的布線線長，充分說明基于文化基因的八角形斯坦納樹算法在處理現(xiàn)實布線中能有較大的優(yōu)越性詳，見表2所示.

表2 與SAT和KNN算法的對比Tab.2 Comparison with SAT and KNN algorithms

4 結(jié)論

本研究提出了基于文化基因的八角形斯坦納樹算法，并成功應(yīng)用于超大規(guī)模集成電路物理設(shè)計中布線問題.首先，在預(yù)處理階段使用Prim算法處理種群，克服了因為引腳數(shù)量過多造成的無法收斂的情況.其次，根據(jù)八角形斯坦納樹結(jié)構(gòu)的特點(diǎn)，結(jié)合文化基因算法，定義了四種走線模式，設(shè)計了新的編碼方式并修改了相應(yīng)的操作，使其能在全局范圍內(nèi)，快速收斂并全局尋優(yōu).最后，通過實驗證明基于文化基因的八角形斯坦納樹算法的有效性和優(yōu)越性，再與最近幾年提出解決布線問題的SAT和KNN算法相比，分別取得了11.52%和10.24%的優(yōu)化率.