时间约束下FPGA 资源最小化的动态重构∗

安 洋 赵 蒙

(1.焦作师范高等专科学校理工学院，河南 焦作 454002；2.苏州科技大学 物理科学与技术学院 江苏 苏州 215009)

动态可重构计算包括在同一设备上连续执行一系列算法，其目标是在相同的硬件结构上交换不同的算法，方法是在有限的时间内采用规定的划分和调度，在硬件中多次重新配置现场可编程门阵列(Field Programmable Gate Array，FPGA)[1－3]。对于实时处理，国内外学者已经提出了一些体系结构设计，并验证了动态可重构计算的概念[4－8]。文献[4]提出了一种支持需求驱动的指令集修改的动态指令集计算机(Dynamic Instruction Set Computer，DISC)，采用部分可重构的FPGA 实现，通过将指令模块物理地重新定位到可用的FPGA 空间，从而进一步提高了FPGA 的功能密度；文献[5]描述了FPGA 体系结构及如何解决FPGA 体系结构中存在的逻辑粒度、配置时间、前向兼容性、硬约束和编译时间等问题，并与传统的数字信号处理器、微控制器或通用处理器相结合，实现支持系统的各种计算需求，而不需要定制硬件；文献[6]提出了一种在不影响FPGA动态部分重构性能的情况下，提高FPGA 动态部分重构安全性的解决方案。所提出的解决方案在目标FPGA 上引入了1% 的可用资源开销，实现了2.5 Gbyte/s的重配置吞吐量；文献[7]针对动态可重构系统中相互耦合的划分、调度和布局问题进行了研究，建立了调度和布局的问题模型，提出了相应的优化算法。为了表示动态可重构系统中的任务调度和布局，提出了三元序列组(Triple Sequence)的表示方法。通过求解混合嵌套序列对的最长公共子序列，能够计算出任务位置坐标。将重构序列和任务数据依赖关系相结合，可以构建重构约束图(Reconfigurable Constraints Graph，RCG)来表示动态重构过程中任务的优先约束关系。通过求解重构约束图中到顶点的最长路径，能够计算出任务配置时刻和执行时刻。在动态可重构过程中，任务调度和布局必须满足硬件资源约束和任务数据依赖关系。并给出了可行任务调度和布局的充要条件和可以确立三元序列组完整的可行解空间；文献[8]研究了基于多FPGA 部件的可重构系统高能耗问题。对多FPGA部件可重构系统的特征，包括重构端口受限、资源受限及通信开销等进行了建模，并基于概率论与统计学的离散方差理论，采用负载均衡思想设计和实现了一种低能耗调度算法。结果表明提出的算法复杂度低、运行速度快，不仅节约能量，而且还缩短了最大完成时间；然而，对于运行时间重构(Runtime Reconfiguration，RTR)算法的最优化分解机制仍然有许多需要解决的问题。事实上分析这一领域的研究可以发现，它们仅局限于应用开发方法。我们还注意到:首先，这些方法不能得到最小的空间资源；其次，好的时间分割/划分可以避免所需资源过大[9－10]。

在实现可重构硬件算法的任务中，可以分为2 种方法，如图1 所示。最常见的是应用开发方法，另一种是所谓的系统设计方法。在第一种情形下，必须在现有的由连接到可重构逻辑阵列的主CPU 实现的系统中选择一种具有可选时间约束的算法，这时，最优化实现的目标是使得下列一个或多个指标最小化:处理时间、存储带宽和重新配置的数量；而在第二种情况下，必须在仍处于设计探索阶段的系统上实现一个具有要求时间约束的算法，设计参数是用于实现算法的数据路径部分的逻辑阵列的大小。这时，最优化实现的目标是得到可重构阵列的最小面积。

图1 用于在可重构硬件上实现算法的2 种方法

嵌入式系统可以利用FPGA 的优势，最明显的就是频繁更新数字硬件功能。但是，也可以采用动态资源分配来实例化仅有严格时间要求的每个算子(也称运算符)，这可以通过减少可重构阵列的面积来提高核的效率[11]。

关于RTR 体系结构的时间划分(也称分区或分割)和综合已提出了一些有益的探索[12－16]。这些提出的方法都假设存在资源约束。文献[12]的目标是通过采用数据路径合成工具门阵列编程(Gate ARrays Program，GAMA)[13]和GARP 可重构处理器在C 程序中实现循环的硬件加速；文献[14－15]专为多FPGA 可重构计算架构上的应用开发而设计了一款CAD 工具套件，其中采用的主要成本函数是数据存储带宽；在文献[16]中，作者提出了一种模型和一种方法来利用连续分区中的公共算子，提出的简单模型用于指定、可视化和开发设计，其中包含可以在运行时可重新配置的元素。这种方法可以减少配置时间和应用执行时间，但是需要额外的逻辑资源来完成这种方法。此外，这种模型不包括满足实时性的时序要求，也没有明确实现的分区。

上述研究的目标或者是资源约束，或者是单一的配置时间和应用执行时间约束。实际上，RTR 的划分问题是可重构计算系统中最重要的问题。对此，本文在可重构体系结构设计流程中采用RTR 算法，以使得实现时间约束条件下所需的FPGA 资源最小化，即实现双重任务。

1 问题构建

运行时间重构实时应用的划分可以归类为一个时空问题，因此，必须在时间上对算法进行划分，并在空间上确定每个分区，相比于运行时间重新配置的调度，它是采用动态资源分配的一个时间约束问题。对实时应用作以下假设。首先，算法可以建模为一个无环数据流图(Data-Flow Graph，DFG)，表示为G(V，E)，其中顶点集V＝{O1，O2，…，Om}对应于算术算子和逻辑算子，有向边集E＝{e1，e2，…，ep}表示运算之间的数据依赖关系；其次，对应用设置一个约束时间T，需要解决的问题如下。

对于一个给定的FPGA 系列，必须寻找G的子图集{P1，P2，…，Pn}，使得:

该式允许通过满足时间约束T和通过E建模的数据依赖关系来执行算法，而且需要的FPGA 单元数量最少。所采用的FPGA 单元数量是阵列面积(也称区域)的一个近似值，由式(2)给出:

式中:Pi是n个分区中的一个。一个分区Pi所需的FPGA 资源由式(3)给出:

式中:Mi是分区Pi中的基本算子的数量，Area(Ok)是算子Ok所需的资源数量。

2 划分策略

划分策略的总的流程图如图2 所示，它由3 个主要模块构成。首先，计算出分区(图2 中的模块A、B、C、D)数量的一个近似值，然后得出分区界限(模块E)，最后，在可能的情况下，细化最后的分区(模块E、F)。

图2 分区方法的原理流程图

2.1 分区数量和分区大小

为了减少搜索区域，首先估计可以得到的最小分区数量和在分区中允许的资源数量。为此，使用一个与目标相关的算子库，这个库可以将两个属性关联到图G的每个顶点，这两个属性分别是ti和Area(Oi)，即最大路径延迟和算子Oi需要的基本FPGA 单元的数量，这两个量是要处理的数据大小(位数)的函数。如果知道要处理的原始数据的大小，就很容易通过对输入数据的最大值的图的“软件执行”来得到每个节点的大小。

此外，还作如下假设。

(1)要处理的数据被分组为N个数据的块；

(2)应用于一个块中的每个数据的运算/操作数量是确定的(即不依赖于数据)；

(3)在图的全部节点之间采用管道寄存器；

(4)考虑重构时间由rt(·)给定，它是所采用的FPGA 技术的函数；

(5)忽略读写计数器(指针)和小关联状态机(控制器部分)所需的资源，在本文的应用中，这相当于一个静态部分，实现时将在所需资源总量中考虑到这部分(见第4 节)。

因此，最小运算时间周期tmax为:

而应用所使用的单元总数C为:

式中:{1，…，m}为数据路径G的全部算子的集合。由此得到了由式(6)给出的最小分区数n和由式(7)给出的相应的每个分区的最佳大小Cn(单元数)为:

式中:T是约束时间(单位为s)，N是一个数据块中的数据字数，σ是整个数据路径的总延迟周期数，tmax是DFG 中最慢算子的传播延迟(单位为s)，且它对应于图G的两个连续顶点之间的最大时间(由于是一个完整的流水线过程)，rt()是重构时间。在部分可重构FPGA 技术的情况下，rt()可以用下载的功能单元面积的线性函数来近似。rt()的表达式如下:

式中:V是FPGA 的配置速度(单元/s)，C是执行整个DFG 所需的单元数量。考虑每个重新配置都覆盖了以前的分区(即配置的单元数量等于最大分区大小)，这就保证了先前的配置不会干扰当前的配置；在完全可重构FPGA 技术的情况下，rt()函数是一个依赖于FPGA 大小的常数。这时，rt()是一个按步长增加的离散线性函数，对应于不同大小的FPGA。式(6)的分子是总的允许处理时间(约束时间)，分母的第一项是一个数据块(包含N个数据)的有效处理时间，第二项是加载n个配置所释放的时间(G的总重新配置时间)。

在大多数应用领域如图像处理中，相比于处理时间，可以忽略管道延迟时间的影响(N≫σ)，因此，在部分可重构FPGA 技术的情况下，可以将式(6)近似为式(9)(对应于图2 中的模块D):

由式(9)给出的n值是一个粗略值(最坏的情况)，因为考虑每个分区中存在最慢的算子。

2.2 划分算法

本文提出的划分算法实现的伪代码如下:

算法中采用了一个First＿Leave()函数，它以DFG 作为参数并返回终端节点。通过累加覆盖节点的大小来覆盖从叶子到根的图，直到总和尽可能接近Cn为止。这些覆盖的顶点形成第一个分区，然后从图中删除相应的节点，并反复覆盖，直到剩下的图为空，然后完成划分。

在First＿Leave()函数的执行过程中有很大的自由度，因为DFG 中通常有很多叶子，唯一的强约束是必须作出选择，以确保整个分区的数据依赖性。DFG 的叶子的读出可以是随机的或有序的，在本文的情形下，它是有序的。把G视为一个包含与DFG算子相关的参数的二维表。First＿Leave()是按表的读取顺序执行的，其中包含DFG(从左到右)的算子参数。First＿Leave()函数的第一个目标是创建尽可能均匀的划分，此时，First＿Leave()并不关心存储带宽。

2.3 划分后的改进

在对2.2 划分阶段得到的每个分区进行放置和寻由之后，就可以计算精确的处理时间。还可能要考虑到每个分区的合成频率接近最大处理频率的值。

分析总的处理时间(配置和执行)与约束许可时间之间的差，就可以对分区作出判决。如果有必要减少分区数量或可能增加分区数量，就返回到2.2节中所描述的步骤，并为n提供一个新的值，否则，分区将被视为最佳分区(见图2)。

3 划分策略的应用—图像处理

3.1 算法思想

本节用一个图像处理算法来举例说明本文提出的划分策略，这是验证本文划分策略的一个很好的选择，因为图像处理数据是按块自然组织的，有许多低层的处理算法可以用DFG 建模，而且约束时间通常是图像采集周期。假设图像以25 次/s 的速率拍摄，空间分辨率为512×512 像素，每个像素灰度级为8 位值，这样，就有40 ms 的约束时间。

图像处理采用的算法是一个3×3 的中值滤波器，后面接的是一个边缘检测器，图3 给出了边缘检测器总的原理图。在这个例子中，考虑一个可分离中值滤波器和一个Sobel 算子[17]。中值滤波器提供3 个垂直连续水平中值的中值。每个水平中值只是一条直线中3 个连续像素的中间值。该滤波器可以在保持边缘质量的同时消除脉冲噪声。其实现原理是对3×3 邻域中的像素根据它们的灰度级值进行排序，然后仅使用中间值(在9 个值的第5 个位置上的值)；算子由8 位比较器和多路复用器构成。梯度计算是通过Sobel 算子实现的，这对应于两个一维滤波器连续应用的图像卷积，这些滤波器分别是垂直和水平Sobel 算子。中心像素的最终梯度值是垂直和水平梯度的最大绝对值，线路延迟由FPGA的外部组件造成的(见图3)。

图3 图像边缘检测器的总的原理图

3.2 DFG 注释

本例中使用的FPGA 系列是Atmel AT40K 系列，这些FPGA 的配置速度约为1 365 个单元/ms，并具有部分重新配置模式。通过对Atmel AT40K 系列数据表[18]的分析，可以得到某些算子类型的特征，如表1 所示。在表1 中，Tcell是一个单元的传播延迟，Trouting是算子内的路由延迟，Tsetup是触发器设置时间。根据文献[18]给出的数据表特征，得到对常用初等算子的执行时间的第一次估计，如表2 所示。

表1 AT40K 系列常用算子特征

表2 采用AT40K 技术的一些8 位算子的估计执行时间

在实际应用中，估计执行时间与实际执行时间之间存在线性关系，它将两个连续节点之间所需的寻由时间结合起来，图4 所示为一些已在寄存器之间的FPGA 阵列中分别实现的不同常用低层算子的估计执行时间与实际执行时间的关系。当这些算子在严格的级联中很好地对齐时，这种线性特性会保持得很好。但这种关系对于在FPGA 中的已经硬连接的专门功能是无效的(如RAM 块、乘法器等)。基于图4，可以得到包含在数据路径中的算子的执行时间的近似值。由于算法是规则的如数据路径(严格的算子级联)，所以结果更加精确。

图4 AT40K 技术中一些算子的估计时间和实际执行时间的关系

通过这些估计值，并考虑到处理导致的数据大小的增加，就可以对DFG 进行注释，然后就可以得到全部算子的数量和特征，表3 给出了关于算法示例的数据。在表3 中，执行时间是对实际执行时间的估计。基于这些数据，就得到以最优化方式实现专用数据路径所需的分区数。从表3 和表4 可见，对于边缘检测器来说，在数据路径的全部算子内，最慢的算子是一个8 位比较器，而且必须重新配置467 个单元。因此，根据式(9)(模块D 的结果)，可以得到n的值为3，实现全局数据路径的每个分区(Cn)大小应大约为156 个单元，表4 总结了算法的RTR 实现的估计。通过应用节2 中描述的方法，得到图5 表示的第一个分区(模块E 的结果)。

图5 用于实现图像边缘检测器DFG 的分区

表3 边缘检测器的算子数量和特征(AT40K)

表4 图像边缘检测器的资源估计

3.3 实施结果

为了说明本文的划分方法，我们在Ardoise 体系结构[6]上测试了本文提出的划分策略，该平台由AT40K FPGA 和2 个1 MB 的SRAM 存储器堆构成。尽管本文提出的划分策略并不是针对资源约束这类体系结构的，但根据所使用的资源和工作频率得到的结果对于任何类似于AT40K 的阵列仍然适用。所需要的特性是小的逻辑单元间隔尺寸、每个单元中有一个触发器，以及部分配置的可能性。表5 所示为边缘检测算法(模块F 的结果)的实施结果。从表5 可见，三个步骤中的动态执行是可以实时实现的，这与估计值(见表4)是一致的。

表5 AT40K 边缘检测器的实施结果

可以看到，第四个分区是不可行的(模块E 和F的第二次迭代是不可能的，见图2)，因为允许的最大算子执行时间小于34 ns。事实上，如果分析剩余的时间，会发现一个追加的分区不允许实现实时处理。通过划分的最大单元数量允许确定由运行时间重新配置执行所得到的功能密度增益因子[11]。在本例中，采用功能密度的增益因子与实时处理的该数据路径(静态实现)的全局实现相比大约为3。这个增益的获得没有考虑控制器部分(静态部分)。

显然，最好的解决方案是找到每一步中使用相同的单元数量。但在实际应用中，必须考虑到存储带宽瓶颈，这就是为什么最实用的划分需要保持数据的吞吐量与所使用的存储器的性能一致。

通常，如果有足够的存储带宽，可以采用以下方式来估算控制部分的成本。存储资源必须能够存储2 个图像(假设是一个不变流量处理)，存储大小为256 kbyte，控制器需要2 个计数器来寻址存储器，一个是控制RTR 的状态机，一个用于读写访问的存储器管理。在本文的示例中，控制器由2 个18 位计数器(N＝5122像素)、1 个有5 个状态的状态机、1 个捕获分区数量的4 位寄存器(假设重构数量小于16)、1 个指示分区数量的计数器、1 个4 位比较器和1 个非操作符(以指示必须读写哪些备用缓冲内存)构成。采用有针对性的FPGA 结构，在每个配置阶段的控制器逻辑区域需要49 个逻辑单元的资源数量。如果将控制器区域添加到本文示例所需的资源中，我们将得到209 个单元的计算区域，存储带宽为19 位。

3.4 与一般体系结构综合法的定性比较

将本文提出的策略与一般体系结构综合法相比较，后者是通过加强对算子控制的重用。尽管两种策略的目标都是硬件资源的最小化，但在应用体系结构综合法时，必须针对最大的数据对算子进行量化，即使一个算子不频繁使用，在整个处理期间也必须存在(从而消耗资源)；对于运行时间可重构体系结构，这些缺点不再存在，从而使得逻辑资源增加；此外，与全空间数据路径相比，资源重用可能导致路由延迟增加，从而降低全局架构效率，而利用FPGA的动态资源分配特性，仅在每个时刻(时间局部性)实例化所需算子，并确保算子的相对位置对于当前处理(功能性局部性)是最优的。

4 结束语

本文提出了一种采用动态可重构特征的DFG的时间划分以使FPGA 的阵列大小最小化的划分策略，以在最小面积上的最大允许频率处理和满足实时约束来提高核的效率。除其他步骤外，采用目标FPGA 的特征化(速度和面积)算子库来估计可能的分区数量。通过在一个图像处理算法上的应用和在Ardoise 体系结构上的实际实施，说明了方法的有效性。

对于未来的研究，将致力于更精确的资源估计，考虑数据路径的存储管理部分，并尝试调整First＿Leave()函数来包含存储带宽，实现分区搜索过程的自动化。