求解VLSI不可二劃分布圖規劃問題的混合遺傳算法

陳建利，朱文興

(福州大學離散數學與理論計算機研究中心，福建福州 350116)

0 引言

超大規模集成電路(VLSI)布圖規劃是VLSI物理設計的早期階段，對集成電路的芯片面積、線長等性能指標有重大影響，是VLSI物理設計的關鍵環節之一［1］.VLSI布圖規劃問題是根據給出的矩形模塊、模塊之間相互聯結的信息(網表)，把所有模塊合法地放置在芯片中適當的位置上，并使其滿足一定的要求.布圖結果的好壞直接影響整個芯片的性能.

在VLSI布圖規劃中，有可二劃分(slicing)和不可二劃分(non-slicing)兩種類型的芯片版圖結構［1］.可二劃分結構通過遞歸法以垂直和水平劃分線把一個個矩形模塊劃分成二部分.其結構比較簡單，但只涵蓋了部分布圖問題.相對而言，不可二劃分結構更具有一般性、靈活性，且具有更高的面積利用率等優點.但不可二劃分版圖結構更加復雜，實現也更為困難.

為表示不可二劃分的布圖結構，大量的結構表示方法被提出.不同的表示法有不同的解空間和不同的冗余度，它們的解碼操作和擾動操作的效率也不盡相同.現有的用來解決VLSI布圖規劃的主要表示結構有:O-tree［2］、B*-tree［3］、序列對(sequence pair)［4］、角模塊序列(corner block list)［5］、TCG(transitive closure graph)［6］、TCG-S［7］、SKB-tree［8］等. 與其它結構表示相比，B*-tree 具有解空間小、操作簡單、能夠處理不同類型模塊等優點，且由一棵B*-tree可以得到唯一的一個與之相對應的布圖.對有預先放置模塊和布圖區域有約束的布圖問題，B*-tree也可以容易地進行處理.因此，本研究采用B*-tree表示結構.

布圖規劃已被證明是NP困難問題［1］，因此不能在線性時間內得到它的最優解.研究者提出了各種啟發式算法來解決布圖規劃問題，主要有模擬退火算法［9-10］、粒子群算法［11-12］、遺傳算法［13-16］等.在基于遺傳算法的布圖規劃方法中，文獻［14-16］所提出的算法只能解決可二劃分布圖規劃問題.基于O-tree的結構表示，文［13］提出一種基于遺傳算法的Memetic算法用來解決不可二劃分的布圖規劃問題.但由于O-tree與布圖非一一對應關系，此編碼方案在搜索時難于從布圖結果中獲得有效的拓撲信息，因此該算法效率不高.

本研究提出一種用以解決不可二劃分VLSI布圖規劃的混合遺傳算法.基于B*-tree的結構表示，在全局搜索時，該算法采用交叉運算和變異運算使有效的拓撲信息得到保留;在局部搜索中，通過不斷地交換B*-tree的結點，得到一個局部最優解.在MCNC［3］標準測試例子集測試的實驗結果表明，該混合遺傳算法是有效的.

1 相關描述

1.1 布圖規劃問題

把VLSI布圖規劃問題加以抽象化，可描述為:給定n個矩形模塊R1，R2，R3，…，Rn(Ri的長為li，寬為wi，1≤i≤n)和這n個模塊之間相互聯結的信息(網表)及一個足夠大的布圖矩形框.VLSI布圖規劃的目標就是在滿足任意兩個矩形模塊不互相重疊且所有模塊的兩邊分別與布圖邊框兩邊平行的條件下，確定每個模塊在布圖矩形框內的具體位置，使得目標函數值最小.在本研究中，與文獻［9-12］一樣，目標函數為:

在一個滿足布圖要求的布圖F中，Area(F)表示包含所有模塊的最小矩形框的面積;Wirelength(F)表示采用半周長線長［10］計算的總線長;Area*，Wirelength*表示當前最優的面積及線長;w是權重因子，w∈［0，1］.

1.2 B*－tree

B*-tree［3］是一棵有序的二叉樹，它的根結點對應著左下角的矩形模塊.類似于深度優先搜索，一棵B*-tree T可以通過如下重復過程進行構造:從根結點出發，先構造T的左子樹，接著構造T的右子樹.用Bi表示與模塊bi相鄰且位于模塊bi右側的所有模塊的集合.bi的左子對應Bi中沒有訪問過的最下方的模塊，bi的右子對應于bi上方且水平方向坐標與bi相同.并且如果bi左側有模塊時，還要求bi右子的豎直方向坐標小于與bi相鄰的左側模塊的上邊界坐標.圖1［3］給出了一個可容許的布圖及其相對應的B*-tree.

圖1 一個可容許的布圖及其對應的B*-tree表示Fig.1 Illustration of an admissible floorplan and its corresponding B*-tree representation

對于一個容許布圖，可以構造出唯一的B*-tree［3］.相反地，由一棵B*-tree可以得到唯一的一個容許布圖.一個布圖是容許的當且僅當所有的模塊無重疊且不能向左或向下移動.對于給定的滿足所有模塊不互相重疊的布圖，可以通過向左向下的緊置移動，得到它的容許布圖及與之相對應的B*-tree.可容許布圖是滿足布圖規劃要求的布圖.

2 混合遺傳算法

在混合遺傳算法中，遺傳算子的作用與一般的遺傳算法不同.在一般的遺傳算法中，只通過交叉運算和變異運算來進行搜索.在混合遺傳算法中，交叉運算和變異運算只在全局搜索中被運用.具體的混合遺傳算法的描述如下.

2.1 適應度函數與初始種群

在混合遺傳算法中，總群中的每個個體為采用B*-tree表示的容許布圖.在超大規模集成電路布圖規劃中，需要優化的目標是最小化cost(F).因此，每個個體的適應度定義如下:

其中:F是一個容許布圖.在混合遺傳算法中，初始種群是采用隨機方法產生的若干棵B*-tree.

2.2 遺傳算子

1)交叉運算:給定二個父代，混合遺傳算法的交叉運算是將兩個父代個體的部分結構加以替換重組而生成新個體的操作.通過這樣的操作，可以使得一些好的拓撲結構信息得到保留.

圖2 交叉運算中的兩個父代Fig.2 Two parents in crossover operator

為了從父代P1，P2得到一個新的個體C1，交叉運算選擇P1的左子樹，通過復制，將左子樹的信息傳遞給C1.接著，將P2中的信息復制到C1的右子樹，并刪除右子樹上與左子樹重復的結點.通過以上的操作，使得P1，P2中好的信息得到了傳遞.圖2給出了用于交叉運算的兩個父代P1和P2.圖3給出了通過交叉運算后得到的子代C1.

2)變異運算:在混合遺傳算法中，通過二種變異運算來擴大搜索范圍.對于一個給定的容許布圖所對應的B*-tree，第一種變異運算是通過交換它的左子樹與右子樹，產生一個新個體;另一種變異操作是交換任意具有相同樹高的結點的左子與右子，產生一個新個體.圖4給出了這兩種變異運算的思想.

在變異操作中，所產生的新個體可能不是一個容許布圖.因此，需要通過向左向下緊置移動使產生的布圖變成一個容許布圖.通過以上這兩種變異運算，混合遺傳算法可以擴大搜索范圍.

圖3 父代P1和P2通過交叉運算后產生的子代C1Fig.3 The child C1 created from parents P1 and P2 by the crossover operator

圖4 變異運算方式1和變異運算方式2Fig.4 Mutation operator 1 and mutation operator 2

2.3 局部搜索算法

在混合遺傳算法中，基于B*-tree交換結點的操作，給出一種確定性的局部搜索算法.在這個局部搜索中，通過搜索每個B*-tree結點的可能位置，得到它的局部最優值.在搜索每個結點的可能位置中，先刪除該結點，再將這個結點添加到這些可能的位置中，并計算目標函數值，最后將該結點插入到可使目標函數值最小的位置上，產生一個新解.局部搜索算法的思想如下:

步驟1:對于B*-tree T中的每個結點ni.

①刪除ni;

②將ni添加到T中的可能位置，并分別計算出目標函數值，將ni插入到最小目標函數值時所對應的位置;

步驟2:輸出T.

在③中，通過旋轉90°，矩形模塊的長寬發生對換.因此，會產生不一樣的容許布圖，得到的目標函數值也不一樣.

2.4 混合遺傳算法描述

混合遺傳算法先產生初始種群，接著在允許時間內，進行逐代演化.在每一代中，混合遺傳算法先選擇父代，然后以一定的概率對父代進行交叉運算得到新子代，接著采用局部搜索算法對這個子代進行改進;接著又以一定的概率對這個改進后的子代進行變異運算，對變異運算后產生的新個體又進行局部搜索.混合遺傳算法的框架描述如下:

1)t:=0;

2)產生初始種群P(t);

3)計算P(t)中所有個體的函數值，并找出函數值最好的個體best;

4)在允許的時間之內，

①t:=t+1;

于是，我們都沉默了。原來看似幸福，并不一定是真的幸福。我們都只是仰望著別人的幸福，拿自己的不開心的一面在跟別人比較。沒錢時以為有錢才是幸福的，有了錢以為有權才是幸福的，錢和權都有了還終日抱怨活得不自在。田間勞作的羨慕車間工作的，車間工作的羨慕坐享空調辦公室的，坐辦公室的羨慕終日天南海北飛來飛去的。也不知這樣羨慕來羨慕去，到底誰活得更好些？不想著別人也有不如你的地方，也許還在羨慕你的。

②對于P(t)中的每個個體i:

令個體i為第一個父代P1，采用賭輪準則［10］選擇第2個父代P2;

{以一定的概率對這兩個個體進行交叉運算，得到新個體C1;

采用局部搜索算法對C1進行優化;

如果C1適應度大于父代個體P1的適應度則替換之，否則保留父代個體P1;

如果cost(C1)小于best，那么best=cost(C1);

}

{以一定的概率對C1進行變異運算，得到新個體F;采用局部搜索算法對個體F進行優化;如果個體F適應度大于父代個體P1的適應度則替換之，否則保留父代個體P1;

如果cost(F)小于best，那么best=cost(F);

}

5)輸出best.

3 實驗結果分析

本研究采用MCNC［3］的標準測試例子集對所提出的混合遺傳算法進行測試及分析.表1是MCNC測試例子集中各個例子的模塊數、線網數、引腳數和總面積的說明.

為測試所提出的混合遺傳算法的有效性，混合遺傳算法與一般的遺傳算法、基于遺傳算法的Memetic算法［13］進行比較.其中一般的遺傳算法和混合遺傳算法采用C++進行編寫，實驗環境為主頻2.0 GHz，內存為2 G的Intel CoreDuo CPU E7500;Memetic算法的實驗結果直接引用文［13］，其實驗環境為主頻2.0 GHz，內存為512 MB的Pentium IV CPU.一般的遺傳算法只進行交叉運算和變異運算，相關的參數設置如下:種群的規模設置為20，交叉運算的概率為0.95，變異運算的概率為0.05;在混合遺傳算法中，種群的規模設置為20，交叉運算和變異運算的概率都設置為0.5.為了便于公平比較，一般遺傳算法和混合遺傳算法每次運行的時間都設置為40 s，并運行30次，把最好的結果和平均結果記錄下來.在文［13］中，Memetic算法也運行30次，每次運行的時間為1 800 s.大部分的VLSI布圖規劃方法都只比較最小化面積時的實驗結果，即目標函數cost(F)中權重w取為1.因此，在第一個實驗中，首先考慮只優化面積時的情況.實驗結果如表2所示.

表1 MCNC測試例子Tab.1 Characteristics of the MCNC benchmarks

從表2可以看出，相比于一般的遺傳算法，混合遺傳算法不論是最優解或平均解的質量都比一般的遺傳算法好，證明了該混合遺傳算法是有效的;相比于Memetic算法，混合遺傳算法在平均解的質量上比Memetic好，但在ami49這個例子的最優解上，混合遺傳算法比Memetic算法差一點.必須指出的是Memetic每次運行的時候為1 800 s.

表2 不同算法在MCNC測試例子的實驗結果對比(w=1)Tab.2 Comparison of results on MCNC benchmarks by the three algorithms(w=1)

為進一步學習所提出的混合遺傳算法在不同面積、線長權重下的表現，令w=0.5，也就是面積、線長處于同樣重要的地位的布圖規劃問題.因Memetic算法只列出了w=1的情況，因此，在這個實驗中，沒有和Memetic算法進行比較.同樣的運行環境和時間(運行30次，每次40 s)，w=0.5時的實驗結果如表3所示.在表3中，線長、面積的單位分別為(mm)和(mm2);最優表示為在這30次中，得到的目標函數cost()最小時所對應的線長和面積;平均表示這30次的線長之和與面積之和的平均.從表3可知，當w=0.5時，混合遺傳算法在所有的例子上都能得到比一般遺傳算法更好的解，cost(F)的值都小于一般的遺傳算法.

表3 不同算法在MCNC測試例子的實驗結果對比(w=0.5)Tab.3 Comparison of results on MCNC benchmarks by the two algorithms(w=0.5)

4 結語

基于B*-tree的結構表示，結合遺傳算法，提出一種用于解決VLSI不可二劃分布圖規劃問題的混合遺傳算法.在全局搜索時，該算法采用交叉和變異的運算使有效的拓撲信息得到保留;在局部搜索中，通過不斷地交換B*-tree的結點，得到一個局部最優解.在MCNC標準測試例子集測試的實驗結果表明，該混合遺傳算法比一般的遺傳算法更為有效.

根據具體的布圖需求和其它約束(溫度、功耗等)條件，進一步完善我們所提出的算法是以后研究工作的一個方向.此外，改進所提出的算法用來求解3D布圖規劃問題也是今后研究的一個重點.