电压岛驱动的多级布图规划优化算法

杜世民,夏银水,储著飞,杨润萍

(1.宁波大学信息科学与工程学院,浙江宁波 315211；2.宁波大学科学技术学院,浙江宁波 315212)

电压岛驱动的多级布图规划优化算法

杜世民1,2,夏银水1,储著飞1,杨润萍2

(1.宁波大学信息科学与工程学院,浙江宁波 315211；2.宁波大学科学技术学院,浙江宁波 315212)

针对多电压布图算法速度较慢、空白面积较高这一问题,提出了一种电压岛驱动的多级布图规划优化方法.首先,以功耗为优化目标,应用线性整数规划分配模块电压,将相同电压的模块划分至同一电压岛;其次,提出一种基于枚举和形状曲线相加的快速方法对所得各电压岛进行布图;最后,构建一个线性规划模型来求解通过交换布图解中模块位置来减少线长的问题,对线长做进一步优化.实验结果表明,和已有方法相比,该方法在算法速度和芯片空白面积率方面有较明显优势.

低功耗;布图规划;多电压;电压岛;多级优化

功耗是当前片上系统（System-on-a-Chip,SoC)设计所面临的一个关键挑战,基于多供电电压（Multiple Supply Voltage,MSV)的设计方法被认为是解决SoC功耗问题最为有效的方法之一[1-3].在MSV设计中,为减少电源网络的布线资源的需求及便于电平转换器（Level Shifters,LS)的布置,需将相同电压的模块聚集在一起,形成电压岛（Voltage Islands,VI),这使传统的物理设计流程变得更加复杂[1-2].

目前,针对MSV设计的研究主要集中在芯片物理设计的布图[1-2,4-7]和后布图阶段[8-10].文献[8]提出了一种分散度函数（Fragmentation Cost)来度量电源网络的复杂度,采用0-1整数线性规划给物理上相邻的模块分配相同的电压,生成电压岛以减少功耗,并降低电源网络的分散度.文献[9]改进了文献[8]的电源网络复杂度模型,提出了一种基于遗传算法的多电压分配算法.然而,上述两种方法均无法生成连续的电压岛,这会使电源布线网络十分复杂.文献[4]将电压分配嵌入到布图过程中,对每个新产生的布图解,应用动态规划分配电压,并构建电压岛,然后以所得布图的面积、总线长和功耗的加权和作为目标函数评估该布图解.由于该方法需对每个解分配1次电压,使得算法较为耗时.为避免进行多次的电压分配,文献[5]在布图之前先进行电压分配,然后分别采用基于文献[11]和文献[5]的布图算法对电压岛及其内部模块进行布图,重复该步骤直至收敛.但该方法无法快速找到较优的电压岛布图,需通过对电压岛及其内部模块进行多次布图来迭代改进面积和线长,使得算法耗时较长,并产生较大的空白面积（Dead Space,DS).

为此,在笔者先前研发的固定边框布图规划算法[12]的基础上,提出了一种电压岛驱动的多级布图规划优化方法.首先,以降低功耗为目标,应用整数线性规划（Integer Linear Programming,ILP)分配模块电压,并依据电压分配结果构建电压岛;其次,提出一种基于枚举和形状曲线相加的方法来对所得电压岛进行布图,优化电压岛布图的面积及电压岛之间的线长;然后,采用文献[12]方法对各电压岛内的模块进行固定边框的布图;最后,通过交换布图解中同一运算符下两个操作数位置对线长做进一步优化.由于文中方法避免了对电压岛及其内部模块进行多次的布图,因此,可大大提高算法的速度.其次,通过对线长进行多级的优化,则有效降低了矩形电压岛所带来的线长方面的开销.

1 问题描述及表示

1.1 问题描述

为简化电源网络的规划并降低LS布置的难度,要求将采用相同电压供电的模块聚集在一起,形成电压岛,并限定电压岛的总数.给定如下输入信息:①一个包含N个模块的集合B={b1,b2,…,bN}及芯片的n个供电电压;②每个模块bi的面积ai和高宽比范围[li,ri],1≤ i≤N;③所有模块之间的线网连接Nets={Nj,j=1,2,…,M};④每个模块bi可行的供电电压集Vi∈Vc及对应的功耗集Pi,1≤i≤N（与文献[4-5]一样,这里假定每个模块的可行电压均已满足时序要求);⑤允许的电压岛最大个数Km（1≤Km≤n).要求为每个模块分配一个合适的供电电压,并产生至多包含Km个矩形电压岛的布图,使芯片功耗降到最低,同时优化总线长和电源网络布线资源.

1.2 布图表示及计算

常用的布图表示有B*-Tree、序列对（Sequence Pair,SP)[13]、正则波兰表达式（Normalized Polish Expression,NPE)[12]等,其中,NPE具有计算简单及便于电压岛规划[4,12]等优点,故采用它表示布图解. NPE的一般形式可表示为

其中,1～N分别表示N个模块对应的序号;“*”和“+”表示模块之间的运算符,“*”表示两个模块水平（或横向)组合,“+”表示两个模块垂直（或纵向)组合.由于所给定模块尺寸在一定范围内可变,同一布图解（NPE)对应多种可能的布图实现.应用形状曲线相加算法[12]可计算出每个NPE所有的布图实现.图1（a)和（b)分别给出了两个模块b1和b2进行“*”和“+”运算时形状曲线相加的示意图.图1中,曲线A1-A2和B1-B2分别为b1和b2的形状曲线,C1-C2-C3为它们运算后所生成组合模块的形状曲线.

图1 形状曲线相加示意图

2 文中提出的算法

文中约束相同电压模块放置在同一矩形电压岛内,这样虽可大大简化电源网络的规划,但会带来线长增加的问题.为能有效控制线长的增加、加快算法的速度和降低芯片的空白面积率,文中提出了一种如图2（a)所示的电压岛驱动的布图算法流程,其操作步骤如下:

图2 所提出的算法及其图形化说明

Step 1 以降低功耗为目标,采用ILP来分配模块的供电电压,并依据所得的电压分配结果,将相同电压的模块划分到同一电压岛,以降低电源布线网络的复杂度,并获得功耗最优的电压分配方案.

Step 2 将所得各电压岛视为软模块,应用枚举和形状曲线相加方法对各电压岛进行布图,使所得布图的面积和线长最优.

Step 3 根据Step 2所得的电压岛尺寸,采用文献[12]所提出方法对电压岛内所包含模块进行固定边框的布图,确定岛内每个模块在相应电压岛的位置和尺寸,并优化它们之间的线长.

Step 4 通过交换同一运算符下的电压岛或模块的上下/左右位置,对线长做进一步优化.在此步骤中,可将这一问题构建为一个线性规划（Linear Programming,LP)模型,通过求解该模型来获得线长最优的模块位置.

上述流程中,采用基于枚举和形状曲线相加的方法来获得电压岛布图,可快速获得面积和线长最优的电压岛布图,避免了文献[5]对电压岛及其内部模块进行多次的布图,因此,可有效提高算法速度和降低芯片的空白面积率.其次,流程中对线长进行多级的优化,可将矩形电压岛所带来的线长开销控制在较低的水平.图2（b)以10个模块电路为例,给出了上述流程的一个说明.下面分别介绍流程中的Step 1、Step 2和Step 4.

2.1 基于ILP的多电压分配算法

面向功耗优化的多电压分配问题描述如下:从芯片的全部n个供电电压中选择K（K≤n)个供电电压,1＜K≤Km,并从Vs中选择其中一个分配给每个模块bi（必须是bi的可行电压之一),使所有模块的总功耗Ptotal最低.下面构建一个ILP模型来求解该问题.

式（3)即为待优化的目标.约束条件如下:

式（4)和式（5)表示仅能从bi的可行电压中选择其中一个分配给模块bi,式（6)约束供电电压总数不能超过指定的电压岛数Km.分配模块电压后,将相同电压的模块划分到同一电压岛,即可得到K个电压岛I= {I1,I2,…,IK},如图2（b)中Step1结果所示.

2.2 电压岛级的布图算法

文中约束相同电压的模块放置在同一电压岛内,因此所得电压岛数目较少.相应地,由这些电压岛构成的布图解空间也较小,故可用枚举法求出所有布图解.图3给出了电压岛数K分别取2～5时,所有可能布图解的切分树（Slicing Tree,ST)表示.图3中,“☉”表示运算符（“*”或“+”),“□”表示电压岛（I1,I2,…,IK).

图3 K取2～5时电压岛布图解的切分树表示

若用d（K)表示K个电压岛时的布图解个数,则其计算式为

其中,[K/2]表示K/2的整数.由式（7)可知,当电压岛数K较少时,相应的电压岛布图解数不多,可以采用枚举法求出所有的布图解.但随着K的增加,布图解数将增加很快.因此,枚举法适用于电压岛数较少的场合（如K≤6).

由于各电压岛均由若干软模块构成,在对它们进行布图时,亦可将它们视作软模块.于是,按图3切分树产生一个布图解Si后,应用形状曲线相加算法计算出Si的形状曲线Γi,再在Γi上找出Si最优的布图实现Fi;然后,计算出Fi的目标函数值,重复此过程,直至计算完所有布图解;最后,保留此过程中的目标函数最优的布图解SBest及相应的布图实现FBest.

对每个所得的布图解Si,将其形状曲线上DS最小的顶点作为Si的最优实现Fi,并采用

作为目标函数（用C（Fi)表示)来评估Fi,以优化所得布图的面积及各电压岛之间的线长.其中,α为加权系数,A为所得布图的面积,W为各电压岛之间的线长.由于此阶段电压岛内模块的具体位置未定,计算W时假定岛内模块的端口（pins)位置均位于该电压岛的几何中心.

2.3 基于LP的线长优化算法

对NPE或切分树表示的可切分布图,交换同一运算符下两个操作数的位置,并不会改变布图的面积,却可能使线长得到改善.已有文献一般通过对切分树自上而下或自下而上的交换运算符下的两个操作数来减少线长[14],但这种方法不能保证找到线长最优的模块位置.因此,文中提出了一个LP模型来描述该问题,通过求解该模型来获得线长最优的模块位置.

对布图解中的每个运算符pi（i=1,2,…,N-1),定义一个与其相关的三元组（pi,si,qi),其中,si为pi所生成的超模块;qi表示pi下的左、右操作数（分别用li和ri表示)是否发生交换,若发生交换,qi=1;否则,qi=0.设si的左下角坐标为x（si)和y（si),则li和ri的坐标x（li)、y（li)和x（ri)、y（ri)分别表示如下:

（1)当pi为“*”时,有

其中,w（li)表示左操作li的宽度;w（ri)表示右操作数ri的高度.

（2)当pi为“+”时,有

其中,h（li)表示左操作数li的宽度;h（ri)表示右操作数ri的高度.

利用式（9)和式（10),对布图解对应的切分树进行一次后序遍历,即可将每个模块bi及超模块si的坐标表示为N-1个二进制变量qi的线性函数.

下面导出待优化目标线长的表达式.设Nj表示线网中第j个线网（net),它连接电路中的zj个模块,（Lxj,Lyj)和（Rxj,Ryj)分别为Nj的左下角和右上角坐标,设所有模块的pins均位于模块中心,线长采用半周长法（Half Perimeter Wire Length,HPWL)估算,对Nj中的任意模块bjk,k=1,…,zj,则有

于是,布图的总线长为

其中,λj为Nj的权值.式（12)即为待优化的目标函数,约束条件为式（9)～（11).求解该模型,即可获得线长最优的模块位置.

3 实验结果与分析

文中算法已用C++编程实现,并在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]相同.目标函数式（7)中的权重α=0.5.2.1节和2.3节的模型采用Gurobi[15]求解.

表1列出了文中方法与文献[4-5]在总功耗、功耗节省率、空白面积率、线长和运行时间方面的结果比较.表1中K为电压数,由于不同电路达到最低功耗所需的电压数不同,如n100需要5个电压达到最低功耗,而n300仅需3个电压,故不同电路K的取值范围不同.表1中“归一化”行为其他算法对文中算法所得实验结果的比值.由表1可见,与文献[4]相比,文中算法可减少14.7%的总功耗和12.2%的线长,平均空白面积率从2.10%减少到0.16%,且在算法速度上加快了16.2倍.这是因为文献[4]在模拟退火算法（Simulation Annealing,SA)中同时优化功耗、线长和面积等多个指标,很难在较短时间内找到一个各目标都较优的解;其次,它对每个新产生布图解应用动态规划分配1次电压,使得算法十分耗时.与文献[5]相比,文中算法仅在线长上增加了5.2%,但在空白面积率和算法速度上有明显优势,且所有电路实现了低于1%的空白面积率.这是因为文中算法避免了文献[5]对电压岛及其内部模块进行多次布图的缺点,因而提高了算法速度.此外,由表1可以看出,当电压岛数目K增加时,算法时间并未随之增加.这是由于当K增加时,每个电压岛包含的模块数减少,对岛内模块布图所需时间亦随之减少.图4（a)和（b)分别给出了n100的4个电压岛和n200的5个电压岛时的布图结果（图中,纵坐标h为高度,横坐标w为宽度).由图4可见,所有相同电压的模块放置在一起形成矩形电压岛,并且产生了极低的空白面积,验证了文中算法的有效性.

图4 文中算法产生的多电压布图结果

表1 文中算法与与文献[4-5]算法的实验结果比较

4 结 论

笔者提出了一种基于多级优化的方法来解决电压岛驱动的布图规划问题.首先构建一个ILP模型来分配模块电压,将芯片功耗降至最低;然后,提出一种基于枚举和形状曲线相加的方法来完成电压岛的布图,避免了对电压岛本身及其内部模块多次的布图规划,加快了算法速度并减少了芯片空白面积率.为解决矩形电压岛带来的线长增加问题,在流程中对线长进行了多级的优化,可将线长开销控制在较低的水平.实验结果表明,笔者提出的算法不仅在总功耗和总线长上接近或优于已有算法,且可明显提高算法速度,并降低芯片的空白面积率.

[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]孙强,孙兴奇,马光胜.一种高层次多电压功耗优化方法[J].西安电子科技大学学报,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].浙江大学学报(理学版),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]杜世民,夏银水,储著飞,等.面向软模块的稳定固定边框布图规划算法[J].电子与信息学报,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

国家自然科学基金重点资助项目（61131001);“十二五”浙江省高校重点学科-计算机应用技术资助项目（20121114);宁波市自然科学基金资助项目（2013A610003);浙江省教育厅科研资助项目（Y201016754)

杜世民（1976-),男,讲师,宁波大学博士研究生,E-mail:dushimin@nbu.edu.cn.