BLE级FPGA布局实现及验证

惠 锋，许 慧，虞 健，王新晨

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

1 引言

现场可编程逻辑门阵列(Field-Programmable Gate Array,FPGA)是一种可以根据用户需要来编程以改变其内部功能的通用型芯片，这种芯片以其使用灵活、成本低廉的特点而受到广泛的青睐。电子设计自动化(Electronic Design Automation,EDA)工具在FPGA的推广和使用中扮演着举足轻重的角色，这一过程主要包括综合、打包、布局、布线、仿真验证、位流下载等。其中布局是本文研究的重点，也是整个EDA流程中至关重要的环节。

布局是将网表中的逻辑单元与实际电路的物理位置建立一一对应关系的过程。布局首先要保证电路符合既定的约束条件，在这个前提下再进行布局质量的优化，其中线长、延时、功耗等都是可以考虑的指标。当前的布局算法大致可以分为三类：基于划分的算法如MHP算法[1]，基于解析的算法如使用最小二乘法求解[2]，基于启发式搜索的算法如模拟退火算法[3]。本文主要基于模拟退火算法，该算法通过设置评价函数并依据评价函数不断交换布局模块的位置来搜索最优的布局。

2 传统模拟退火布局

在传统模拟退火布局开始之前首先要经历打包的过程。打包首先将触发器 (flip-flop，FF)和查找表(Look-Up-Table，LUT)进行一对一的配对并封装为基本逻辑单元(basic logic element，BLE)，然后根据一定约束和优化条件将若干个BLE放入一个可配置逻辑块(Configurable Logic Block，CLB)中，在此后的过程中CLB内部的配置不再发生改变。

布局基于打包阶段生成的CLB级网表进行。图1所示为传统模拟退火算法的基本流程。首先生成一个初始布局状态，这一状态一般是随机生成的，然后在初始布局的基础上进行若干次交换并计算出初始温度，初始半径一般设置为芯片长度。布局的主体部分分为内外两层循环，外循环控制温度和交换半径，内循环交换CLB。每一次内循环中仅选定一个CLB，然后根据当前的交换半径选取一个芯片上的位置(site)，如果site空置则直接将选定的CLB移动到site上，如果site上已有CLB放置则交换两个CLB。移动CLB后，根据事先设定的评价函数计算出评价值的变化量ΔC，评价函数一般可以使用线长、延时、拥挤等作为参数。如果ΔC≤0，则直接接受该交换；若ΔC＞0，则以的概率接受交换[4]。这样算法便具有了接受差解的能力即爬坡能力。接受或拒绝交换后，一次内循环结束，判断是否达到了内循环的迭代上限，若未达到则继续下一次CLB的选取；若达到则退出内循环。内循环退出后在外循环中更新温度和交换半径，并判断是否达到外循环退出温度，若达到则退出，未达到则再次进入内循环。外循环退出后，将温度设置为0，这时候只能接受使布局变好的交换，进行若干次交换后算法结束。

图1 传统模拟退火算法流程图

3 BLE级模拟退火布局实现

本文基于Virtex-5芯片结构实现了BLE级的布局，布局的大体过程与传统的模拟退火算法相似，但也有一些不同的地方。

3.1 布局开始前的处理

一个Virtex-5芯片的CLB包含了两个slice和一个开关矩阵，每个slice又可以包含最多4个BLE，如图2即为一个slice。程序在打包阶段不生成CLB级网表，而是直接将BLE级网表传递给布局使用，在布局结束后再生成slice级网表供布线使用。

3.2 初始状态的生成

模拟退火开始之前先使用二次线性规划算法进行布局，得到一个较优的布局状态，并以此作为模拟退火的初始布局。在这个布局上进行若干次交换并记录其评价值，以此计算出模拟退火的初始温度，但这里所进行的交换均被拒绝，仅记录下交换后的评价值，从而保护二次线性规划算法生成的较优的布局状态不被破坏。由于已经有了较优的布局，初始的交换半径也不再设置为整个芯片的长度而是直接设置为1。

3.3 内循环

首先随机选定一个交换单元，这个单元可能是一个BLE，也可以是DSP等其他Virtex-5芯片中存在的复杂单元。若选中的是一个slice型的单元则使用交换半径来约束其交换的可达空间，在可达空间中随机选定一个site后又分为几种情况：（1）site空置，则直接将选定的单元移动到site上；（2）site上已有BLE放置但未满，则随机选择放置到空位上或者与其中一个BLE交换，空置的位置越大放在空位上的几率也越大，但不论是放置到空位还是进行交换，都必须先对其控制信号进行一致性的检测，若不一致则需重新选择其他site；（3）site上已放满，则随机选择一个BLE进行交换，并检测控制信号的一致性。如果多次单一单元的交换均失败，则将选定单元所在site上所有的单元与选定site上所有的单元进行整体交换。若选中的不是一个slice型的单元则不使用交换半径，直接在全芯片范围内选择一个相同类型的site进行交换。图3是选择和交换过程的流程图。交换后，使用基于线网边界框半周长的评价函数对交换后的结果进行评价，计算出评价值的变化量ΔC。若ΔC≤0，则直接接受该交换；若 ΔC＞0，则以的概率接受交换。一次内循环结束后，判断是否达到内循环迭代上限，达到则退出。

图2 slice示例图

3.4 外循环

内循环达到迭代上限退出后进入外循环中。由于已经在初始化时将交换半径设置为1，外循环中不再更新交换半径。外循环中以分段线性下降的方式更新温度。但在前6次更新温度时若当前布局的评价值小于初始布局的评价值，则温度反而会上升。这一过程是为了增大模拟退火算法的搜索空间，使其向全局最优解收敛。表1即为温度更新的规则，t表示温度，curscore为当前布局的总评价值，initscore为初始状态的总评价值，outer_iter代表外循环的次数，rejrate代表交换被拒绝的比例。更新完温度后判断是否达到外循环退出温度，若未达到则重新进入内循环，若达到则退出外循环。

3.5 布局结束

外循环退出后将温度置为0，此时只能接受使布局变好的交换，进行若干次交换后确定最终布局并生成slice级网表，布局结束。

表1 温度更新规则表

4 布局验证

布局结束后，将其结果保存为xdl文件，再使用Xilinx的XDL工具来验证其正确性。

使用18位累加器作为测试用例，该用例中除了普通的BLE单元外还有分布式RAM和DSP等复杂单元。在使用本文提出的BLE级布局处理电路之后将其结果保存为XDL文件，命名为ae18_core_place.xdl。使用Xilinx工具ISE Design Suite 64 Bit Command Prompt，输入 xdl-xdl2ncd ae18_core_place.xdl命令，验证布局结果的正确性，其结果如图4所示，转换成功即代表布局信息合法。

图3 BLE级模拟退火算法流程图

图4 验证布局结果

5 结论和展望

本文实现了一种BLE级的布局算法并验证了其正确性。这种算法不同于传统的CLB级布局算法，它允许在打包之后仍可以改变CLB内部配置，理论上可以增大解集以求获得更好的解，今后的研究中将基于本文实现的算法尝试改进和优化。

参考文献：

[1]G Karypis,R Aggarwal,V Kumar.Multilevel Hypergraph Partitioning:Application in VLSI domin[C].IEEE Transactions on Very Large Scale Integration (VLSI)Systems.1999.69-79.

[2]谢志宏.FPGA布局布线算法的研究和优化[D].西安：西安电子科技大学，2012.

[3]Metropolis,N A,A Rosenbluth.Equation of State Calculations by Fast Computing Machines[J].Journal of Chemieal Physies,1953,21:1087-7092.

[4]Vauglm Betz,Jonathan Rose.VPR:A New Packing,Placement and Routing Tool for FPGA Research[C].International Workshop on Field Programmable Logic and Applications,1997.