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

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

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

杜世民1,2,夏銀水1,儲著飛1,楊潤萍2

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

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

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

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

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

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

1 問題描述及表示

1.1 問題描述

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

1.2 布圖表示及計算

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

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

圖1 形狀曲線相加示意圖

2 文中提出的算法

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

圖2 所提出的算法及其圖形化說明

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

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

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

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

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

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

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

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

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

2.2 電壓島級的布圖算法

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

圖3 K取2～5時電壓島布圖解的切分樹表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

于是,布圖的總線長為

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

3 實驗結(jié)果與分析

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

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

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

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

4 結(jié) 論

筆者提出了一種基于多級優(yōu)化的方法來解決電壓島驅(qū)動的布圖規(guī)劃問題.首先構(gòu)建一個ILP模型來分配模塊電壓,將芯片功耗降至最低;然后,提出一種基于枚舉和形狀曲線相加的方法來完成電壓島的布圖,避免了對電壓島本身及其內(nèi)部模塊多次的布圖規(guī)劃,加快了算法速度并減少了芯片空白面積率.為解決矩形電壓島帶來的線長增加問題,在流程中對線長進行了多級的優(yōu)化,可將線長開銷控制在較低的水平.實驗結(jié)果表明,筆者提出的算法不僅在總功耗和總線長上接近或優(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]孫強,孫興奇,馬光勝.一種高層次多電壓功耗優(yōu)化方法[J].西安電子科技大學(xué)學(xué)報,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é)報(理學(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]杜世民,夏銀水,儲著飛,等.面向軟模塊的穩(wěn)定固定邊框布圖規(guī)劃算法[J].電子與信息學(xué)報,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

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

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