八角形斯坦納樹(shù)問(wèn)題的文化基因算法

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

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

0 引言

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

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

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

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

1 問(wèn)題模型

1.1 八角形斯坦納樹(shù)問(wèn)題描述

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

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

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

定義 2(VX模式)從源點(diǎn)沿垂直線向上至拐點(diǎn)，再?gòu)墓拯c(diǎn)沿45度方向至終點(diǎn)，則稱(chēng)為VX模式.

定義 3(XV模式)從源點(diǎn)沿45度方向至拐點(diǎn)，再?gòu)墓拯c(diǎn)沿垂直線向上至終點(diǎn)，則稱(chēng)為XV模式.

定義 4(VH模式)從源點(diǎn)沿垂直線向上至拐點(diǎn)，再?gòu)墓拯c(diǎn)沿水平線向右至終點(diǎn)，則稱(chēng)為VH模式.

定義 5(HV模式)從源點(diǎn)沿水平線向右至拐點(diǎn)，再?gòu)墓拯c(diǎn)沿垂直線向上至終點(diǎn)，則稱(chēng)為HV模式.

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

1.3 編碼方式

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

2 本研究算法

2.1 文化基因算法

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

2.2 本研究算法描述

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

(1)

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

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

2.2.1初始化種群

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

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

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

(2)

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

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

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

(3)

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

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

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

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

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

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

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

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

2.3 局部搜索

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

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

2.4 選擇種群

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

2.5 終止條件

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

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

3.1 實(shí)驗(yàn)基本設(shè)置

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

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

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

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

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

3.3 與其他算法的實(shí)驗(yàn)對(duì)比

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

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

4 結(jié)論

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