面向軟模塊的穩(wěn)定固定邊框布圖規(guī)劃算法

杜世民 夏銀水 儲著飛 黃 誠 楊潤萍

?

面向軟模塊的穩(wěn)定固定邊框布圖規(guī)劃算法

杜世民*①②夏銀水①儲著飛①黃 誠①楊潤萍②

①(寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211)②(寧波大學(xué)科學(xué)技術(shù)學(xué)院 寧波 315212)

該文提出一種穩(wěn)定的面向軟模塊的固定邊框布圖規(guī)劃算法。該算法基于正則波蘭表達(dá)式(Normalized Polish Expression, NPE)表示，提出一種基于形狀曲線相加和插值技術(shù)的計(jì)算NPE最優(yōu)布圖的方法，并運(yùn)用模擬退火(Simulation Annealing, SA)算法搜索最優(yōu)解。為了求得滿足固定邊框的布圖解，提出一種基于刪除后插入(Insertion After Delete, IAD)算子的后布圖優(yōu)化方法。對8個(gè)GSRC和MCNC電路的實(shí)驗(yàn)結(jié)果表明，所提出算法在1%空白面積率的邊框約束下的布圖成功率接近100%，在總線長上較已有文獻(xiàn)有較大改進(jìn)，且在求解速度上較同類基于SA的算法有較大優(yōu)勢。

布圖規(guī)劃；固定邊框；后布圖優(yōu)化；刪除后插入算子；形狀曲線相加

1 引言

為此，本文提出一種有效的后布圖優(yōu)化方法。首先對正則波蘭表達(dá)式(Normalized Polish Expression, NPE)[14]表示的布圖解，應(yīng)用形狀曲線相加算法和插值技術(shù)來計(jì)算其最優(yōu)的布圖實(shí)現(xiàn)。其次，運(yùn)用SA算法來求取以總線長和固定邊框約束為目標(biāo)的布圖近優(yōu)解。然后將SA所得解作為初始解，提出了一種基于刪除后插入(Insertion After Delete, IAD)算子的后布圖優(yōu)化方法來獲得滿足固定邊框的布圖解，提高了布圖算法的成功率。最后，通過交換同一運(yùn)算符下的操作數(shù)位置來進(jìn)一步降低總線長。

2 問題描述及有關(guān)表示

2.1 問題描述

面向軟模塊的FOF問題的輸入包括：

要求確定每個(gè)模塊m的尺寸(w, h)及其在芯片中的坐標(biāo)(x,y)，使這些模塊互不重疊地放置在指定的固定邊框內(nèi)，同時(shí)優(yōu)化芯片的面積和總線長。

由上述定義可知，固定邊框約束下的合法布圖須滿足：

式(1)中和分別為所得布圖的寬度和高度；W和H為固定邊框的寬度和高度，可由式(2)計(jì)算：

其中為中所有模塊的總面積。若所得布圖不能同時(shí)滿足式(1)中的兩個(gè)條件，則為非法布圖。

2.2 布圖表示

迄今已提出多種有效的布圖表示方法，如B*-tree[15], SP[16]，約束圖[17]，SKB[7], NPE[2,5,14]等，其中NPE表示具有計(jì)算簡單和便于處理軟模塊形狀上的靈活性等優(yōu)點(diǎn)[2,5]，故采用它表示布圖解，其一般形式為

(3)

式(3)中，1~分別表示個(gè)模塊，也稱操作數(shù)(operand),“*”和“+”表示模塊之間的運(yùn)算符(operator)：“*”表示兩個(gè)模塊橫向或水平組合，“+”表示兩個(gè)模塊縱向或垂直組合。

3 NPE的布圖計(jì)算

由于所給定模塊的尺寸可變，一個(gè)NPE對應(yīng)多種可能的布圖實(shí)現(xiàn)[5,17]。本文先采用形狀曲線來表示每個(gè)軟模塊，然后提出一種形狀曲線相加算法和插值方法來獲得每個(gè)NPE的最優(yōu)布圖。

3.1 軟模塊的形狀曲線

由FOF問題的輸入可知，任意模塊m的高度w和寬度h滿足：

式(4)可表示為圖1中的一段曲線，稱之為m的形狀曲線，端點(diǎn)和稱為該形狀曲線的頂點(diǎn)。

3.2 形狀曲線相加算法

由于每個(gè)軟模塊都可用形狀曲線來描述，因此，可將它們之間的運(yùn)算轉(zhuǎn)化為相應(yīng)形狀曲線之間的運(yùn)算。當(dāng)兩個(gè)模塊作“*”或“+”運(yùn)算時(shí)，分別對應(yīng)于各自的形狀曲線進(jìn)行橫向或縱向相加。

設(shè)1和2為兩個(gè)軟模塊，其形狀曲線分別如圖2(a)中1-2和1-2所示。3為它們作“*”運(yùn)算后得到的組合模塊，其高度3和寬度3可由下式計(jì)算：

圖2 形狀曲線相加示意圖

由此可知，當(dāng)兩個(gè)模塊進(jìn)行“*”運(yùn)算時(shí)，所得組合模塊的面積或保持不變或是其高度的線性函數(shù)。因此，在對軟模塊的形狀曲線進(jìn)行“*”相加時(shí)，只需簡單地在它們的頂點(diǎn)處進(jìn)行相應(yīng)的橫向相加就可以了。當(dāng)兩個(gè)模塊作“+”運(yùn)算時(shí)，其形狀曲線之間的相加可以用類似的方法來實(shí)現(xiàn)，如圖2(b)所示。

由于每次計(jì)算新解的布圖時(shí)都會涉及到較多兩個(gè)軟模塊之間的“*”或“+”運(yùn)算，為提高算法速度，可預(yù)先計(jì)算出所有軟模塊兩兩組合運(yùn)算的結(jié)果。這樣每次計(jì)算新解時(shí)，就可節(jié)省這部分運(yùn)算所需的時(shí)間。

3.3 形狀曲線的插值

應(yīng)用上述方法計(jì)算NPE的形狀曲線，在計(jì)算過程中僅記錄了形狀曲線上的頂點(diǎn)信息，因此可能遇到相鄰兩頂點(diǎn)均不滿足但其內(nèi)部一些點(diǎn)卻已滿足固定邊框約束的情況。例如在圖3中，頂點(diǎn)1(1,1)和2(2,2)均在邊框外，但它們之間的某些點(diǎn)卻已落在邊框內(nèi)。這時(shí)，需要對形狀曲線以一定的步長進(jìn)行插值。設(shè)圖3中頂點(diǎn)1和2處的面積分別為1和2，插值步長為，則1-2之間任一點(diǎn)A的面積s和坐標(biāo)(x,y)可計(jì)算如下：

圖3 對NPE形狀曲線進(jìn)行插值

4 本文提出的算法

4.1 算法流程

本文提出了一種改進(jìn)的固定邊框布圖規(guī)劃的算法流程。首先以固定邊框約束和總線長為目標(biāo)，利用SA算法對解空間進(jìn)行搜索。然后判斷SA求得的布圖解是否滿足固定邊框，如果不滿足，提出了一種新的IAD算子對該解進(jìn)行后布圖優(yōu)化，將其轉(zhuǎn)變?yōu)闈M足固定邊框的解。最后通過交換NPE中同一運(yùn)算符下的兩個(gè)操作數(shù)的左右/上下次序，對總線長作進(jìn)一步的優(yōu)化，整個(gè)算法的流程如圖4所示。

在上述流程中，由于在SA算法后新增了一個(gè)后布圖優(yōu)化步驟，只要SA算法能搜索到一個(gè)接近于固定邊框的解，就可以通過該步驟將其修正為合法解，從而放寬了約束條件，因此提高整個(gè)算法的布圖成功率。

4.2 基于IAD算子的后布圖優(yōu)化方法

(1)一個(gè)較小的單一模塊和一個(gè)較大的模塊進(jìn)行組合運(yùn)算；

(2)一個(gè)較小的組合模塊和一個(gè)較大的模塊進(jìn)行組合運(yùn)算。

圖4 本文算法流程

在上述兩種情況下，由于參與運(yùn)算的兩個(gè)操作數(shù)尺寸相差較大，組合后產(chǎn)生較大的空白面積，從而導(dǎo)致所得布圖超出指定的邊框，因此稱它們?yōu)榉莾?yōu)組合。圖5(a)和圖6(a)分別給出了這2類非優(yōu)組合的示例（圖中的虛線框表示固定邊框）。

在圖5(a)中，所得布圖的寬度雖已滿足約束條件，但在高度上違反了約束。其原因是在該布圖解中存在一對非優(yōu)的組合運(yùn)算，即模塊7和由子表達(dá)式“8 6 + 9 5 1 * 2 + * 4 3 * + *”表示的組合模塊之間的組合運(yùn)算。如果能設(shè)法消除布圖解中存在的類似的非優(yōu)組合，就有可能將一個(gè)接近于滿足固定邊框的近似解轉(zhuǎn)化為合法的布圖解。

從圖5(a)不難發(fā)現(xiàn)，若將模塊7從該布圖中刪除，然后將其重新插入到圖中的合適位置，就有可能得到一個(gè)合法的布圖，如圖5(b)所示。這是因?yàn)椋?1)模塊7刪除后所得到的較大空白區(qū)域給其它模塊的尺寸調(diào)整提供了空間；(2)由于模塊7面積較小，將它重新插入后不至于對原有已接近于滿足邊框約束的布圖產(chǎn)生過大的改變。因此，通過這樣一種先刪除后插入操作，可以有效地消除布圖解中的非優(yōu)組合。本文提出的后優(yōu)化策略正是基于這一思想，同時(shí)將這種新的用于后布圖優(yōu)化的操作稱為IAD算子。

應(yīng)用IAD算子來消除SA算法解中的一對非優(yōu)組合，需經(jīng)過以下3個(gè)步驟：

步驟1 找出原布圖解(NPE)中存在的非優(yōu)組合；

步驟2 刪除非優(yōu)組合中面積較小的模塊(設(shè)為m)；

步驟3 將刪除后模塊m重新插入到原布圖解的合適位置。

在上述步驟中，由于沒有直觀的方法來確定m在中最合適的插入位置，因此采用了枚舉法，即通過將m和中所有模塊分別進(jìn)行“*”和“+”組合運(yùn)算，然后比較每種組合下的目標(biāo)函數(shù)(此時(shí)以滿足固定邊框?yàn)槟繕?biāo))來確定m在中最佳的插入位置。利用該方法消除一對非優(yōu)組合最多需進(jìn)行次插入操作。由于經(jīng)過SA算法優(yōu)化后，中非優(yōu)組合的數(shù)目并不多，因此后布圖優(yōu)化所需的計(jì)算量和前面的SA算法相比基本可以忽略。

圖5 非優(yōu)布圖和優(yōu)化后布圖

在圖6(a)中，子表達(dá)式“6 8 +”和“9 5 7 * 2 + * 4 3 1 + * +”之間的橫向組合屬于第2類非優(yōu)組合。首先將子表達(dá)式“6 8 +”所表示的組合模塊從當(dāng)前NPE中刪除，然后將其拆成兩個(gè)獨(dú)立的模塊：6和8，再依次將這兩個(gè)模塊插入到余下布圖解(NPE)中的合適位置，最終得到了一個(gè)合法的布圖解，如圖6(c)。

綜上，可得到所提出的基于IAD算子的后布圖優(yōu)化算法的流程，如流程1所示。

流程1：基于IAD算子的后布圖優(yōu)化算法流程

圖6 方式2操作示意圖

(4)在當(dāng)前布圖解中刪除m及其對應(yīng)的運(yùn)算符；

(5)將m依次和中所有模塊m(≠m)分別進(jìn)行“*”和“+”組合運(yùn)算，并記錄下該過程中的最優(yōu)解；

(6)判斷m是否為組合模塊，若是，轉(zhuǎn)第(7)步，否則轉(zhuǎn)第(9)步；

(7)將m拆分成一個(gè)個(gè)單一模塊，然后按面積大小順序逐一插入到中，記錄下該過程中最優(yōu)解；

(9)1，判斷是否等于0？若是，轉(zhuǎn)下一步，否則，將賦給，轉(zhuǎn)第(3)步；

流程中的A是一個(gè)經(jīng)驗(yàn)參數(shù)。當(dāng)它取值過小時(shí)，后布圖優(yōu)化次數(shù)增加，會導(dǎo)致總線長增加；而當(dāng)它取值太大時(shí)，會忽略掉一些非優(yōu)組合，優(yōu)化后不易滿足固定邊框約束。經(jīng)多次實(shí)驗(yàn)測試，A取/500較為合適。

5 實(shí)驗(yàn)結(jié)果

為進(jìn)一步驗(yàn)證本文算法的有效性，本文在1%空白面積約束下，讓高寬比以0.5的步長從1增加到6對上述5個(gè)電路進(jìn)行了實(shí)驗(yàn)。表1給出了所得的布圖成功率SR(%)及空白面積率WS(%)結(jié)果。從表1可見，所有電路均獲得了99%以上的布圖成功率(僅ami33和ami49在部分下有1%的失敗率)，且平均空白面積率0.04%。特別是在高寬比達(dá)到5:1或6:1時(shí)，除ami33外所有電路仍可達(dá)100%的成功率，表明本文算法對不同高寬比的固定邊框約束具有良好的穩(wěn)定性。

表3列出了本文算法和A-FP[8], SAFFOA[6], SKB[7]等方法在不同下所得到的總線長的比較。由表可見，當(dāng)芯片高寬比分別為2:1, 3:1和4:1時(shí)，本文所提出的算法較A-FP可分別減少38.0%, 36.5%和35.3%的總線長；與SAFFOA相比，本文所提出算法在總線長上分別減少了17.9%, 13.7%和14.8%。與SKB相比，本文算法在總線長上分別減少了5.5%, 4.1%和5.4%?？梢姡疚乃岢鏊惴ㄍㄟ^對總線長的二次優(yōu)化，使其在不同的高寬比下都可得到較低的總線長。圖8(a)-圖8(d)分別給出了n300在時(shí)的布圖結(jié)果。

表1不同高寬比下固定邊框的布圖成功率及空白面積率結(jié)果(%)

電路高寬比?平均 1:11.5:12:12.5:13:13.5:14:14.5:15:15.5:16:1 ami33WS0.0150.0120.0120.0100.0200.0320.0410.0380.0490.0510.0560.031 SR1001001001009910010099999910099.636 ami49WS0.0110.0070.0690.0040.0160.0160.0540.0580.0710.0450.0810.039 SR100991001001001001009910010010099.818 n100WS0.0150.0200.0190.0300.0260.0400.0210.0330.0710.0660.0550.036 SR100100100100100100100100100100100100 n200WS0.0180.0200.0220.0200.0240.0320.0260.0390.0420.0480.0390.030 SR100100100100100100100100100100100100 n300WS0.0380.0190.0400.0260.0320.0290.0210.0430.0250.0250.0650.033 SR100100100100100100100100100100100100

表2分別與文獻(xiàn)[8,9,3,6,7]總線長及運(yùn)行時(shí)間(s)的比較

電路A-FP[8]PATOMA[9]Parquet 4.0[3]SAFFOA[6]SKB [7]本文 HPWL時(shí)間HPWL時(shí)間HPWL時(shí)間HPWL時(shí)間HPWL時(shí)間HPWL時(shí)間 n10-- 522581 50690146207 236175 438459 0.1 n30-- 15692111663361138218 14102579 13102475 0.8 n50--1801151 1891212165366 39129916 16125754 2.6 n1002916282028345223174661026246915819917111317225012.8 n20057214531505736258159657480573690388277613348182 61.3 n30070282241566242477008916055172015635330591247541759144.1 平均1.4750.422 1.3130.050 1.5621.042 1.23811.123 1.0459.0481.0001.000

注：表中“-”表示原文未給出結(jié)果，下同。

表3 本文分別與文獻(xiàn)[6,7,8]在不同高寬比下總線長的比較

6 結(jié)論

本文提出了一種穩(wěn)定的基于IAD算子的固定邊框布圖規(guī)劃算法。和傳統(tǒng)方法相比，該算法新增了一個(gè)后布圖優(yōu)化步驟，放寬了SA優(yōu)化時(shí)對解的苛刻的邊框約束，從而提高算法的收斂速度。本文提出了一種新的IAD算子對SA所得的布圖解進(jìn)行后優(yōu)化，從而提高了布圖成功率。同時(shí)在算法中對總線長進(jìn)行了二次優(yōu)化。實(shí)驗(yàn)結(jié)果表明，本文算法在寬范圍的高寬比下可實(shí)現(xiàn)接近100%的布圖成功率和接近于零的空白面積率，且和已有文獻(xiàn)相比，可獲得總線長和求解速度都較優(yōu)的布圖結(jié)果。

[1] 徐寧, 洪先龍, 董社勤. BBL布局算法研究[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(9): 1216-1219.

Xu Ning, Hong Xian-long, and Dong She-qin. Algorithm research on VLSI placement[J].&, 2004, 16(9): 1216-1219.

[2] 杜世民, 夏銀水, 羅佐. 基于切分結(jié)構(gòu)的快速布圖規(guī)劃方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(4): 99.0005-99.0008.

Du Shi-min, Xia Yin-shui, and Luo Zuo. Fast floorplanning algorithm base on slicing structure[J]., 2013, 30(4): 99.0005-99.0008.

[3] Adya S N and Markov I L. Fixed-outline foorplanning: enabling hierarchical design[J]., 2003, 11(6): 1120-1135.

[4] Chen Song and Yosihmura Takeshi. A stable fixed-outline floorplanning method[C]. Proceedings of the 2007 International Symposium on Physical Design, Austin, Texas, USA, 2007: 119-126.

[5] Yan J Z and Chu Chris. DeFer: deferred decision making enabled fixed-outline floorplanning algorithm[J]., 2010, 29(3): 367-381.

[6] He Ou, Dong She-qin, and Bian Ji-nian. A novel fixed-outline floorplanner with zero deadspace for hierarchical design[C]. IEEE/ACM International Conference on Computer-Aided Design, San Jose, California, USA, 2008: 16-23.

[7] Lin Jai-ming and Hung Zhi-xiong. SKB-Tree: a fixed-outline driven representation for modern floorplanning problems[J].(), 2012, 20(3): 473-484.

[8] Zhan Yong, Feng Yan, and Sapatnekar S S. A fixed-die floorplanning algorithm using an analytical approach[C]. 11th Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2006: 771-776.

[9] Cong Jason, Romesis Michail, and Shinnerl Joseph R. Fast floorplanning by look-ahead enabled recursive bipartition[J]., 2006, 25(9): 1719-1732.

[10] Hoo Chyi-shiang, Jeevan Kanesan, Antipathy Velappa,.. PPTP: Pre-Post Terminal Propagation in modern fixed-outline soft module VLSI floorplanning design[C]. Proceedings of the 10th IEEE International Conference on Semiconductor Electronics, Kuala Lumpur, Wilayah Persekutuan, Malaysia, 2012: 448-452.

[11] Chan Kai-chung,Hsu Chao-jam, and Lin Jia-ming. A flexible fixed-outline floorplanning methodology for mixed-size modules[C]. 18th Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2013: 435-440.

[12] Yan J Z and Chu C. SDS: an optimal slack-driven block shaping algorithm for fixed-outline floorplanning[J].2013, 32(2): 175-188.

[13] Kirkpatrick S, Gelatt C D, and Vecchi M P. Optimization by simulated annealing[J].1983, 220(4598): 671-680.

[14] Wong D F and Liu C L. A new algorithm for floorplan design[C]. Proceedings of the 23rd ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA, 1986: 101-107.

[15] Chen Tung-chieh and Chang Yao-wen. Modern floorplanning based on B*-tree and fast simulated annealing[J]., 2006, 25(4): 637-650.

[16] Senguptaa Dipanjan, Veneris Andreas, Wilton Steve,. Multi-objective voltage island floorplanning using sequence pair representation[J]., 2012, 2(2): 58-70.

[17] Wang Jia and Zhou Hai. Linear constraint graph for floorplan optimization with soft blocks[C]. IEEE/ ACM International Conference on Computer-Aided Design, San Jose, California, USA, 2008: 9-15.

杜世民： 男，1976年生，博士生，講師，研究方向?yàn)榧呻娐吩O(shè)計(jì)自動化.

夏銀水： 男，1963年生，研究員，博士生導(dǎo)師，研究方向?yàn)榧呻娐肪C合和優(yōu)化、高信息密度集成電路.

儲著飛： 男，1986年生，博士生，研究方向?yàn)榧呻娐吩O(shè)計(jì)自動化.

A Stable Fixed-outline Floorplanning Algorithm for Soft Module

Du Shi-min①②Xia Yin-shui①Chu Zhu-fei①Huang Cheng①Yang Run-ping②

①(,,315211,)②(&,,315212,)

A stable Fixed-Outline Floorplanning (FOF) algorithm for soft module is proposed in this paper. It takes the Normalized Polish Expression (NPE) as a floorplan solution, using the shape curve adding algorithm and the interpolation technique to compute the best floorplan of a NPE. The Simulated Annealing (SA) algorithm is used to search the solution space. A post-floorplanning optimization method based on the new Insertion After Delete (IAD) operator is adopted to optimize those SA floorplan solutions which fail to meet the fixed-outline constraints. The experimental results on eight GSRC and MCNC benchmarks show that the proposed algorithm can not only achieve a nearly 100% floorplanning success rate under fixed-outline constraints with 1% white space but can also obtain better total wirelength than previous works. Besides, the proposed algortihtm has a greater advantage in the runtime over the similar SA-based algorithms.

Floorplanning; Fixed-outline; Post-floorplanningoptimization; Insertion After Delete (IAD) operator;Shape curve adding

TN402; TP391.72

A

100.0009-5896(2014)05-1258-08

10.3724/SP.J.1146.2013.01181

杜世民 dushimin@nbu.edu.cn

2013-08-06收到，2014-01-17改回