面向软模块的稳定固定边框布图规划算法

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



面向软模块的稳定固定边框布图规划算法

杜世民*①②夏银水①储著飞①黄 诚①杨润萍②

①(宁波大学信息科学与工程学院 宁波 315211)②(宁波大学科学技术学院 宁波 315212)

该文提出一种稳定的面向软模块的固定边框布图规划算法。该算法基于正则波兰表达式(Normalized Polish Expression, NPE)表示，提出一种基于形状曲线相加和插值技术的计算NPE最优布图的方法，并运用模拟退火(Simulation Annealing, SA)算法搜索最优解。为了求得满足固定边框的布图解，提出一种基于删除后插入(Insertion After Delete, IAD)算子的后布图优化方法。对8个GSRC和MCNC电路的实验结果表明，所提出算法在1%空白面积率的边框约束下的布图成功率接近100%，在总线长上较已有文献有较大改进，且在求解速度上较同类基于SA的算法有较大优势。

布图规划；固定边框；后布图优化；删除后插入算子；形状曲线相加

1 引言

为此，本文提出一种有效的后布图优化方法。首先对正则波兰表达式(Normalized Polish Expression, NPE)[14]表示的布图解，应用形状曲线相加算法和插值技术来计算其最优的布图实现。其次，运用SA算法来求取以总线长和固定边框约束为目标的布图近优解。然后将SA所得解作为初始解，提出了一种基于删除后插入(Insertion After Delete, IAD)算子的后布图优化方法来获得满足固定边框的布图解，提高了布图算法的成功率。最后，通过交换同一运算符下的操作数位置来进一步降低总线长。

2 问题描述及有关表示

2.1 问题描述

面向软模块的FOF问题的输入包括：

要求确定每个模块m的尺寸(w, h)及其在芯片中的坐标(x,y)，使这些模块互不重叠地放置在指定的固定边框内，同时优化芯片的面积和总线长。

由上述定义可知，固定边框约束下的合法布图须满足：

式(1)中和分别为所得布图的宽度和高度；W和H为固定边框的宽度和高度，可由式(2)计算：

其中为中所有模块的总面积。若所得布图不能同时满足式(1)中的两个条件，则为非法布图。

2.2 布图表示

迄今已提出多种有效的布图表示方法，如B*-tree[15], SP[16]，约束图[17]，SKB[7], NPE[2,5,14]等，其中NPE表示具有计算简单和便于处理软模块形状上的灵活性等优点[2,5]，故采用它表示布图解，其一般形式为

(3)

式(3)中，1~分别表示个模块，也称操作数(operand),“*”和“+”表示模块之间的运算符(operator)：“*”表示两个模块横向或水平组合，“+”表示两个模块纵向或垂直组合。

3 NPE的布图计算

由于所给定模块的尺寸可变，一个NPE对应多种可能的布图实现[5,17]。本文先采用形状曲线来表示每个软模块，然后提出一种形状曲线相加算法和插值方法来获得每个NPE的最优布图。

3.1 软模块的形状曲线

由FOF问题的输入可知，任意模块m的高度w和宽度h满足：

式(4)可表示为图1中的一段曲线，称之为m的形状曲线，端点和称为该形状曲线的顶点。

3.2 形状曲线相加算法

由于每个软模块都可用形状曲线来描述，因此，可将它们之间的运算转化为相应形状曲线之间的运算。当两个模块作“*”或“+”运算时，分别对应于各自的形状曲线进行横向或纵向相加。

设1和2为两个软模块，其形状曲线分别如图2(a)中1-2和1-2所示。3为它们作“*”运算后得到的组合模块，其高度3和宽度3可由下式计算：

图2 形状曲线相加示意图

由此可知，当两个模块进行“*”运算时，所得组合模块的面积或保持不变或是其高度的线性函数。因此，在对软模块的形状曲线进行“*”相加时，只需简单地在它们的顶点处进行相应的横向相加就可以了。当两个模块作“+”运算时，其形状曲线之间的相加可以用类似的方法来实现，如图2(b)所示。

由于每次计算新解的布图时都会涉及到较多两个软模块之间的“*”或“+”运算，为提高算法速度，可预先计算出所有软模块两两组合运算的结果。这样每次计算新解时，就可节省这部分运算所需的时间。

3.3 形状曲线的插值

应用上述方法计算NPE的形状曲线，在计算过程中仅记录了形状曲线上的顶点信息，因此可能遇到相邻两顶点均不满足但其内部一些点却已满足固定边框约束的情况。例如在图3中，顶点1(1,1)和2(2,2)均在边框外，但它们之间的某些点却已落在边框内。这时，需要对形状曲线以一定的步长进行插值。设图3中顶点1和2处的面积分别为1和2，插值步长为，则1-2之间任一点A的面积s和坐标(x,y)可计算如下：

图3 对NPE形状曲线进行插值

4 本文提出的算法

4.1 算法流程

本文提出了一种改进的固定边框布图规划的算法流程。首先以固定边框约束和总线长为目标，利用SA算法对解空间进行搜索。然后判断SA求得的布图解是否满足固定边框，如果不满足，提出了一种新的IAD算子对该解进行后布图优化，将其转变为满足固定边框的解。最后通过交换NPE中同一运算符下的两个操作数的左右/上下次序，对总线长作进一步的优化，整个算法的流程如图4所示。

在上述流程中，由于在SA算法后新增了一个后布图优化步骤，只要SA算法能搜索到一个接近于固定边框的解，就可以通过该步骤将其修正为合法解，从而放宽了约束条件，因此提高整个算法的布图成功率。

4.2 基于IAD算子的后布图优化方法

(1)一个较小的单一模块和一个较大的模块进行组合运算；

(2)一个较小的组合模块和一个较大的模块进行组合运算。

图4 本文算法流程

在上述两种情况下，由于参与运算的两个操作数尺寸相差较大，组合后产生较大的空白面积，从而导致所得布图超出指定的边框，因此称它们为非优组合。图5(a)和图6(a)分别给出了这2类非优组合的示例（图中的虚线框表示固定边框）。

在图5(a)中，所得布图的宽度虽已满足约束条件，但在高度上违反了约束。其原因是在该布图解中存在一对非优的组合运算，即模块7和由子表达式“8 6 + 9 5 1 * 2 + * 4 3 * + *”表示的组合模块之间的组合运算。如果能设法消除布图解中存在的类似的非优组合，就有可能将一个接近于满足固定边框的近似解转化为合法的布图解。

从图5(a)不难发现，若将模块7从该布图中删除，然后将其重新插入到图中的合适位置，就有可能得到一个合法的布图，如图5(b)所示。这是因为：(1)模块7删除后所得到的较大空白区域给其它模块的尺寸调整提供了空间；(2)由于模块7面积较小，将它重新插入后不至于对原有已接近于满足边框约束的布图产生过大的改变。因此，通过这样一种先删除后插入操作，可以有效地消除布图解中的非优组合。本文提出的后优化策略正是基于这一思想，同时将这种新的用于后布图优化的操作称为IAD算子。

应用IAD算子来消除SA算法解中的一对非优组合，需经过以下3个步骤：

步骤1 找出原布图解(NPE)中存在的非优组合；

步骤2 删除非优组合中面积较小的模块(设为m)；

步骤3 将删除后模块m重新插入到原布图解的合适位置。

在上述步骤中，由于没有直观的方法来确定m在中最合适的插入位置，因此采用了枚举法，即通过将m和中所有模块分别进行“*”和“+”组合运算，然后比较每种组合下的目标函数(此时以满足固定边框为目标)来确定m在中最佳的插入位置。利用该方法消除一对非优组合最多需进行次插入操作。由于经过SA算法优化后，中非优组合的数目并不多，因此后布图优化所需的计算量和前面的SA算法相比基本可以忽略。

图5 非优布图和优化后布图

在图6(a)中，子表达式“6 8 +”和“9 5 7 * 2 + * 4 3 1 + * +”之间的横向组合属于第2类非优组合。首先将子表达式“6 8 +”所表示的组合模块从当前NPE中删除，然后将其拆成两个独立的模块：6和8，再依次将这两个模块插入到余下布图解(NPE)中的合适位置，最终得到了一个合法的布图解，如图6(c)。

综上，可得到所提出的基于IAD算子的后布图优化算法的流程，如流程1所示。

流程1：基于IAD算子的后布图优化算法流程

图6 方式2操作示意图

(4)在当前布图解中删除m及其对应的运算符；

(5)将m依次和中所有模块m(≠m)分别进行“*”和“+”组合运算，并记录下该过程中的最优解；

(6)判断m是否为组合模块，若是，转第(7)步，否则转第(9)步；

(7)将m拆分成一个个单一模块，然后按面积大小顺序逐一插入到中，记录下该过程中最优解；

(9)1，判断是否等于0？若是，转下一步，否则，将赋给，转第(3)步；

流程中的A是一个经验参数。当它取值过小时，后布图优化次数增加，会导致总线长增加；而当它取值太大时，会忽略掉一些非优组合，优化后不易满足固定边框约束。经多次实验测试，A取/500较为合适。

5 实验结果

为进一步验证本文算法的有效性，本文在1%空白面积约束下，让高宽比以0.5的步长从1增加到6对上述5个电路进行了实验。表1给出了所得的布图成功率SR(%)及空白面积率WS(%)结果。从表1可见，所有电路均获得了99%以上的布图成功率(仅ami33和ami49在部分下有1%的失败率)，且平均空白面积率0.04%。特别是在高宽比达到5:1或6:1时，除ami33外所有电路仍可达100%的成功率，表明本文算法对不同高宽比的固定边框约束具有良好的稳定性。

表3列出了本文算法和A-FP[8], SAFFOA[6], SKB[7]等方法在不同下所得到的总线长的比较。由表可见，当芯片高宽比分别为2:1, 3:1和4:1时，本文所提出的算法较A-FP可分别减少38.0%, 36.5%和35.3%的总线长；与SAFFOA相比，本文所提出算法在总线长上分别减少了17.9%, 13.7%和14.8%。与SKB相比，本文算法在总线长上分别减少了5.5%, 4.1%和5.4%。可见，本文所提出算法通过对总线长的二次优化，使其在不同的高宽比下都可得到较低的总线长。图8(a)-图8(d)分别给出了n300在时的布图结果。

表1不同高宽比下固定边框的布图成功率及空白面积率结果(%)

电路高宽比平均 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分别与文献[8,9,3,6,7]总线长及运行时间(s)的比较

电路A-FP[8]PATOMA[9]Parquet 4.0[3]SAFFOA[6]SKB [7]本文 HPWL时间HPWL时间HPWL时间HPWL时间HPWL时间HPWL时间 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

注：表中“-”表示原文未给出结果，下同。

表3 本文分别与文献[6,7,8]在不同高宽比下总线长的比较

6 结论

本文提出了一种稳定的基于IAD算子的固定边框布图规划算法。和传统方法相比，该算法新增了一个后布图优化步骤，放宽了SA优化时对解的苛刻的边框约束，从而提高算法的收敛速度。本文提出了一种新的IAD算子对SA所得的布图解进行后优化，从而提高了布图成功率。同时在算法中对总线长进行了二次优化。实验结果表明，本文算法在宽范围的高宽比下可实现接近100%的布图成功率和接近于零的空白面积率，且和已有文献相比，可获得总线长和求解速度都较优的布图结果。

[1] 徐宁, 洪先龙, 董社勤. BBL布局算法研究[J]. 计算机辅助设计与图形学学报, 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] 杜世民, 夏银水, 罗佐. 基于切分结构的快速布图规划方法[J]. 计算机应用研究, 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年生，博士生，讲师，研究方向为集成电路设计自动化.

夏银水： 男，1963年生，研究员，博士生导师，研究方向为集成电路综合和优化、高信息密度集成电路.

储著飞： 男，1986年生，博士生，研究方向为集成电路设计自动化.

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改回