電壓島驅(qū)動(dòng)的多級(jí)布圖規(guī)劃優(yōu)化算法

杜世民,夏銀水,儲(chǔ)著飛,楊潤(rùn)萍

(1.寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江寧波 315211；2.寧波大學(xué)科學(xué)技術(shù)學(xué)院,浙江寧波 315212)

電壓島驅(qū)動(dòng)的多級(jí)布圖規(guī)劃優(yōu)化算法

杜世民1,2,夏銀水1,儲(chǔ)著飛1,楊潤(rùn)萍2

(1.寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江寧波 315211；2.寧波大學(xué)科學(xué)技術(shù)學(xué)院,浙江寧波 315212)

針對(duì)多電壓布圖算法速度較慢、空白面積較高這一問(wèn)題,提出了一種電壓島驅(qū)動(dòng)的多級(jí)布圖規(guī)劃優(yōu)化方法.首先,以功耗為優(yōu)化目標(biāo),應(yīng)用線性整數(shù)規(guī)劃分配模塊電壓,將相同電壓的模塊劃分至同一電壓島;其次,提出一種基于枚舉和形狀曲線相加的快速方法對(duì)所得各電壓島進(jìn)行布圖;最后,構(gòu)建一個(gè)線性規(guī)劃模型來(lái)求解通過(guò)交換布圖解中模塊位置來(lái)減少線長(zhǎng)的問(wèn)題,對(duì)線長(zhǎng)做進(jìn)一步優(yōu)化.實(shí)驗(yàn)結(jié)果表明,和已有方法相比,該方法在算法速度和芯片空白面積率方面有較明顯優(yōu)勢(shì).

低功耗;布圖規(guī)劃;多電壓;電壓島;多級(jí)優(yōu)化

功耗是當(dāng)前片上系統(tǒng)（System-on-a-Chip,SoC)設(shè)計(jì)所面臨的一個(gè)關(guān)鍵挑戰(zhàn),基于多供電電壓（Multiple Supply Voltage,MSV)的設(shè)計(jì)方法被認(rèn)為是解決SoC功耗問(wèn)題最為有效的方法之一[1-3].在MSV設(shè)計(jì)中,為減少電源網(wǎng)絡(luò)的布線資源的需求及便于電平轉(zhuǎn)換器（Level Shifters,LS)的布置,需將相同電壓的模塊聚集在一起,形成電壓島（Voltage Islands,VI),這使傳統(tǒng)的物理設(shè)計(jì)流程變得更加復(fù)雜[1-2].

目前,針對(duì)MSV設(shè)計(jì)的研究主要集中在芯片物理設(shè)計(jì)的布圖[1-2,4-7]和后布圖階段[8-10].文獻(xiàn)[8]提出了一種分散度函數(shù)（Fragmentation Cost)來(lái)度量電源網(wǎng)絡(luò)的復(fù)雜度,采用0-1整數(shù)線性規(guī)劃給物理上相鄰的模塊分配相同的電壓,生成電壓島以減少功耗,并降低電源網(wǎng)絡(luò)的分散度.文獻(xiàn)[9]改進(jìn)了文獻(xiàn)[8]的電源網(wǎng)絡(luò)復(fù)雜度模型,提出了一種基于遺傳算法的多電壓分配算法.然而,上述兩種方法均無(wú)法生成連續(xù)的電壓島,這會(huì)使電源布線網(wǎng)絡(luò)十分復(fù)雜.文獻(xiàn)[4]將電壓分配嵌入到布圖過(guò)程中,對(duì)每個(gè)新產(chǎn)生的布圖解,應(yīng)用動(dòng)態(tài)規(guī)劃分配電壓,并構(gòu)建電壓島,然后以所得布圖的面積、總線長(zhǎng)和功耗的加權(quán)和作為目標(biāo)函數(shù)評(píng)估該布圖解.由于該方法需對(duì)每個(gè)解分配1次電壓,使得算法較為耗時(shí).為避免進(jìn)行多次的電壓分配,文獻(xiàn)[5]在布圖之前先進(jìn)行電壓分配,然后分別采用基于文獻(xiàn)[11]和文獻(xiàn)[5]的布圖算法對(duì)電壓島及其內(nèi)部模塊進(jìn)行布圖,重復(fù)該步驟直至收斂.但該方法無(wú)法快速找到較優(yōu)的電壓島布圖,需通過(guò)對(duì)電壓島及其內(nèi)部模塊進(jìn)行多次布圖來(lái)迭代改進(jìn)面積和線長(zhǎng),使得算法耗時(shí)較長(zhǎng),并產(chǎn)生較大的空白面積（Dead Space,DS).

為此,在筆者先前研發(fā)的固定邊框布圖規(guī)劃算法[12]的基礎(chǔ)上,提出了一種電壓島驅(qū)動(dòng)的多級(jí)布圖規(guī)劃優(yōu)化方法.首先,以降低功耗為目標(biāo),應(yīng)用整數(shù)線性規(guī)劃（Integer Linear Programming,ILP)分配模塊電壓,并依據(jù)電壓分配結(jié)果構(gòu)建電壓島;其次,提出一種基于枚舉和形狀曲線相加的方法來(lái)對(duì)所得電壓島進(jìn)行布圖,優(yōu)化電壓島布圖的面積及電壓島之間的線長(zhǎng);然后,采用文獻(xiàn)[12]方法對(duì)各電壓島內(nèi)的模塊進(jìn)行固定邊框的布圖;最后,通過(guò)交換布圖解中同一運(yùn)算符下兩個(gè)操作數(shù)位置對(duì)線長(zhǎng)做進(jìn)一步優(yōu)化.由于文中方法避免了對(duì)電壓島及其內(nèi)部模塊進(jìn)行多次的布圖,因此,可大大提高算法的速度.其次,通過(guò)對(duì)線長(zhǎng)進(jìn)行多級(jí)的優(yōu)化,則有效降低了矩形電壓島所帶來(lái)的線長(zhǎng)方面的開(kāi)銷(xiāo).

1 問(wèn)題描述及表示

1.1 問(wèn)題描述

為簡(jiǎn)化電源網(wǎng)絡(luò)的規(guī)劃并降低LS布置的難度,要求將采用相同電壓供電的模塊聚集在一起,形成電壓島,并限定電壓島的總數(shù).給定如下輸入信息:①一個(gè)包含N個(gè)模塊的集合B={b1,b2,…,bN}及芯片的n個(gè)供電電壓;②每個(gè)模塊bi的面積ai和高寬比范圍[li,ri],1≤ i≤N;③所有模塊之間的線網(wǎng)連接Nets={Nj,j=1,2,…,M};④每個(gè)模塊bi可行的供電電壓集Vi∈Vc及對(duì)應(yīng)的功耗集Pi,1≤i≤N（與文獻(xiàn)[4-5]一樣,這里假定每個(gè)模塊的可行電壓均已滿足時(shí)序要求);⑤允許的電壓島最大個(gè)數(shù)Km（1≤Km≤n).要求為每個(gè)模塊分配一個(gè)合適的供電電壓,并產(chǎn)生至多包含Km個(gè)矩形電壓島的布圖,使芯片功耗降到最低,同時(shí)優(yōu)化總線長(zhǎng)和電源網(wǎng)絡(luò)布線資源.

1.2 布圖表示及計(jì)算

常用的布圖表示有B*-Tree、序列對(duì)（Sequence Pair,SP)[13]、正則波蘭表達(dá)式（Normalized Polish Expression,NPE)[12]等,其中,NPE具有計(jì)算簡(jiǎn)單及便于電壓島規(guī)劃[4,12]等優(yōu)點(diǎn),故采用它表示布圖解. NPE的一般形式可表示為

其中,1～N分別表示N個(gè)模塊對(duì)應(yīng)的序號(hào);“*”和“+”表示模塊之間的運(yùn)算符,“*”表示兩個(gè)模塊水平（或橫向)組合,“+”表示兩個(gè)模塊垂直（或縱向)組合.由于所給定模塊尺寸在一定范圍內(nèi)可變,同一布圖解（NPE)對(duì)應(yīng)多種可能的布圖實(shí)現(xiàn).應(yīng)用形狀曲線相加算法[12]可計(jì)算出每個(gè)NPE所有的布圖實(shí)現(xiàn).圖1（a)和（b)分別給出了兩個(gè)模塊b1和b2進(jìn)行“*”和“+”運(yùn)算時(shí)形狀曲線相加的示意圖.圖1中,曲線A1-A2和B1-B2分別為b1和b2的形狀曲線,C1-C2-C3為它們運(yùn)算后所生成組合模塊的形狀曲線.

圖1 形狀曲線相加示意圖

2 文中提出的算法

文中約束相同電壓模塊放置在同一矩形電壓島內(nèi),這樣雖可大大簡(jiǎn)化電源網(wǎng)絡(luò)的規(guī)劃,但會(huì)帶來(lái)線長(zhǎng)增加的問(wèn)題.為能有效控制線長(zhǎng)的增加、加快算法的速度和降低芯片的空白面積率,文中提出了一種如圖2（a)所示的電壓島驅(qū)動(dòng)的布圖算法流程,其操作步驟如下:

圖2 所提出的算法及其圖形化說(shuō)明

Step 1 以降低功耗為目標(biāo),采用ILP來(lái)分配模塊的供電電壓,并依據(jù)所得的電壓分配結(jié)果,將相同電壓的模塊劃分到同一電壓島,以降低電源布線網(wǎng)絡(luò)的復(fù)雜度,并獲得功耗最優(yōu)的電壓分配方案.

Step 2 將所得各電壓島視為軟模塊,應(yīng)用枚舉和形狀曲線相加方法對(duì)各電壓島進(jìn)行布圖,使所得布圖的面積和線長(zhǎng)最優(yōu).

Step 3 根據(jù)Step 2所得的電壓島尺寸,采用文獻(xiàn)[12]所提出方法對(duì)電壓島內(nèi)所包含模塊進(jìn)行固定邊框的布圖,確定島內(nèi)每個(gè)模塊在相應(yīng)電壓島的位置和尺寸,并優(yōu)化它們之間的線長(zhǎng).

Step 4 通過(guò)交換同一運(yùn)算符下的電壓島或模塊的上下/左右位置,對(duì)線長(zhǎng)做進(jìn)一步優(yōu)化.在此步驟中,可將這一問(wèn)題構(gòu)建為一個(gè)線性規(guī)劃（Linear Programming,LP)模型,通過(guò)求解該模型來(lái)獲得線長(zhǎng)最優(yōu)的模塊位置.

上述流程中,采用基于枚舉和形狀曲線相加的方法來(lái)獲得電壓島布圖,可快速獲得面積和線長(zhǎng)最優(yōu)的電壓島布圖,避免了文獻(xiàn)[5]對(duì)電壓島及其內(nèi)部模塊進(jìn)行多次的布圖,因此,可有效提高算法速度和降低芯片的空白面積率.其次,流程中對(duì)線長(zhǎng)進(jìn)行多級(jí)的優(yōu)化,可將矩形電壓島所帶來(lái)的線長(zhǎng)開(kāi)銷(xiāo)控制在較低的水平.圖2（b)以10個(gè)模塊電路為例,給出了上述流程的一個(gè)說(shuō)明.下面分別介紹流程中的Step 1、Step 2和Step 4.

2.1 基于ILP的多電壓分配算法

面向功耗優(yōu)化的多電壓分配問(wèn)題描述如下:從芯片的全部n個(gè)供電電壓中選擇K（K≤n)個(gè)供電電壓,1＜K≤Km,并從Vs中選擇其中一個(gè)分配給每個(gè)模塊bi（必須是bi的可行電壓之一),使所有模塊的總功耗Ptotal最低.下面構(gòu)建一個(gè)ILP模型來(lái)求解該問(wèn)題.

式（3)即為待優(yōu)化的目標(biāo).約束條件如下:

式（4)和式（5)表示僅能從bi的可行電壓中選擇其中一個(gè)分配給模塊bi,式（6)約束供電電壓總數(shù)不能超過(guò)指定的電壓島數(shù)Km.分配模塊電壓后,將相同電壓的模塊劃分到同一電壓島,即可得到K個(gè)電壓島I= {I1,I2,…,IK},如圖2（b)中Step1結(jié)果所示.

2.2 電壓島級(jí)的布圖算法

文中約束相同電壓的模塊放置在同一電壓島內(nèi),因此所得電壓島數(shù)目較少.相應(yīng)地,由這些電壓島構(gòu)成的布圖解空間也較小,故可用枚舉法求出所有布圖解.圖3給出了電壓島數(shù)K分別取2～5時(shí),所有可能布圖解的切分樹(shù)（Slicing Tree,ST)表示.圖3中,“☉”表示運(yùn)算符（“*”或“+”),“□”表示電壓島（I1,I2,…,IK).

圖3 K取2～5時(shí)電壓島布圖解的切分樹(shù)表示

若用d（K)表示K個(gè)電壓島時(shí)的布圖解個(gè)數(shù),則其計(jì)算式為

其中,[K/2]表示K/2的整數(shù).由式（7)可知,當(dāng)電壓島數(shù)K較少時(shí),相應(yīng)的電壓島布圖解數(shù)不多,可以采用枚舉法求出所有的布圖解.但隨著K的增加,布圖解數(shù)將增加很快.因此,枚舉法適用于電壓島數(shù)較少的場(chǎng)合（如K≤6).

由于各電壓島均由若干軟模塊構(gòu)成,在對(duì)它們進(jìn)行布圖時(shí),亦可將它們視作軟模塊.于是,按圖3切分樹(shù)產(chǎn)生一個(gè)布圖解Si后,應(yīng)用形狀曲線相加算法計(jì)算出Si的形狀曲線Γi,再在Γi上找出Si最優(yōu)的布圖實(shí)現(xiàn)Fi;然后,計(jì)算出Fi的目標(biāo)函數(shù)值,重復(fù)此過(guò)程,直至計(jì)算完所有布圖解;最后,保留此過(guò)程中的目標(biāo)函數(shù)最優(yōu)的布圖解SBest及相應(yīng)的布圖實(shí)現(xiàn)FBest.

對(duì)每個(gè)所得的布圖解Si,將其形狀曲線上DS最小的頂點(diǎn)作為Si的最優(yōu)實(shí)現(xiàn)Fi,并采用

作為目標(biāo)函數(shù)（用C（Fi)表示)來(lái)評(píng)估Fi,以?xún)?yōu)化所得布圖的面積及各電壓島之間的線長(zhǎng).其中,α為加權(quán)系數(shù),A為所得布圖的面積,W為各電壓島之間的線長(zhǎng).由于此階段電壓島內(nèi)模塊的具體位置未定,計(jì)算W時(shí)假定島內(nèi)模塊的端口（pins)位置均位于該電壓島的幾何中心.

2.3 基于LP的線長(zhǎng)優(yōu)化算法

對(duì)NPE或切分樹(shù)表示的可切分布圖,交換同一運(yùn)算符下兩個(gè)操作數(shù)的位置,并不會(huì)改變布圖的面積,卻可能使線長(zhǎng)得到改善.已有文獻(xiàn)一般通過(guò)對(duì)切分樹(shù)自上而下或自下而上的交換運(yùn)算符下的兩個(gè)操作數(shù)來(lái)減少線長(zhǎng)[14],但這種方法不能保證找到線長(zhǎng)最優(yōu)的模塊位置.因此,文中提出了一個(gè)LP模型來(lái)描述該問(wèn)題,通過(guò)求解該模型來(lái)獲得線長(zhǎng)最優(yōu)的模塊位置.

對(duì)布圖解中的每個(gè)運(yùn)算符pi（i=1,2,…,N-1),定義一個(gè)與其相關(guān)的三元組（pi,si,qi),其中,si為pi所生成的超模塊;qi表示pi下的左、右操作數(shù)（分別用li和ri表示)是否發(fā)生交換,若發(fā)生交換,qi=1;否則,qi=0.設(shè)si的左下角坐標(biāo)為x（si)和y（si),則li和ri的坐標(biāo)x（li)、y（li)和x（ri)、y（ri)分別表示如下:

（1)當(dāng)pi為“*”時(shí),有

其中,w（li)表示左操作li的寬度;w（ri)表示右操作數(shù)ri的高度.

（2)當(dāng)pi為“+”時(shí),有

其中,h（li)表示左操作數(shù)li的寬度;h（ri)表示右操作數(shù)ri的高度.

利用式（9)和式（10),對(duì)布圖解對(duì)應(yīng)的切分樹(shù)進(jìn)行一次后序遍歷,即可將每個(gè)模塊bi及超模塊si的坐標(biāo)表示為N-1個(gè)二進(jìn)制變量qi的線性函數(shù).

下面導(dǎo)出待優(yōu)化目標(biāo)線長(zhǎng)的表達(dá)式.設(shè)Nj表示線網(wǎng)中第j個(gè)線網(wǎng)（net),它連接電路中的zj個(gè)模塊,（Lxj,Lyj)和（Rxj,Ryj)分別為Nj的左下角和右上角坐標(biāo),設(shè)所有模塊的pins均位于模塊中心,線長(zhǎng)采用半周長(zhǎng)法（Half Perimeter Wire Length,HPWL)估算,對(duì)Nj中的任意模塊bjk,k=1,…,zj,則有

于是,布圖的總線長(zhǎng)為

其中,λj為Nj的權(quán)值.式（12)即為待優(yōu)化的目標(biāo)函數(shù),約束條件為式（9)～（11).求解該模型,即可獲得線長(zhǎng)最優(yōu)的模塊位置.

3 實(shí)驗(yàn)結(jié)果與分析

文中算法已用C++編程實(shí)現(xiàn),并在2.4 GHz CPU、2.0 GB RAM的PC上對(duì)6個(gè)GSRC（Gigascale Systems Research Center)電路進(jìn)行了實(shí)驗(yàn),所有模塊的高寬比范圍為[0.3,3].為與文獻(xiàn)[4-5]進(jìn)行公平比較,每個(gè)電路的供電電壓集Vc、每個(gè)模塊bi可行的供電電壓集Vi及模塊bi在電壓vj下的功耗計(jì)算方法與文獻(xiàn)[4-5]相同.目標(biāo)函數(shù)式（7)中的權(quán)重α=0.5.2.1節(jié)和2.3節(jié)的模型采用Gurobi[15]求解.

表1列出了文中方法與文獻(xiàn)[4-5]在總功耗、功耗節(jié)省率、空白面積率、線長(zhǎng)和運(yùn)行時(shí)間方面的結(jié)果比較.表1中K為電壓數(shù),由于不同電路達(dá)到最低功耗所需的電壓數(shù)不同,如n100需要5個(gè)電壓達(dá)到最低功耗,而n300僅需3個(gè)電壓,故不同電路K的取值范圍不同.表1中“歸一化”行為其他算法對(duì)文中算法所得實(shí)驗(yàn)結(jié)果的比值.由表1可見(jiàn),與文獻(xiàn)[4]相比,文中算法可減少14.7%的總功耗和12.2%的線長(zhǎng),平均空白面積率從2.10%減少到0.16%,且在算法速度上加快了16.2倍.這是因?yàn)槲墨I(xiàn)[4]在模擬退火算法（Simulation Annealing,SA)中同時(shí)優(yōu)化功耗、線長(zhǎng)和面積等多個(gè)指標(biāo),很難在較短時(shí)間內(nèi)找到一個(gè)各目標(biāo)都較優(yōu)的解;其次,它對(duì)每個(gè)新產(chǎn)生布圖解應(yīng)用動(dòng)態(tài)規(guī)劃分配1次電壓,使得算法十分耗時(shí).與文獻(xiàn)[5]相比,文中算法僅在線長(zhǎng)上增加了5.2%,但在空白面積率和算法速度上有明顯優(yōu)勢(shì),且所有電路實(shí)現(xiàn)了低于1%的空白面積率.這是因?yàn)槲闹兴惴ū苊饬宋墨I(xiàn)[5]對(duì)電壓島及其內(nèi)部模塊進(jìn)行多次布圖的缺點(diǎn),因而提高了算法速度.此外,由表1可以看出,當(dāng)電壓島數(shù)目K增加時(shí),算法時(shí)間并未隨之增加.這是由于當(dāng)K增加時(shí),每個(gè)電壓島包含的模塊數(shù)減少,對(duì)島內(nèi)模塊布圖所需時(shí)間亦隨之減少.圖4（a)和（b)分別給出了n100的4個(gè)電壓島和n200的5個(gè)電壓島時(shí)的布圖結(jié)果（圖中,縱坐標(biāo)h為高度,橫坐標(biāo)w為寬度).由圖4可見(jiàn),所有相同電壓的模塊放置在一起形成矩形電壓島,并且產(chǎn)生了極低的空白面積,驗(yàn)證了文中算法的有效性.

圖4 文中算法產(chǎn)生的多電壓布圖結(jié)果

表1 文中算法與與文獻(xiàn)[4-5]算法的實(shí)驗(yàn)結(jié)果比較

4 結(jié) 論

筆者提出了一種基于多級(jí)優(yōu)化的方法來(lái)解決電壓島驅(qū)動(dòng)的布圖規(guī)劃問(wèn)題.首先構(gòu)建一個(gè)ILP模型來(lái)分配模塊電壓,將芯片功耗降至最低;然后,提出一種基于枚舉和形狀曲線相加的方法來(lái)完成電壓島的布圖,避免了對(duì)電壓島本身及其內(nèi)部模塊多次的布圖規(guī)劃,加快了算法速度并減少了芯片空白面積率.為解決矩形電壓島帶來(lái)的線長(zhǎng)增加問(wèn)題,在流程中對(duì)線長(zhǎng)進(jìn)行了多級(jí)的優(yōu)化,可將線長(zhǎng)開(kāi)銷(xiāo)控制在較低的水平.實(shí)驗(yàn)結(jié)果表明,筆者提出的算法不僅在總功耗和總線長(zhǎng)上接近或優(yōu)于已有算法,且可明顯提高算法速度,并降低芯片的空白面積率.

[1]Lee W P,Liu H Y,Chang Y W.Voltage-Island Partitioning and Floorplanning under Timing Constraints[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2009,28(5):690-702.

[2]Chu Z F,Xia Y S,Wang L Y,et al.Efficient Nonrectangular Shaped Voltage Island Aware Floorplanning with Nonrandomized Searching Engine[J].Microelectronics Journal,2014,45(4):382-393.

[3]孫強(qiáng),孫興奇,馬光勝.一種高層次多電壓功耗優(yōu)化方法[J].西安電子科技大學(xué)學(xué)報(bào),2009,36(5):933-939. Sun Qiang,Sun Xingqi,Ma Guangsheng.High-level Power Optimization Method for Multiple Supply Voltage Using the Multi-objective Genetic Algorithm[J].Journal of Xidian University,2009,36(5):933-939.

[4]Ma Q,Young E F Y.Multivoltage Floorplan Design[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2010,29(4):607-617.

[5]Lin J M,Hung Z X.SKB-Tree:a Fixed-outline Driven Representation for Modern Floorplanning Problems[J].IEEE Transactions on Very Large Scale Integration Systems,2012,20(3):473-484.

[6]Meng Z,Chen S,Huang L.Irregularly Shaped Voltage Islands Generation with Hazard and Heal Strategy[C]// Proceedings of the International Symposium on Quality Electronic Design.Piscataway:IEEE,2015:310-315.

[7]Lin J M,Wu J H.F-FM:Fixed-outline Floorplanning Methodology for Mixed-size Modules Considering Voltage-island Constraint[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2014,33(11):1681-1692.

[8]Mak W K,Jr Chen W.Voltage Island Generation under Performance Requirement for Soc Designs[C]//Proceedings of the Asia and South Pacific Design Automation Conference.Piscataway:IEEE Computer Society,2007:798-803.

[9] 杜世民,夏銀水,戚利俠.基于遺傳算法的電壓島感知的多電壓分配[J].浙江大學(xué)學(xué)報(bào)(理學(xué)版),2013,40(1):56-61,66. Du Shimin,Xia Yinshui,Qi Lixia.Voltage Island-aware Multiple Voltage Assignment Based on Genetic Algorithm[J]. Journal of Zhejiang University(Science Edition),2013,40(1):56-61,66.

[10]Wang K,Dong S Q.Post-floorplanning Power Optimization for MSV-driven Application Specific NoC Design[C]// Proceedings of the IEEE International Symposium on Circuits and Systems.Piscataway:IEEE,2014:994-997.

[11]Chen T C,Chang Y W.Modern Floorplanning Based on B*-tree and Fast Simulated Annealing[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2006,25(4):637-650.

[12]杜世民,夏銀水,儲(chǔ)著飛,等.面向軟模塊的穩(wěn)定固定邊框布圖規(guī)劃算法[J].電子與信息學(xué)報(bào),2014,36(5):1258-1265. Du Shimin,Xia Yinshui,Chu Zhufei,et al.A Stable Fixed-outline Floorplanning Algorithm for Soft Module[J]. Journal of Electronics&Information Technology,2014,36(5):1258-1265.

[13]Senguptaa D,Veneris A,Wilton S,et al.Multi-objective Voltage Island Floorplanning Using Sequence Pair Representation[J].Sustainable Computing:Informatics and Systems,2012(2):58-72.

[14]Yan J Z,Chu C.Defer:Deferred Decision Making Enabled Fixed-outline Floorplanning Algorithm[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2010,29(3):367-381.

[15]Gurobi Optimization.Gurobi5.62[CP/OL].[2014-12-22].http://www.edgestone-it.com/gurobi.htm,2013.

（編輯:齊淑娟)

(卷 終)

Voltage island-driven multilevel floorplanning optimization algorithm

DU Shimin1,2,XIA Yinshui1,CHU Zhufei1,YANG Runping2
(1.Department of Information Science and Engineering,Ningbo Univ.,Ningbo 315211,China; 2.College of Science&Technology,Ningbo Univ.,Ningbo 315212,China)

Since the existing multiple voltage floorplanning algorithms are slower and generate a higher white space,a voltage island-driven multilevel floorplanning optimization algorithm is proposed.Firstly,an ILP(Integer Linear Programming)-based approach is used to assign the voltage to each module aiming at minimizing power consumption,and all modules are divided into different voltage islands according to their voltage assignment results.Secondly,a rapid method based on enumeration and shape curve adding techniques is proposed to determine the shape and position of each voltage island.Finally,an LP(Linear Programming)model is constructed to solve the wirelength optimization problem by exchanging blocks’positions.Experimental results show that our algorithm outperforms previous methods in runtime and chip area usage ratio.

lower power;floorplanning;multiple supply voltage;voltage islands;multilevel optimization

TP391

A

1001-2400（2015)06-0184-07

10.3969/j.issn.1001-2400.2015.06.031

2015-03-17

國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（61131001);“十二五”浙江省高校重點(diǎn)學(xué)科-計(jì)算機(jī)應(yīng)用技術(shù)資助項(xiàng)目（20121114);寧波市自然科學(xué)基金資助項(xiàng)目（2013A610003);浙江省教育廳科研資助項(xiàng)目（Y201016754)

杜世民（1976-),男,講師,寧波大學(xué)博士研究生,E-mail:dushimin@nbu.edu.cn.