正态分布评价方式的布局拥挤度优化方法

虞 健，周洋洋，王新晨

（无锡中微亿芯有限公司，江苏无锡 214072）

1 引言

布局是FPGA配套设计工具中非常重要的模块，布局质量的好坏直接影响着整个用户设计的实现。布局模式一般分为非时序驱动模式布局和时序驱动模式布局两种。在传统做法中，非时序驱动模式布局一般以线长作为优化目标，时序驱动模式布局一般以时序和线长两个因素作为优化目标。在实际应用设计中由于一般用户设计都带有时序约束，因此主要采用时序驱动模式布局。然而由于实际芯片上逻辑资源、模块间互联线资源等数量有限，理论上以线长和时序的优化结果不能完全反映最终的布局结果质量。如在互联线利用率比较高的区域，会存在模块间互联线的竞争关系，从而影响到后续布线流程的效率，最终影响用户设计质量[1]。为使布局算法能够更准确地反映芯片实际的资源竞争关系，从而提高布局质量，本文提出了一种基于正态分布评价方式的布局拥挤度优化方法，将布线拥挤度因素提前考虑到布局中。

2 基于模拟退火算法的时序驱动模式布局算法

模拟退火算法来源于固体退火原理，将固体加温至充分高温，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp[-ΔE/(kT)]，其中E为温度T时的内能，ΔE为其改变量，k为玻尔兹曼常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

模拟退火算法可以分解为解空间、目标函数和初始解3部分。

模拟退火的基本思想如下。

(1)初始化：初始温度T0(充分大)，初始解状态S（是算法迭代的起点），每个T值的迭代次数L；

(2)对k=1,2,...,L做第3至第6步；

(3)产生新解S′；

(4)计算增量ΔC=C(S′)-C(S)，其中C(S)为评价函数；

(5)若ΔC<0则接受S′作为新的当前解，否则以概率exp(-ΔC/T)接受S′作为新的当前解；

(6)如果满足终止条件则输出当前解作为最优解，结束程序，终止条件通常取为连续若干个新解都没有被接受时终止算法；

(7)T逐渐减少，并不断趋近于0，每次T减少后转第2步，进行下一温度的迭代。

模拟退火算法是布局实现的经典算法之一，著名的VTR系统中布局模块就是使用的模拟退火算法[2]。

2.1 代价函数的构建

传统模拟退火布局算法都以线长和时序作为优化目标，将这两个因素通过构建代价函数输入到算法中。在退火过程中，通过分析代价函数的变化来确定接受或者不接受节点移动。

2.1.1线长代价函数构建

在模拟退火算法中，一个用户设计网表可以描述为一张超图G=（V，E），其中V代表网表中的所有基本逻辑单元，E代表网表中的所有连接线。在以线长为优化目标时，一般都以线网半周长来构建代价函数[3]。图1为半周长示意图，图中有网表中一条连接线的连接关系，其中点A为源头端，点B、C、D、E、F为负载端。那么对于该条连接线的线长评价计算为连接线上所有节点最大坐标范围的半周长，如图1中红线所示，即maxi∈e xi-minj∈e xj+maxi∈e yi-minj∈e yj，其中e代表整个网表连接线集合E中的一条连接线，xi，xj代表节点的x坐标，yi，yj代表节点y坐标。即网表中节点所占x方向的最大长度和y方向最大长度之和[6]。

图1 半周长示意图

对于整个网表，以线网半周长来构建代价函数为所有连接线的半周长之和，即H=∑e∈E(maxi∈e ximinj∈e xj+maxi∈e yi-minj∈eyj)，其中H代表线网半周长。

2.1.2时序代价函数构建

在时序模式中，通过时序分析引擎可以分析出每一个连接点的建立保持余量。当余量值为正时表示该连接点时序合法，负值时表示不合法，余量值为最小的节点代表当前设计中时序最差的情况[4]。每一个负载节点都有一个延时值，表示从源节点到当前负载点的线的延时。图2为延时示意图，节点F上的延时值表示该虚线的信号传输延时。在构建代价函数时，以所有负载节点的延时值和当前节点余量值的权重综合考虑，即J=∑v∈V[D×(Sworst-Scurrent)/Sworst]，其中J代表时序代价函数，D代表负载点的延时值，S代表时序余量，(Sworst-Scurrent)/Sworst项代表当前节点跟设计中时序最差节点对比后所占的权重值。

图2 延时示意图

2.1.3时序目标函数与线长目标函数的归一化处理

在模拟退火算法中，需要将这两个代价函数拟合成一个最终代价函数。但是由于计算线长和时序的目标函数最终得出的代价值经常不在一个数量级上，因此在算法中需要将这两个因素的数量级拉到同一水平上。即F=H/J，得出线长代价与时序代价的比例系数，其中F代表比例因素。在后续模拟退火算法中计算时序变化时都需要乘以F。

经过归一化处理后，最终的代价函数可以归结为C=Whpw1×H+Wtiming×J×F，其中，C代表最终代价函数，Whpw1代表线长所占权重，Wtiming代表时序所占权重。在模拟退火算法中，每次节点移动都根据Cost值的变化来确定是否接受移动结果[7]。

2.2 模拟退火算法流程

模拟退火布局算法流程如图3所示，分为读入用户网表、初始布局形成初始解、基于初始解构建代价函数、产生新解判断是否接受、接受新解替换旧解、达到退出条件时退出。其核心模块主要有如下5个步骤：

图3 模拟退火算法流程

第1步是产生初始解，通过随机的方式对每个节点给定一个合法的初始位置，形成初始解，求得初始代价和决定退火初始温度。

第2步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单的变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第3步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第4步是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若ΔC<0则接受S′作为新的当前解S，否则以概率exp(-ΔC/T)接受S′作为新的当前解S。其中ΔC代表代价函数变化。

第5步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代，可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验[5,8]。

3 基于正态分布评价方式的布局拥挤度模型优化

由于线长和时序的布局模型不能完全反映芯片后续步骤布线的实际情况，当布局把绕线资源竞争比较多的模块放得比较靠近时，会大大影响布线效率，从而影响整体设计最终结果的质量。为了解决此问题，本文提出了一种正态分布式的布局拥挤度评估模型，并应用到模拟退火算法中，达到优化布局结果的效果。

3.1 基于正态分布的拥挤度评估模型建立

在算法模型中，每一个节点上的连接线都需要通过端口输入输出，而输出端口比较固定，很少出现资源竞争问题，因此本文提出以模块被连接的输入端口数量来代表当前模块所需要占用连接线资源的数量。图4为单个节点拥挤度计算示意图，模块有6个输入端口和3个输出端口被连接，那么在模块拥挤度计算时，其拥挤度代价Ccost=6。

图4 单个节点拥挤度计算示意图

在实际布线过程中，拥挤度并不只看当前节点的资源占用数量。布线资源竞争如图5所示，对中心点进行布线时不仅要考虑到当前节点资源竞争问题，还需要考虑到周围节点资源的使用情况。当一根线进入该区域时，如果被周围其他逻辑单元的某一传输信号A使用了，那么当前逻辑单元非传输信号A的走线就不能再使用这条逻辑资源线，从而会产生资源竞争。

图5 布线资源竞争

芯片逻辑资源情形如图6所示，图中有9条布线资源线，其中线1、2有3个输出口，线3、4、5有2个输出口，线6、7、8、9有1个输出口。那么对于D点，其自身在绕线时互相有竞争关系的线有3条，为线2、3、9。与之距离为1的C点跟其有竞争关系的连接线有2条为线2、3，与之距离为2的B点跟其有竞争关系的连接线有1条为线2，与之距离为3的A点跟其有竞争关系的连接线有0条。针对此情况，可以认为距离当前节点越近的其他节点与当前节点的竞争关系越激烈。距离越远绕线资源竞争关系越小，此特征符合正态分布关系。因此本文提出了基于正态分布模型来评估周围节点对当前节点影响的方法，从而形成正态分布函数其中x代表与当前节点的坐标偏离，假设当前节点对拥挤度影响因素为1，则f(0)=1。假设基于当前节点为中心的正态分布，则μ=0，从而可以求出样本方差σ=1.13。根据正态分布公式，可以得出每个节点距离当前节点的位置来求出相应的影响因子，从而得出当前节点的拥挤度代价为Ci=∑v∈V[Ccost×f(x)]，将每个节点的拥挤度代价相加，得出整个网表的拥挤度代价其中n代表网表中节点数量。另外正态分布的因子μ和σ可以根据各个器件资源竞争情况进行调整，得出合适的值。

图6 芯片布线资源

3.2 模拟退火算法中拥挤度模型应用

与传统模拟退火算法不同，基于拥挤度模型的模拟退火算法需要在原有的代价函数上增加一个拥挤度代价因子，即代价函数变为：C=Whpw1×H+Wtiming×T×Ftiming+Wcongestion×Ccongestion×Fcongestion，其中Wcongestion代表拥挤度因素所占权重，Fcongestion是通过2.1.3节方法对拥挤度代价归一化处理后得出的比例因子。

将新的代价函数替换原来模拟退火算法中的代价函数，进行退火求解，从而可以得出基于拥挤度的布局结果。

4 试验结果

一般评价布局结果的质量有两个方面：第一是布线运行时间，布线时间越短，布局质量越好；第二是布线后最差路径的时序余量（Slack），余量越大，质量越好。本文所提出的基于正态分布拥挤度模型的模拟退火布局算法与传统的基于时序模拟退火布局算法进行了试验对比。将布局结果分别用相同的布线器进行布线，通过对比布线的运行时间和最差时序建立余量两方面来评价最终布局结果的好坏。测试用例选用了客户实际用例中规模比较大的一些，其中测试用例X1、X2、X4、with_dsp包含slice、dsp、bram、iob逻辑资源，fixpt、syn测试用例不含有bram资源，no_dsp测试用 例 不 含 有dsp资 源，aes、ecg、noc、mac、smith、arm9_24、arm9_22不含有dsp和bram资源，具体每个测试用例逻辑资源占用数量如表1所示。

表1 试验结果对比

如表中布线运行时间列所示，基于正态分布拥挤度模型的模拟退火布局算法得出的布局结果相较于传统的基于时序模拟退火布局算法得出的布局结果，相同布线器布线时间平均下降23.32%。

如表中最差时序余量列所示，基于正态分布拥挤度模型的模拟退火布局算法得出的布局结果相较于传统的基于时序模拟退火布局算法得出的布局结果，相同布线器得出的平均最差时序建立余量波动较小，影响不大。

5 结论

本文提出了一种基于正态分布拥挤度模型的模拟退火布局算法，通过试验对比，得出本文所提出的方法是有效可行的，该方法可以在对设计时序影响不大的情况下大大降低布线时间，从而证明可以化简布线时绕线资源的竞争关系，达到优化整个用户设计的目的。本文所提出的方法也有一定局限性：用户设计比较简单时，拥挤度因素相较于线长和时序因素比较次要，因此不一定能达到优化布局结果的作用；代价函数参数的调整也需要大量的试验去进行摸索，包括正态分布函数中和值的确定，后续将对该方面进行大量测试用例的试验分析；试验结果中有些情况利用拥挤度模型布局后布线运行时间增加，分析原因为布局结果后网表中Slack值接近的节点数量增加，导致布线时很多节点绕线优先度区分不开，增加了布线时间，后续将根据这方面缺陷进行改进。