用于时分复用技术的多阶段协同优化FPGA布线方法

刘耿耿 许文霖 周茹平 徐 宁

①(福州大学计算机与大数据学院 福州 350116)

②(福建省网络计算与智能信息处理重点实验室 福州 350116)

③(武汉理工大学信息工程学院 武汉 430070)

1 引言

近年来，现场可编程门阵列(Field Programmable Gate Array, FPGA)广泛应用于各个领域，如深度学习[1]、云计算[2]和芯片设计的验证问题[3]。复杂的专用集成电路(Application Specific Integrated Circuit, ASIC)芯片设计需要通过多种验证方法保证设计的正确性。验证的主要方法有软件仿真、形式化验证和硬件仿真。随着芯片设计越来越复杂，软件仿真需要花费大量的运行时间仿真每个逻辑电路，形式化验证难以适用于大型ASIC设计的验证问题，同时传统的硬件仿真方法需要花费大量的成本来实现验证。而基于FPGA原型验证的硬件仿真方法可以解决大型ASIC设计的验证问题，并且能够在成本和运行时间之间做到平衡。因此，许多先进的微处理器制造商在其验证过程中使用了基于FPGA原型验证的硬件仿真方法。

ASIC设计随着规模的不断扩大，越来越难在单个FPGA上实现逻辑验证[4,5]。因此，大型的ASIC设计将根据设计需求被划分到多个FPGA内。与单FPGA系统相比，多FPGA系统逻辑复杂性更高，设计能力更强。高速收发器被运用于FPGA系统中，可以提高FPGA间的数据交换速度。随着FPGA内部构造越发复杂，FPGA间信号数量会远远超过I/O引脚数量。而时分复用(Time-Division Multiplexing, TDM)技术被广泛运用于解决I/O引脚数量不足的问题。然而，TDM技术会造成FPGA间的信号延迟，导致系统时延的增加。因此，减少TDM技术所导致的系统时延是十分重要的问题。

时分复用比率是用来衡量系统时钟周期使用情况的数值。在多FPGA原型系统的设计流程中，TDM比率通常是在FPGA布线后确定的。文献[6]提出了同时进行信号分割和分组的方法，可以优化分区和TDM比率。为了解决FPGA间的布线问题，文献[7]和文献[8]使用Pathfinder迭代地优化FPGA间的布线问题。然而，这两类工作都未考虑线网组的概念。文献[9]通过减少线长优化FPGA间的布线结果。然而，多FPGA系统的优化目标不仅仅是线长，TDM的比率分配也非常重要，因为系统性能很大程度上受到FPGA间线网的延迟影响。为了优化TDM比率，文献[10]提出了一种基于整数线性规划(Integer Linear Programming, ILP)的优化算法，但ILP只适合解决较小尺寸的问题。此外，以往工作中的TDM比率通常是任意整数，并不符合实际情况。

根据实际应用中的设计，本文提出一种用于时分复用技术的多阶段协同优化FPGA布线(Multi-Stage Co-optimization FPGA Routing, MSCOFRouting)方法，旨在满足TDM比率约束的前提下，布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段协同优化FPGA间的可布线性和TDM比率。本文的主要贡献如下：

(1) 提出一种自适应布线算法，以避免布线拥塞，解决FPGA间布线优化问题，有力减少系统时延。

(2) 提出一种基于拉格朗日松弛(Lagrangian Relaxation, LR)的TDM比率分配算法，使小规模线网组获得较大TDM比率，大规模线网组获得较小TDM比率，有效解决TDM比率分配问题。

(3) 提出了一种TDM比率优化算法，缩减线网组和FPGA连接对的TDM比率。

(4) 将多线程并行化方法运用到上述3个算法，进一步提高MSCOFRouter的运行效率。

(5) 实验结果表明，本文算法不仅能满足TDM约束条件，而且可以获得比同类工作更好的解决方案。

后文组织如下：第2节介绍了时分复用技术和问题模型；第3节阐述了MSCOFRouting的整体框架。第4节给出本文相关策略的有效性验证及实验结果的比较分析。第5节总结全文。

2 问题模型

2.1 时分复用技术

使用时分复用技术可以有效地解决I/O引脚数量不足的问题，使得多个信号可以在不同时间段共用一个I/O引脚。然而，使用时分复用技术会造成系统时延的增加。TDM比率是用来衡量系统时钟周期使用情况的数值，可以作为衡量系统时延的指标。系统时延与TDM比率呈单调递增关系。因此，通过降低TDM比率可以有效减少系统时延。FPGA连接对p上边e的时分复用比率如式(1)所示。

其中，DN(p), Cap(p)和TR(e)分别代表通过FPGA连接对p的信号数、FPGA连接对p的容量和边e的TDM比率。由于一个FPGA连接对间只有一根物理导线，所以FPGA连接对的容量固定为1。

图1是时分复用技术的示意图。图中的长方形、正方形和圆形分别表示转换器、实例和分区。红色箭头、蓝色箭头和绿色箭头分别表示3种不同的信号，两个FPGA中间的黑色箭头表示两个FPGA之间唯一的物理导线。在未使用时分复用技术的情况下，一个系统时钟周期内，一条物理导线只能传输一种信号。这会导致FPGA系统运行效率的下降。为了提升FPGA系统的运行效率，时分复用技术被运用在FPGA系统中，使得在一个系统时钟周期内可以传输3种不同的信号。

2.2 FPGA间的布线问题

2019年ICCAD比赛[11,12]提出的FPGA间布线问题将FPGA系统中的FPGA抽象为节点，忽略了一些FPGA的特殊性，着重解决FPGA间的布线问题。本文常用的符号如表1所示。

表1 常用符号

本节通过图2和表2的例子介绍FPGA间的布线问题。给定一组线网N和一组线网组NG。线网组是根据设计目的给定的。例如，具有相似属性或相同功耗的线网将在同一个线网组中。同时，给定一个无向图G，其中包括了多个由F表示的FPGA和多个由P表示的FPGA连接对。问题目标是根据无向图G对所有线网进行布线，并且为每条边分配合理的TDM比率，以最小化线网组的最大TDM比率。

表2 线网组信息

图2 TDM比率分配示意图

表2给出了线网N和线网组NG的信息，其中，不同的线网用不同颜色表示。图2(a)是一个结构图。fi代表第i个FPGA，pk代表第k个FPGA连接对。图2(b)是表1基于图2(a)所生成的布线结果。ej,k代表线网nj经过连接对pk所布的边。连接对pk间边的数量就是通过连接对pk的信号数量。为了分析系统时延，每条边ej,k应该被分配一个TDM比率。一个FPGA连接对应该满足TDM比率约束，如式(2)所示。

其中，etrj,k表示ej,k的TDM比率。如图1所示，由于所有的信号必须在半个周期内完成1次传输，故etrj,k的值必须是偶数。每条边的TDM比率分配结果如图2(c)所示，对于p1, e2,1, e3,1, e4,1和e5,1的TDM比率分别是4, 6, 6和10。由于1/4+1/6+1/6+1/10<1，所以p1满足TDM比率约束。

线网nj的TDM比率和线网组ngj的TDM比率定义为

其中，ntrj和gtrj分别表示nj的TDM比率和ngi的TDM比率。如图2(c)所示，线网n2上的边有e2,1=4和e2,3=2，所以ntr2=etr2,1+etr2,3=2+4=6。线网组ng2的包括n3和n4，所以gtr2是12。

本文的优化目标是最小化TDM比率最大线网组的TDM比率，从而优化系统时延，具体如式(6)所示。

其中，gmt代表了TDM比率最大的线网组的TDM比率。如图2(c)所示，gmt是12。

3 总体框架

用于时分复用技术的多阶段协同优化FPGA布线方法的总体框架如图3所示，分别为布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段。具体地，第1阶段根据问题定义的线网和线网组进行布线，得到未分配TDM比率的布线结果。第2阶段使用拉格朗日松弛的方法为FPGA连接对的每条边分配初始的TDM比率。第3阶段通过松弛TDM比率较小的线网组，减小TDM比率倒数之和相对较小的FPGA连接对的最大TDM比率来优化TDM比率比较大的线网组。MSCOFRouting通过上述3个阶段协同优化FPGA的可布线性和TDM比率分配结果。

图3 MSCOFRouting总体流程图

3.1 布线拓扑生成

布线拓扑生成阶段的目标是根据给定的线网和线网组定义将每个线网的FPGA连接在一起。布线生成的Steiner树的质量会影响后续的TDM比率分配。由于Dijkstra算法可以有效构建Steiner树[13,14]，因此本文使用基于Dijkstra算法的FPGA间布线算法连接所有线网，解决FPGA间的布线优化问题，使可布线性得到优化。算法中各变量的定义如下，fs代表从Fn中选择的第1个FPGA、Fn表示线网nj必须连接的目标FPGA、d表示两个FPGA间的布线代价、Fall表示所有FPGA、fu表示与fs布线代价最小的FPGA，fv表示fu的每个邻居FPGA,spv表示该线网的Steiner树。

自适应布线算法如下所示。由于线网所在的线网组中的线网数量和线网需要连接的FPGA数量对于线网的布线方案有重要的影响。所以所有线网都按照这两个指标进行排序。然后，初始化布线图，每个FPGA连接对的初始布线代价为1。最后，对所有的线网进行迭代布线。

对所有的线网进行迭代布线的具体步骤如下。首先，从Fn中选择一个FPGA赋值给fs。其次，初始化Fn中各FPGA与fs的距离。然后，集合Fall等于集合F。最后，通过Dijkstra算法构造Steiner树。Dijkstra算法首先找到与Fall中与fs代价最小的FPGA fu，然后更新集合Fall，最后更新fu的所有邻居节点的布线代价dv。当找到所有目标FPGA后，Steiner树被构造出来，把spx记录下来。Steiner树所使用的FPGA连接对的布线代价更新公式为

其中，Tpk代表FPGA连接对的布线代价，Npk代表FPGA连接对上已布线的边数，te和to分别表示FPGA连接对上已布线的边数为偶数和奇数的更新代价。实验得出te, to分别取0.81和1.19时优化效果最好。

图4只考虑两个FPGA间的布线情况。两个FPGA间有1条或者2条边时，每条边分配的TDM比率都是2，最大TDM比率都是2；当两个FPGA间有3条边时，每条边分配的TDM比率分别是2, 4, 4。当两个FPGA间有4条边时，每条边分配的TDM比率分别是4, 4, 4, 4。最大TDM比率都是4。由此可以得出结论：设i为奇数，当两个FPGA间有i条边时，布下1条边之后，最大TDM比率不变，为i+1；当两个FPGA间有i+1条边时，布下1条边之后，最大TDM比率值增加2，为i+3。所以布线代价更新式(7)可以减少两个FPGA间奇数条边的情况，优化布线结果，减少最大的T D M 比率。

图4 FPGA之间不同布线情况示意图

3.2 TDM比率分配

TDM比率分配阶段需要为每条边分配满足约束的TDM比率并且使TDM比率最大的线网组的TDM比率最小化。在这一阶段，本文提出了一种基于拉格朗日松弛算法的TDM比率分配方法。

由于优化目标是将线网组中最大的TDM比率最小化，所以问题模型可以写成

其中，gmt是布线图中TDM比率最大的线网组的TDM比率，tren是线网n中边e的TDM比率。本文将此公式称为主问题(Primal Problem, PP)。为了解决这个NP难问题，算法松弛第1个约束并引入非负拉格朗日乘数λ。λ作为违反约束的惩罚值。式(8)引入λ后可以得到

对于给定的拉格朗日乘数，拉格朗日乘数子问题LRS(λ)如式(10)所示。

通过应用Karush-Kuhn-Tucker (KKT)条件以获得最优解，LRS(λ)问题可以简化为

拉格朗日对偶问题(Lagrangian Dual Problem,LDP)可以定义为

对给定λ集合，求解LDP就是求解下界的最大值。LDP的主要目的是找到合适的λ集合惩罚PP中违反的约束。拉格朗日乘子根据时序弧的时序临界性更新，以满足KKT条件[15–17]。更新公式为

其中，TDMi,g为第i次迭代线网组g与最大线网组的TDM比率之比，Ki,g为第i次迭代的加速因子。加速因子越大，收敛速度越快，但是收敛效果越差。λ越接近目标值，加速因子应该越小。Ki,g的更新公式为

其中，str是由用户定义的gmt的优化目标。

TDM比率分配算法如下所示。首先，计算边ej,k的所在FPGA连接对边的数量。接着，计算线网组ngi的λi。然后，根据λ集合计算线网ni的snλi值，计算分配给每条边的TDM比率，再更新λ集合。最后，根据式(13)更新λi并根据式(14)更新Ki,g。

3.3 TDM比率优化

在TDM比率分配阶段，通过拉格朗日松弛算法得到的初始TDM比率并非最优解，还存在优化空间。因此，TDM比率优化阶段可以通过增加TDM比率较小的线网组边的TDM比率以减少TDM比率较大的线网组边的TDM比率，并可以针对具体连接对进行优化系统时延，从而使TDM比率最大的线网组的TDM比率最小化。

TDM比率优化算法包括3个步骤。第1步是缩减操作。具体是增加TDM比率较小的线网组的TDM比率，减少TDM比率较大的线网组的TDM比率。第2步是合法化操作。经过缩减步骤后，TDM比率增加的FPGA连接对可能会违反TDM比率约束。因此，违反约束的FPGA连接对需要进行合法化操作。第3步是针对性优化操作。经过上述步骤后，所有FPGA连接对的TDM比率的倒数和与最大值1还有一定距离。通过减少连接对中TDM比率最大的etrj,k的方式，使得每个FPGA连接对的TDM比率倒数和更接近1，从而使TDM比率最大的线网组的TDM比率更小。

缩减操作的具体步骤如下所示。首先，所有线网按其所在线网组的最大TDM比率从大到小排序。然后，线网nj中每条边的TDM比率e t根据以下公式更新。

线网nj的TDM比率减少后，更新nglj中各线网组的TDM比率，有利于后续的缩减。

第2步是对FPGA连接对进行合法化操作。经过缩减步骤，TDM比率增加的边ej,k可以直接使用新的TDM比率e tr；对于TDM比率减小的边ej,k，如果pk满足TDM比率约束，则用e tr替换对应的pk中的每条边的etrj,k。然而，如果pk不满足TDM比率约束，应由式(16)合法化。

算法第3步是减小具体FPGA连接对的最大TDM比率。经过前两个阶段后，当FPGA连接对边的TDM比率倒数和resk小于0.95时，这个FPGA连接对的最大TDM比率由式(17)进行更新。

其中，resk是FPGA连接对pk上TDM比率倒数和，eltk,max是FPGA连接对pk上最大的TDM比率。

如果在缩减步骤中，当mngj> str，减少的部分都向下取偶数会使得当前FPGA连接对的TDM倒数和更小，更有利于第3步FPGA连接对中最大TDM比率的减小。比如，当有3个线网组的TDM比率为4, 14和24，优化的目标值为8。如果不论mngj是否大于str，变化值都向上取偶数，经过缩减阶段得出的TDM比率是6, 10和16，TDM倒数和为0.329；如果按照式(15)优化TDM比率，得到的TDM比率是6, 12和16，TDM倒数和为0.25。后者TDM比率倒数和小于前者，更有利于第3步FPGA连接对最大TDM比率的减小。所以选择式(15)的缩减方式。

3.4 多线程并行化

为了提高布线器的效率，使用并行编程模型OpenMp在布线器的各个阶段集成多线程并行化方法。编译器通过识别编译制导语句自动创建线程进行并行化，从而有效提高算法的效率。在布线拓扑生成阶段，各线网的布线操作可以并行执行。在TDM比率分配阶段，每个线网的TDM比率分配都是完全独立的。因此，这个阶段可以对不同线网进行并行化操作。在系统时延优化阶段，每个线网的缩减操作都是并行的。合法化操作和针对性优化中不同FPGA连接对可以并行处理。但是，由于不同线网之间存在资源冲突，自适应布线算法的记录spx操作和TDM比率优化算法的更新nglj中各线网组的TDM比率操作应该加锁。通过对上述3个阶段使用多线程并行化方法可以有效减少算法运行时间。

4 实验结果

所提出的优化框架采用C/C++语言实现，并在Intel Xeon Linux服务器上运行。本文在2019年的ICCAD竞赛[12]发布测试用例上展开实验。该测试用例将FPGA系统中的FPGA抽象为节点，忽略了一些FPGA的特殊性，着重解决FPGA间的布线问题。所以本文算法可以解决不同FPGA的布线问题，具有普适性。表3为测试用例具体信息，其中#FPGA表示FPGA数量，#Net表示线网数量，#NG表示线网组数量，#Edge表示FPGA连接对数量。

表3 测试用例信息

4.1 与ALIFRouter及MSFRoute的实验比较

本节参考ICCAD2019比赛[12]的计算评估分数公式将MSCOFRouting与ALIFRouter[11]及MSFRoute[18]进行比较。为了强调运行时间的影响，计算评估分数时考虑了运行时间。评估分数sco计算公式为

其中，TR为TDM最大的线网组的TDM比率，RT为运行时间，MRT为3个布线器运行时间的中位数。sum为所有测试用例的sco之和。布线器的sum越小表示它的优化效果越好。

如表4所示，MSCOFRouting获得了最好的sum，并且达到了最好的TDM比率和运行时间。与MSFRoute和ALIFRouter相比，MSCOFRouting的TDM比率分别降低了4.57%和1.05%，运行时间分别缩短了20.8%和0.44%。由于每个标准测试用例涉及多个线网组，总的布线边数量非常多，因此时钟周期数的基数很大，TDM比率数值很大。虽然TDM比率的优化率较小，但是TDM比率优化值较大，系统时延的优化效果较好，所以实验结果表明MSCOFRouting可以有效优化系统时延。

表4 本文算法与ALIFRouter及MSFRoute的实验比较(TR为TDM Ratio)

4.2 多线程并行化方法的有效性验证

MSCOFRouting在不同线程数下的运行时间如图5所示。不同的线段表示不同测试用例的运行时间。本节在具有典型性的中等规模测试用例S3, S4和H2上展开实验。通过使用8个线程、16个线程、24个线程和多线程并行化方法，MSCOFRouting分别可以得到3.11倍、3.82倍和4.08倍的加速。各线网间存在共用同一变量的情况。为了避免多个线程同时修改变量而导致数据错误，则需要对共享变量进行加锁操作。如果同时运行中的线程需要用到已使用的共享变量，则需要等待正在使用该资源的线程运行结束。所以随着线程数的增多，等待共享变量的时间逐渐增加，运行时间的优化率逐渐减少。

图5 并行化方法有效性折线图

4.3 自适应布线算法有效性验证

为了验证自适应布线算法的有效性，本节将采用不同更新代价的自适应布线算法与未采用自适应布线算法的最大TDM比率进行比较。表5为采用不同权重值的自适应布线算法的实验结果。数据都是从同一环境中由8个线程运行的程序中获得的。表5中△TR的优化率的计算公式为

表5 自适应布线算法有效性验证

不同的更新代价分别将△TR比率的优化率增加4.26%, 11.63%, 4.88%和10.93%。根据实验结果可知，当te=0.19, to=1.81时，自适应布线算法效果最好。由于较好的布线结果较少出现布线拥塞的情况，从而减少最大TDM比率。因此通过这些△TR的优化率可以得出自适应布线算法可以有效避免布线拥塞的情况出现，解决FPGA间的布线优化问题，优化布线结果，有效地减少系统时延。

4.4 LR分配算法和TDM比率优化算法有效性验证

本节将TDM比率分配算法和TDM比率优化算法运用到当前最先进的FPGA布线器ALIFRouter中进行比较。表6为LR分配算法和多层次的TDM比率优化算法的实验结果，并与ALIFRouter的实验数据进行对比。数据都是从同一环境中由8个线程运行的程序中获得的。表格中△TR的优化率是由MSFRoute在各测试用例上得到的线网组的最大TDM比率减去使用ALIFRouter、使用TDM比率分配算法和使用TDM比率优化算法后获得的最大TDM比率计算得到的。与ALIFRouter相比，两种算法可分别将ΔTR比率的优化率增加8.85%和10.39%。这些ΔTR的优化率表明LR分配算法和TDM比率优化算法可以有效地降低系统时延。

表6 LR分配算法(即TDM比率分配算法)和TDM比率优化算法有效性验证

5 结束语

针对FPGA系统中运用TDM技术后导致系统时延增加的问题，本文提出了一种用于时分复用技术的多阶段协同优化FPGA布线方法，通过布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段协同优化FPGA的可布线性和TDM比率分配结果。首先，为了生成高质量的布线拓扑，避免布线拥塞，解决FPGA间的布线优化问题，提出了自适应布线算法。其次，使用基于拉格朗日松弛的TDM比率分配算法，为布线图的边分配系统时延更小的初始TDM比率。然后，为了进一步减小最大线网组的TDM比率，通过一种多层次的TDM比率优化算法，同时缩减线网组和FPGA连接对的TDM比率。并且，为了提高MSCOFRouting的运行效率，在上述3个算法中使用多线程并行化方法，降低算法的运行时间。实验结果表明，与同类布线器相比，本文提出的MSCOFRouting能够获得最佳的系统时延优化质量。未来的工作中，将扩展本文算法应用到考虑带高速收发器的FPGA系统的TDM比率优化问题。