基于深度学习的FPGA快速布局算法

刘 伟，王伶俐，周 灏

(复旦大学 专用集成与系统电路国家重点实验室，上海 201203)

现今，现场可编程门阵列(Field Programmable Gate Array, FPGA)作为一个可重构平台得到越来越广泛的应用.为满足实际的需要，Xilinx和Intel公司最新的芯片包含近百万个逻辑单元块.随着电路规模和复杂度的提升，在FPGA的整个计算机辅助设计流程中，布局占据近49%[1]的运行时间，这直接影响到FPGA的使用效率.

FPGA布局是NP(Non-deterministic Polynomial)完全的组合优化问题[2]，对于一块给定的FPGA芯片，对打包流程之后的电路网表中的每一个逻辑单元块进行位置选择，以实现最终关键路径延时最小和线长的最优.总体来说，布局算法有3类： 第1类为启发式算法，典型的代表就是VPR(Versatile Place Route)[3]中使用的模拟退火算法，它基于交换的方式实现对线长和关键路径的优化.虽然这一类方法能够得到比较理想的布局结果，但是处理大规模电路布局时，需要非常长的运行时间；第2类是基于划分的布局算法，如PPFF[4]，它将一个大的电路布局问题分解为更多的子问题，从而降低了电路计算的复杂度，但是该算法在性能上会带来非常大的关键路径延时损失；第3类是解析法，如QPF[5]，CAPRI[6]，StarPlace[7]，这也是目前Xilinx商业计算机辅助设计软件中使用的布局算法.解析法是目前综合表现最优的算法，在接近于VPR布局结果的情况下通常能够实现布局速度3～8倍的提升.

针对基于模拟退火的VPR布局算法的优化主要分为3类.第1类是提供更精确的目标函数，如采用基于路径的时序分析模型或者引入拥挤度矩阵为每一次交换提供更高质量的结果.但是在大规模电路指数级增长的交换次数前提下，VPR布局阶段使用的半周长线网框模型和最小延时时序矩阵是相对理想的选择.第2类则是寻找更高效的策略如初始化布局、自适应退火表、交换逻辑单元的选择以及交换的目标区域选择等.模拟退火算法交换过程中随着温度的降低交换范围逐渐缩小，RBSA[8]采用线网中心而不是逻辑单元块的中心指定交换范围产生交换策略，在不损失关键路径延时的情况下运行速度提升一倍.第3类是采用并行策略对模拟退火算法进行加速，文献[9]中在小规模电路中实现64线程下运行加速提升34倍，线长损失平均为1.7%，关键路径延时损失为0.6%，但是该并行策略并没有在大规模电路中有效地实现.所以目前对于基于模拟退火的FPGA布局算法，在处理大规模电路时难以得到一个快速而且比较理想的布局结果.

深度学习[10]与传统的机器学习方法不同，在模型深度上扩展，分层地进行学习并将上层学习到的特征作为下层的输入，实现由低阶到高阶的特征提取.深度学习已经广泛应用于视觉，文本识别、机器人、人工驾驶、游戏、医疗等诸多领域.文献[11]使用机器学习算法对FPGA布局结果进行布线拥挤度的预测，相较于传统的VPR中使用的拥挤度预测方法，在近乎准确的拥挤度预测情况下实现了291倍的运行速度提升.本文基于深度学习处理FPGA布局这样的NP完全组合优化问题，实现了布局速度的极大提升.

1 模型思想

本文模型有别于基于传统的3类布局算法，由底层到顶层的方式逐步进行布局.在每一次逻辑单元块的选择和逻辑单元块位置确定的过程中，需要动态地提取当前布局阶段的状态信息，为下一次决策做准备.采用训练好的深度学习网络，将对应的状态信息作为网络输入，实现对下一个逻辑单元块的位置确定，最后使用基于交换的快速详细布局算法进行优化.状态信息的提取和网络模型的训练在模型实现中详细介绍.

2 模型实现

2.1 FPGA结构

深度学习模型的训练针对是VPR中一种通用的FPGA芯片描述k4_n4_v7_bidir.xml，芯片的核心部分由可配置逻辑块阵列(Configurable Logic Block, CLB)和全局布线资源组成.如图1所示，每个可配置逻辑单元由4个基础逻辑单元(Basic Logic Element, BLE)组成，每个BLE包含一个4输入查找表(Look-Up Table, LUT)和可配置D触发器.FPGA全局布线资源中线长为4，CLB通过连接盒与全局布线资源连接.

2.2 电路网表解析

图1 可配置逻辑块结构Fig.1 Architecture of CLB

电路网表的解析用于逻辑单元块的选择和逻辑单元块的位置确定.打包之后的电路网表中的结点不仅包括可配置逻辑块等逻辑单元块的输入输出端口的信号结点(外部结点)，也包含可配置逻辑块内部如LUT4和D触发器输出端口的信号结点(内部结点).初始化时，不考虑结点之间的延时，对电路网表中的所有结点进行拓扑排序，对所有结点进行遍历之后，可以确定决定每一个结点最长路径的输入结点.在对网表进行解析的过程中保留确定所有结点最长路径的路径，超图的连接由此解析为所有结点组成的森林，每个结点都在森林中的一棵树中.布局过程中，采用VPR中的布局阶段延时模型对已布局电路的结点延时和路径延时进行分析，树中父子结点的关系由延时模型计算得到的最大延时确定，所以在周期性的更新过程中，动态的布局过程也伴随电路网表解析森林中父子结点连接关系的变化.

图2所示即是经过拓扑排序之后的一个电路网表.图中实线和虚线都是网表中不同结点的连接，实线为确定该线输出端点最长路径的路径，从图中可以看出拓扑排序之后的网表形成了由3棵树组成的森林，每棵树由椭圆内的结点和实线连接组成.

在算法的动态的布局过程中，动态的网表解析过程如表1所示.首先在布局开始之前进行拓扑排序，排序之后保留确定每个网表中结点最长路径的路径，从而将电路解析为森林.随后布局的实现过程中，在每次布局单个逻辑单元块之后对当前电路中已布局的部分网表进行时序更新，如图3描述的是布局的中间过程，此时已经处理到网表中的A，B，C，D，E，G，J结点，与之前分析不同的是每条路径对应有相应延时计算值，此时结点J的最长路径延时由CJ之间的路径确定.受运行时间的影响，时序更新之后，网表的动态解析条件由第10行确定，在本文具体实现中Every_Iteration_times取值0.01，Threshold_time_update取值1.10.

图2 初始化网表解析Fig.2 Initialization of netlist parser

图3 动态网表解析Fig.3 Dynamic netlist parser

输入: 电路网表Netlist,P为网表逻辑单元块数量输出: 电路网表解析数据结构对网表Netlist中结点进行拓扑排序保留确定每个网表中结点最长路径的路径∥布局过程中动态更新网表解析过程,Last_Update用于记录上次动态更新网表解析到当前阶段布置逻辑单元块的数目∥Last_Critical_Time用于记录上次动态更新网表解析时最长路径的延时,Critical_Time为当前阶段最长路径延时For j←P to 0 do 调用训练好的深度模型进行布局 更新已布局部分网表中结点和路径延时,结点中最大延时值为Critical_Time if(Last_Update>Every_Iteration_times×P) or (Critical_Time/Last_Critical_Time)>Threshold_time_update 更新确定每个网表中结点最长路径的路径 Last_Update=0,Last_Critical_Time=Critical_Time else Last_Update=Last_Update+1 End ifEnd For

2.3 深度学习模型

训练模型的建立主要包括数据的提取、深度学习网络结构的确定、特征的选取3部分.

2.3.1 数据的提取

数据由两类电路网表产生： 一部分数据由基于PEKO[12]的最优线长电路生成器产生，该电路生成器中每个逻辑单元块的位置都是线长最优的；另一部分数据是由随机化电路生成器产生.由于VPR采用的模拟退火算法通常能够得到较好的布局结果，所以对于随机化电路网表将模拟退火算法布局得到的逻辑单元块的位置作为深度学习模型训练的理想标签.

最优线长电路是普通电路的一种特例，也是一种理想情况.根据VPR中线网框计算方法，对于有N个端点的线网，将其所连接的N个逻辑单元块限定在包含该逻辑单元块的最小的矩阵框范围内能够实现周长最小的线网框，从而得到最小线长.对于所有的线网都找到最小的线网框从而得到最优线长的布局结果[13].虽然与通常的基准电路不同，最优线长电路网表中逻辑单元块之间简单的连接，以及最优位置的确定更有利于深度学习模型的训练.PEKO算法确定的是逻辑单元块之间的外部线网，以达到线长最优.最优线长电路网表生成器在PEKO基础上产生适用于FPGA芯片描述k4_n4_v7_bidir.xml的电路网表.表2(见第690页)为最优线长电路网表生成器的伪代码，P为网表逻辑单元数量，Archclb为逻辑单元块结构.如表中所示，为产生不同的电路网表，一方面需要根据结构产生不同的电路网表参数如Inave,Outave,Dffave，Distri以及对应于每个逻辑单元块的Lutnum和Dffnum，另一方面需要在合法连接的前提下实现全局互连以及逻辑单元内部互连的随机性.随机化电路网表生成器不同之处在于： 在选择每一条线网所连接的逻辑单元块时，不是根据半周长线网框模型选择包含该线网所连接逻辑单元块的最小矩阵，而是随机性的选择任意大小和任意位置的线网框，并最终在该线网框选择确定数量的任意逻辑单元块.

表2 最优线长电路网表生成器伪代码

2.3.2 深度学习的网络结构

深度学习采用的是残差网络，实验中证明，在深度网络的训练中，残差块能够加速收敛并提高训练效果.整个网络结构由输入层、20个中间层(残差块)和输出层组成.中间层(残差块)及参数如图4所示，残差块的第一层的输入被加入到最后一层的输出中，其内部包含由批归一化和激活函数隔离的卷积层.输入层同样使用类似残差块结构，如图5所示，卷积核的大小分别为[5,5]与[1,1]，卷积层之后的输出进行相加.输出层卷积层中卷积核大小为[3,3]，输出层的大小为[100,100，1]，输出层经过softmax层后得到的是逻辑单元块位于资源阵列中各个位置的概率分布.

图4 残差块Fig.4 Residual block

图5 残差输入层Fig.5 Residual input layer

2.3.3 特征提取

布局过程中已经被选择并且确定位置的逻辑单元块称为已布逻辑单元块，被选出来并且即将由训练好的深度学习模型进行位置预测的逻辑单元块称为待布逻辑单元块，目前未被选择的逻辑单元块称为未布逻辑单元块.特征提取的思想是在动态布局过程中，统计FPGA资源阵列中每个坐标位置可供使用的逻辑单元块资源(总的逻辑单元块资源与已布逻辑单元块资源之差)和每个坐标位置附近需求的逻辑单元块资源，并根据提取的时序和线长信息对待布逻辑单元块进行位置的确定.

特征一(f1)： FPGA资源阵列.该特征记录FPGA芯片的总逻辑资源，包含FPGA芯片映射的FPGA资源阵列以及每个坐标位置所包含的逻辑单元块数量.

特征二(f2)： 已布逻辑单元块占用资源.该特征动态记录FPGA资源阵列中每个坐标位置上已布的逻辑单元块数目.最大值为特征一中对应坐标位置的值.特征二与特征一的差值即是每个坐标位置可供使用的逻辑单元块资源数目.

特征三(f3)： 线网连接数量.线网连接记录坐标位置已布逻辑单元块与待布逻辑单元块线网连接的数量，线网的统计包含了直接相连和跨一级相连(在一条路径中，隔一个中间结点实现相连).

特征四(f4)： 线长代价.根据半周长线网框的线长计算方法，对于待布逻辑单元块中输入输出端线网(线网已出现在已布逻辑单元块或该待布逻辑单元块中)，提取待布逻辑单元块位于不同位置时对线长的影响.

(1)

特征六(f6)： 时序信息特征.时序部分特征包含多个子特征.时序优化作为VPR中时序驱动模拟退火算法的主要目标，是决定布局结果的关键.本文中时序部分信息的提取采用了VPR布局中的延时模型.

1) 结点时序最大值.结点时序最大值表示FPGA资源阵列的坐标位置上已布逻辑单元块的所有结点中最长延时的最大值.

图6 源结点需求的逻辑单元块数量Fig.6 Source node’s demand of logic elements

2) 输入端线网源端时序值.该特征提取待布逻辑单元块输入端线网源端结点的最长延时，与结点时序最大值特征考虑全局时序信息不同的是，该特征考虑局部与待布逻辑单元块输入端直接相连的时序信息.

3)输出端线网漏端时序值.该特征提取待布逻辑单元块输出端线网漏端结点的最长延时.

在FPGA资源阵列的每个特征中，无效或者没有实际值的坐标位置都取值为0，当FPGA资源阵列的坐标位置包含多个逻辑单元块时，各个特征在该坐标位置的取值为与各个逻辑单元块对应特征值的平均值.

2.4 待布逻辑单元块的选择

表3 FPGA的簇映射

随着布局过程的进行需要动态选择下一个待布的逻辑单元块.根据PEKO思想，一个好的布局结果，倾向于将线网连接的逻辑单元块布局紧凑[9,13]，所以将在FPGA资源阵列中坐标位置靠近的多组逻辑单元块集合为一个逻辑单元簇.如表3所示为FPGA有效资源阵列参数n大小与选取的逻辑单元簇大小的对应关系，确定了逻辑单元簇大小之后，FPGA资源阵列映射后得到的FPGA簇阵列的阵列规模也如表中所示.对FPGA簇阵列中每个坐标位置计算未布逻辑单元块中与对应逻辑单元簇范围内已布逻辑单元块亲密度加权和最大的逻辑单元块.每次选择所有簇中与簇内逻辑单元块亲密度最大的逻辑单元块作为待布逻辑单元块.

待布逻辑单元块的选择分为两次筛选过程： 首先选出与逻辑单元簇中逻辑单元块线网连接的数量之和最大的未布逻辑单元块.然后在其基础上选出与逻辑单元簇中逻辑单元块亲密度加权和最大的未布逻辑单元块.两个逻辑单元块clb1，clb2之间的亲密度Correlation(clb1,clb2)由式(2)，(3)可得，Basicval称为逻辑单元块的基础价值，在动态电路网表解析后，如图1输出端线网源结点Node C，Totnode为解析后网表中Node C所在树的总结点数目，Rmnode为Node C为根结点的子树的总结点数目，Curlen为Node C结点的深度，Totlen为该结点所在树的最大深度.α为经验参数，这里取值为0.25.Connection(clb1,clb2)即为2个逻辑单元块线网连接数量特征的值.式(5)中Correlation(clb1,cluster)为clb1与逻辑单元簇cluster中逻辑单元块的亲密度加权和.其中：Xave和Yave认为是clb1与逻辑单元簇亲密度计算下的重心位置；Xave由式(4)计算得到；Xclb2为clb2在该逻辑单元簇中的相对位置，Yave同理.

(2)

Correlation(clb1,clb2)=Basicval(clb1)+Basicval(clb2)+Connection(clb1,clb2).

(3)

(4)

(5)

2.5 快速详细布局

FPGA资源阵列中可能包含一个或者多个逻辑单元块，在处理其布局流程时略有不同，主要为： 一，处理各个特征时，对应各个坐标位置的取值为与各个逻辑单元块对应特征值的平均值；二，由于预测位置得到的是在FPGA资源阵列中的位置，处理大规模电路布局过程中，位置坐标中包含多个逻辑单元块时，预测的位置往往不是精确映射回FPGA芯片阵列.为了处理上述问题，并且进一步优化时序，可以对模型训练之后的布局结果进行详细布局.采用基于交换的详细布局方法，为实现更有效交换从而加快详细布局速度，对需要交换的逻辑单元块和其进行交换的区间进行约束.待交换的逻辑单元块是与延时裕量(slack)最低15%路径关联的逻辑单元块[13]，交换区间的选择基于可行区域[14]进行优化，经过多次迭代得到最终的布局结果.

优化策略上，首先使用最小延时时序矩阵对可行区域进行进一步提取，其中最小延时时序矩阵F(x,y)是VPR布局阶段使用全局布线资源的延时分析矩阵，记录位置坐标相差(x,y)的2个结点之间的全局布线之间的最小延时，虽然不能准确估算布线之后的路径延时，但是可以在布局阶段给出合理的参考.如图7所示，假设CLB1中Net1，Net2，Net3分别是网表中slack最低15%的线网路径，以Net1为例，(x1,y1)和(x2,y2)是决定线网输入端(xs,ys)最大延时的结点，可行区域如图中A、B、C、D所示.经过最小延时时序矩阵计算，保留可行区域中使得(x1,y1),(x2,y2)到(xt,yt)延时更小的部分区间.其次，对于连接到多条时序上高关键度路径的逻辑单元块，分别对每条路径的可行区域进行评估，并优先使用区间重叠区域进行交换.假设图8为图7中线网Net1,Net2,Net3分别对应的3个可行区域的交叠情况，区域1为3个可行区域重叠的区域，在进行位置选择时具有最高的优先级，其次是区域2，再是区域3.

图7 基于线网Net1的可行区域Fig.7 Feasible range of Net1

图8 CLB1可行区域的分级Fig.8 Classification of feasible range of CLB1

3 模型训练与特征工程

表4 不同特征组合和对应的预测精确度

注： “*”表示为模型序号中包含的特征;“—”则表示该模型序号中没有使用的特征.

为了训练用于确定待布逻辑单元块位置的深度学习模型，采用随机电路网表生成器和最优线长电路网表生成器生成的网表产生模型训练数据，分别为270万和30万数据.训练环境为Linux系统下Keras 2.1.0(基于Tensorflow 1.4.0)，Xeon E5-2620处理器，4块TITAN-V和3块TITAN-X GPU，在初始学习率0.003下经过20 epoches训练得到最终的模型.在过滤掉无效和不合法数据之后提取top5模型预测准确度(标签位置在预测位置概率分布中top5的精确度).并针对多组特征进行分别训练，分析不同特征对模型训练的影响.

表4为不同特征组合进行模型训练得到的结果，f1～f5分别为特征一到特征五，f6-1,f6-2,f6-3分别为特征六的3个子特征，总共进行了DL1～DL99组对照分析.可以看到不同特征对模型的影响差别各异，同时采用6个完整特征时得到最高的模型预测准确度，预测达到41.3%的top5准确度.

4 实验结果

注： 1)平均值.

实验采用深度学习特征组合DL9训练得到的模型进行测试，调用模型进行位置预测后进行快速详细布局优化.在与模型训练的相同运行环境下使用MCNC基准电路[15]与VPR 8.0中使用的模拟退火布局算法进行对比.使用的FPGA为通用岛形结构k4_n4_v7_bidir.xml，实验结果如表5所示.从表5可以看出，尽管在布线后关键路径延时上，基于深度学习的布局算法与VPR相比关键路径延时相差大致为9.8%，但是从运行时间上看，基于深度学习的布局算法能够明显提升运行速度，提升在1.59到78.5倍，平均上看运行速度提升在24.54倍，其中接近十万量级的大规模电路实现近似64.9倍的运行速度提升.分析数据可以看出，布局的加速效果受电路规模影响很大，这是由于基于交换的模拟退火算法交换空间随着电路规模的增大成指数级增长，因而模拟退火算法在处理类似mcml,arm_core等规模大的电路交换次数达到数亿次，而基于深度学习的布局算法布局的次数与可交换逻辑单元块数量相同，快速详细布局部分只有少量的时序优化交换次数，总的来说，在处理大规模电路时该算法的运行速度能够得到非常大的提升，这也适应于实际应用.

5 结 语

本文基于FPGA芯片描述k4_n4_v7_bidir.xml将布局过程转化为逐步进行待布逻辑单元块的选择和逻辑单元块位置确定的过程.利用残差网络对数据进行训练，得到在6组特征下41.3%的top5预测精确度.该算法对MCNC基准电路与VPR相比在平均9.8%的关键路径延时损失下实现了平均运行速度24.54倍的提升，在处理大规模电路时有明显的时间优势.实际上本文中的算法可以支持复杂的可配置逻辑块的结构，也体现深度学习工具在处理FPGA这样的NP问题时有实际的意义.