基于初始解优化的FPGA 布线方法

惠 锋，谢尚銮

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

1 引言

布线是现场可编程门阵列（FPGA）编译流程中的关键模块，占用整个编译工具大量的运行时间，且布线质量直接影响芯片的最终性能。因此提升布线器性能、减少布线时间是FPGA 编译流程中的关键问题[1]。

布线是在满足用户设计约束的前提下，利用器件布线资源连接布局后的逻辑单元。由于器件布线资源有限，拥塞在布线过程中不可避免。拥塞协商算法[2]的思想是引入对历史成本的需求，通过迭代“拆线-重布”操作来协商解决布线拥塞问题。目前几乎所有FPGA 厂商的布线器均以拥塞协商算法为基础，拥塞协商算法在该领域占主导地位，学术界广泛使用的FPGA 架构设计和分析工具VPR 也是由此改进而来。为了提升布线器性能，研究人员提出了诸多优化策略。工业界主流厂商的优化细节不公开，学术界则主要有并行计算[3-4]和宏模块[5]等优化策略。并行计算策略通过对线网的任务划分与分配来实现算法的并行化，并采用互斥锁的方式解决布线资源竞争问题。但随着用户设计规模变大，高扇出线网边界会逐渐覆盖整个芯片，算法效率变低。宏模块策略通过将电路模块封装为宏单元进行布线来减少时间开销，由于宏单元内部结构在实际布线时无法更改，因此解的质量不佳。文献[6]针对复位信号等高扇出线网利用FPGA 专用时钟资源进行布线，有效避开与普通线网的资源竞争，达到提升布线效率的目的。

在没有新算法引入或改进算法存在缺陷的情况下，利用FPGA 结构定制优化策略也是一种提升编译工具效率的方法。本文基于自主研发的FPGA 器件布线资源结构，通过重构布局网表执行预布线，为布线算法提供优质的初始解，从而实现解的快速收敛，达到提升布线性能的目的。

2 FPGA 结构

自主研发的FPGA 芯片简化结构如图1 所示，其中主要包括可编程输入输出块（IO）、可编程逻辑簇（CLC）、可编程互连资源和异构集成的存储器等硬件。可编程互连资源是FPGA 各模块实现信号传递的桥梁，由开关盒（SWB）、连接盒（CB）和布线通道组成，其中SWB 位于水平布线通道和垂直布线通道的交汇处，实现布线方向和不同布线类型间的切换；CB 则分布于CLC 的四周，通过内部开关或多路选择器将CLC 的输入和输出连接到任意纵横的布线通道上，每个CLC 与关联的CB 与SWB 组成了一个逻辑块。

图1 FPGA 的简化结构

一个CLC 由2 个逻辑片（dice）组成，每个逻辑片中有4 个6 输入查找表（LUT），其中每个LUT 输入端口上的引脚逻辑等价，各引脚可以随意交换与LUT 输入端口的连接顺序，而不影响电路逻辑功能，在交换后修正LUT 配置信息即可[7]，本文将该操作称为引脚的重构。为了提升布通率，在逻辑块内集成了SWB 到LUT 的48 组特定布线资源，逻辑片内的连接关系见表1，其中IN0~IN47 为SWB 的输出端口，并以字母A~D 与数字1~6 的组合区分dice 中不同LUT 的不同输入端口。

表1 逻辑片内的互连资源表

3 基于初始解优化的FPGA 布线方法设计

本文提出一种有效的布线优化策略，在加载网表文件后，根据逻辑片的特定布线结构对逻辑单元引脚进行重构，进而实现片内布线资源的有序分配，为拥塞协商布线算法提供优质的初始解，提高其求解效率。

3.1 收益分析

在FPGA 设计流程中，装箱通常使用聚类及最小割等算法[8-9]，将关联度大的逻辑单元组装到同一个CLC 中，以减少信号与外部的连接，缩小装箱面积。

已知1 个源端为Q 的线网，其漏端数为2 且位于相同逻辑片中，位置分别为D1 与A4。布线器在布线资源充足时的最优解是用布线开关M 引脚的过渡将A4 与Q 连通，最优布线解见图2，图中SWB 内部的虚线为布线开关，SWB 间的实线为布线通道，该结果产生4 个布线开关和1 条布线通道的开销。

图2 最优布线解示意图

然而在实际布线过程中拥塞问题是无法避免的，布线器通过惩罚冲突资源来增加其布通成本，协商解决拥塞问题，因此随着布线资源竞争的加剧将导致较差的布线解，图3 为其中的1 种情况，布线器需消耗4个SWB 开关和2 条布线通道资源才能将Q 与A4、D1连接，从而增加了布线拥塞发生的几率，增大了布线资源的扩展范围和运行时间。

图3 不佳布线解示意图

若利用LUT 输入端口各引脚的逻辑等价性，将D1 上的漏端引脚重构至D2，这样布线器只需2 个SWB 开关和1 条布线通道就可以将Q 与该漏端连通，与图2 的结果相比可节省2 个SWB 开关，该解的示意图见图4。

图4 优化的布线解示意图

基于上述分析，在布线前通过对线网逻辑单元引脚重构可以实现布线资源的有序利用，有助于改善布线资源的竞争问题，减少布线拥塞数量。

3.2 初始解生成

对于任意两个线网漏端，若其所对应源端不同或对应引脚逻辑等价，则称其是互斥的。本研究遍历布线网表，通过将其中每个CLC 内的线网漏端基于互斥性高效分组并加以引脚重构来获得初始解，其示意图见图5，具体步骤为：

图5 初始解生成示意图

1)创建集合X，令变量i=0，获取网表内的k 个CLC{m0,m1,...,mk-1}；

2)对于mi，将其中逻辑单元引脚对应的线网漏端均存入X，令变量j=0；

3) 若X 为空集，进入步骤4；否则，创建漏端组Yj，依次读取X 中保存的漏端s，若Yj为空或s 与Yj中的漏端均不互斥，将s 从X 中移出至Yj。当前X 的遍历结束后，令j=j+1，重复该步骤；

4)将mi内的漏端划分为j 组，将其按照内部元素数量降序排序，重标记为{Z0,Z1,...,Zj-1}，令变量h=0；

5)查找SWB 的空闲IN 端口（节点），确定与其连接的LUT 端口列表F，将Zh中的漏端从当前连接的端口交换到F 中同一LUT 的端口，更新端口映射表。若h

6)若i

图6 线网漏端处理

3.3 布线算法的改进

为了提升布线效率，本研究对现有布线流程进行改进，在布线实现阶段采用节点与漏端相结合的策略进行布线，具体的改进布线算法流程如图7 所示，其中SLACK 为关键路径时序裕量。首先在全局布线阶段基于重构后的初始解完成源端与节点之间的布线。然后在详细布线阶段，根据时序分析结果对拥塞线网的漏端逐一分析，组内漏端时序违规处理见图6（b），移出时序不合法的漏端进行单独布线，其余漏端仍以源端到节点的形式进行拆线-重布，每个节点仍对应1个漏端组，布通该线网后更新路径上节点的当前拥挤度；每次布线迭代完成后更新布线树节点占用的历史成本，并调用时序分析引擎更新漏端关键度，直到无布线资源被重用后算法结束[10]。

图7 改进布线算法流程

4 试验结果与分析

本研究针对自主FPGA 芯片，提出初始解优化策略以提升布线效率，并利用典型的布线测试例集进行验证。试验在CPU 为3.4 GHz Intel core I7-6700、内存为32 GB、操作系统为Windows 7 的PC 上进行，采用经典的拥塞协商布线算法进行求解，记录算法加入初始解优化策略前后的运行数据，其结果如表2 所示，其中“全局冲突”为全局布线阶段的冲突资源数量；“迭代”为详细布线阶段“拆线-重布”操作的迭代数，“详细冲突”为迭代过程累计的冲突资源数量；“时间”为算法实现设计收敛所需的CPU 运行时间；“裕量”为关键路径时序裕量；“平均值”为各测试例同一试验参数的平均值。

表2 试验数据

本文通过重构网表中的逻辑单元引脚来实现逻辑片内布线资源的高效分配，得到布线拥挤度低的初始解，并采用节点与漏端相结合的布线策略快速实现了设计收敛。试验数据表明，采用初始解后的布线算法与原始算法相比可在全局布线阶段减少16.6%的冲突资源数，在详细布线阶段减少12.4%的迭代次数与9.8%的累计冲突资源数。布线问题是一个复杂的非确定性多项式难题，布线拥塞数量直接影响算法的求解时间，因此本文也实现了7.8%的CPU 运行时间优化，17.2%的关键路径时序裕量优化。

5 结论

本文通过逻辑片内高效预布线为拥塞协商布线算法提供了布线拥挤度低的初始解，并在布线过程中采用节点与漏端相结合的布线策略来提升布线效率。试验数据表明所提方法可有效改善布线资源竞争现象，加速算法收敛，并实现关键路径时序裕量优化。由于装箱与布局的结果都将影响布线器的质量，因此后续研究的方向是为自主研发的FPGA 器件结构提供一个有效的拥塞预测模型来指导装箱和布局算法的求解，为布线器提供更优质的输入，同时也能为FPGA器件结构的优化提供设计参考。