Quadratic布局算法力模型的建立和一种均匀展开的方法

虞健，董志丹，惠锋，王新晨，胡凯

（1.无锡中微亿芯有限公司，江苏无锡214072；2.中国电子科技集团公司第五十八研究所，江苏无锡214072）

Quadratic布局算法力模型的建立和一种均匀展开的方法

虞健1，董志丹1，惠锋1，王新晨2，胡凯2

（1.无锡中微亿芯有限公司，江苏无锡214072；2.中国电子科技集团公司第五十八研究所，江苏无锡214072）

布局是FPGA软件设计中一个基本而且非常重要的环节。随着FPGA规模的不断扩大，在大规模、复杂的设计约束条件下，花费较少时间获得高质量的相关逻辑单元物理位置是布局算法的关键问题。在二次线性规划布局算法的基础上，以线长为优化目标，介绍了一种力模型的建立理论和在力模型基础上的一种均匀展开方法。

布局；力模型；展开

1 引言

布局是指在既定的所有约束条件下，以一种或者几种参数（线长、时序、功耗、拥挤度）组合作为优化目标，确定所有布局网表中逻辑单元的物理位置。一般可以把布局划分为全局布局和详细布局两个部分。全局布局主要从整个全局网表的角度出发，一般可以大体确定逻辑单元位置。全局布局的结果一般可以允许存在一定的不合法条件。详细布局主要做布局结果合法化和局部位置调整的工作。目前应用比较广泛的全局布局算法有划分算法、模拟退火算法、二次线性规划算法等，这几种算法各有优缺点，很多情况下需要几类算法相互配合形成最终的全局布局结果。本文主要以二次线性规划算法为基础，以线长作为优化目标参数，介绍全局布局算法中一种力模型的建立和在力模型下的一种均匀展开方式[2，4]。

2 Quadratic算法模型的建立

在布局网表中，可以把所有的布局逻辑单元看作节点，把所有节点之间的信号关系建立成点到点的边的关系。如图1所示，网表中有A、B、C、D、E 5个节点，信号1从节点A输出，到达节点B、C、D、E上的4个目的端口。在建模时将信号1转换成图中边1、边2、边3、边4，形成点→边→点模型。这样，以图1为例，以线长作为约束条件布局的话，目标信号1从源端A到目的端B、C、D、E的线长最短可以等效看作为目标边1、边2、边3、边4的边长总和最短。那么对整个网表而言，布局优化目标就是使得网表中所有边的长度总和最小[3，5]。

图1 网表转换图

图2 边长等效图

对目标函数分别在xc、xd上求偏导数可得：

图3 布局网表示意图

还是以图3所示网表为例，求解可知节点C的X坐标为16，D的X坐标为34，那么以C节点来看，固定点A、B对C在X方向上可以认为产生一个向左的拉力。可动点D对C在X方向上可以认为产生一个向右的拉力，大小为：fright=Wcd(xd-xc)=1×(34-16)=18。由此可知X方向上，点C处于一个力平衡状态，同理可以得出D也处于一个力平衡状态。那么以力模型建立网表结构以后，在布局改变可动点位置时，只需要根据力平衡模型，对目标节点加上一个固定的力就可以达到目的。

3 根据力模型的一种均匀展开方法

由于我们根据二次函数偏导数求极值的方法求得的逻辑单元位置会存在很大程度上的单元重叠，而布局合法的前提条件是逻辑单元之间不能存在重叠。因此我们需要对求解出来的结果进行展开，使得重叠不断降低。

图4 初始节点分布图

图5 均匀展开方法示意图

其中min代表整行方格的左边边界的x坐标，max代表整行方格的右边边界x坐标，L1代表切割线左边的方格长度总和，Lr代表切割线右边的方格长度总和，xori代表节点原来的x坐标值，xnew代表需要求的节点新坐标。通过上述等式，可以求得节点的目标位置，如果以向右方向代表正方向，那么可以得出节点需要向右移动的距离xnew-xori。

图6 加力模型示意图

4 结果与讨论

通过在实际应用中使用上文论述的均匀展开方法，可以在较好地保持模块间相对关系的基础上均匀快速地对布局重叠进行展开。图7、图8、图9、图10、图11、图12、图13、图14所示为一个实际设计用例在布局流程中迭代展开过程中的布局效果，当迭代300次以后，重叠部分已经完全展开。

图7 初始解效果图

图8 第30次迭代展开效果图

图9 第50次迭代展开效果图

图10 第80次迭代展开效果图

图11 第100次迭代展开效果图

图12 第150次迭代展开效果图

图13 第200次迭代展开效果图

图14 第300次迭代展开效果图

通过实际应用测试，本文所论述的Quadratic算法结合均匀展开方式作为布局算法流程，也取得了比较好的结果。如表1所示，在测试设备xc5vlx330ff1760的条件下，以线长为布局优化目标，测试下列17个用例，上文论述的Quadratic结合均匀展开布局方法比传统模拟退火布局方法平均线长可以降低6.72%。

表1 布局测试对比表

5 结论

本文主要论述了Quadratic算法力模型的建立和基于该模型的一种均匀展开的方法。该模型和方法应用于自主FPGA设计工具软件的布局模块中。在软件的实际测试应用中，该模型和方法可以快速有效地得到较优的布局结果，从而可以为后续软件步骤提供较好的基础。

[1]虞健.FPGA布局算法应用研究[D].武汉：武汉理工大学，2011.

[2]蒋中华.超大规模集成电路布图/布局算法及热模型研究[D].武汉：武汉理工大学，2008.

[3]杨维嘉.布局问题求解算法与策略的研究[D].天津：天津大学，2005.

[4]王凯.FPGA布局算法研究与设计[D].武汉：武汉理工大学，2010.

[5]Myung Chul Kim,Dong Jin Lee,Igor L Markov.SimPL:An Effective Placement Algorithm[D].University of Michigan, 2005.

[6]黄钢.VLSI布图规划和布局算法[D].北京：清华大学，1999.

Force Mode Setup and a Balance Expansion Method Based on Quadratic

YU Jian1,DONG Zhidan1,HUI Feng1,WANG Xinchen2,HU Kai2
（1.East Technologies,Inc.,Wuxi 214072,China; 2.China Electronics Technology Group Corporation No.58 Research Institute,Wuxi 214072,China）

Placement is a key step in designing FPGA software.As the logic resources surge,obtaining a good placement result under the complicated design constraints is becoming significant.Based on quadratic algorithm,the article regards HPWL as the optimize target and introduces a force module setup and a force-module-based expansion method.

placement;force module;expansion

TN402

A

1681-1070（2017）07-0031-05

虞健（1988—），男，江苏无锡人，硕士学历，软件工程师，现从事EDA软件领域工作。

2017-3-29