【赛灵思中国通讯】55期：尝试通过算法重构和Vivado HLS生成高效的处理流水线

通过用于重构高级算法描述的简单流程，就可以利用高层次综合功能生成更高效的处理流水线。

如果您正在努力开发计算内核，而且采用常规内存访问模式，并且循环迭代间的并行性比较容易提取，这时，Vivado设计套件高层次综合(HLS)工 具是创建高性能加速器的极好资源。通过向C语言高级算法描述中添加一些编译指示，就可以在赛灵思FPGA上快速实现高吞吐量的处理引擎。结合使用软件管理 的DMA机制，就可以比通用处理器提速数十倍。

然而，实际应用中经常会遇到难以处理的复杂内存访问问题，尤其是当突破科学计算和信号处理算法领域时更是如此。我们设计出了一种简单方法，可供您在 此类情况下生成高效的处理流水线。在详细介绍之前，我们首先了解一下Vivado HLS的工作原理，更重要的是了解它何时不起作用。

HLS工具如何起作用?

高层次综合功能试图获取由高级语言描述的控制数据流图 (CDFG)中的并行性。对计算操作和内存访问进行分配和调度时，应根据它们之间的依赖约束和目标平台的资源约束来执行。电路中特定操作的激活与某个时钟 周期相关，同时，沿数据路径综合的中央控制器协调整个CDFG的执行。

单纯在内核上应用HLS可以建立一条具有众多指令级并行性的数据路径。但是当它被激活时，就需要频繁停下来等待数据送入。

由于调度工作是在静态下完成的， 因此加速器运行时间的行为相当简单。所生成电路的不同部分相互之间以相同步调运行;并不需要动态的相关性检查机制，例如高性能CPU上出现的那种。例如， 在图1(a) 所示的函数中，循环索引添加和curInd的加载可以并行处理。此外，下次迭代可以在当前迭代完成前开始。

同时，由于浮点乘法通常使用上次迭代的乘法结果

因此可以开始新迭代的最短间隔受到浮点乘法器时延的限制。该函数的执行调度如图2(a)所示。

该方案何时达不到理想效果?

这种方案的问题在于整个数据流图严格按调度运行。片外通信产生的拖延会传播到整个处理引擎，从而导致性能大幅下降。当内存访问模式已知，数据能在需 要使用之前移动到芯片上，或者如果数据集足够小，则可完全高速缓存在FPGA上，这类情况下不会有问题。然而，就很多有趣的算法而言，数据访问取决于计算 结果，而且内存占用决定了需要使用片外RAM。现在，在内核上单纯应用HLS可建立一条具有众多指令级并行性的数据路径。但是，当它被激活时，就需要频繁 停下来等待数据送入。

图2(b)给出了针对实例函数生成的硬件模块的执行情况，此时数据集太大，需要动态送入片上高速缓存。注意减速程度如何反映所有高速缓存缺失时延的 综合影响。不过，情况并非一定如此，因为计算图中有些部分的进展不需要立即提供内存数据。这些部分应该可以向前移动。执行调度中这点额外自由度有可能产生 显著影响，就像我们看到的那样。

重构/解耦实例

我们看一下刚才的实例函数。假设浮点乘法的执行和数据访问没有全部由统一的安排联系在一起。当一个负载运算符等待数据返回时，另一个负载运算符可以 开始新的内存请求，乘法器的执行也能向前移动。为达到此目的，每项内存访问都应该由一个模块来负责，并按各自的调度运行。此外，乘法器单元应该与所有内存 操作异步执行。

不同模块间的数据相关性

通过硬件FIFO来通信。对于我们的实例而言，可能的重构形式如图1(b)所示。用于各阶段之间通信的硬件队列可以缓冲已经取回但尚未使用的数据。 当内存访问部件因高速缓存缺失而出现拖延时，当前已产生的积压数据还可以继续供乘法器单元使用。在经历较长时间后，形成的拖延时间会被浮点乘法的长时延掩 盖。

图2(c)给出了使用解耦处理流水线时的执行调度。这里，通过FIFO的时延没有考虑在内，不过如果迭代量很大，该时延的影响会达到最小。

我们如何进行重构?

为了给解耦处理模块生成流水线，首先需要将初始CDFG中的指令进行组合以构成子图。为使所得的实现方案性能最大化，聚类方法必须满足几个要求。

首先，正如我们之前所见，Vivado HLS工具在前面的迭代完成之前使用软件流水线发起新的迭代。CDFG中最长循环依赖的时延决定可发起新迭代的最小间隔，最终会限制加速器所能实现的总吞 吐量。因此，很重要的一点在于这些依赖循环不能遍历多个子图，例如用于模块间通信的FIFO总是会增加时延。

其次，应该将内存操作与涉及长时延计算的依赖循环分开，这样高速缓存缺失就会被慢速的数据处理所“掩盖”。在这里，“长时延”是指操作需要一个周期以上的时间才能完成;在这里，我们使用Vivado HLS调度来获取这一指标。例如，乘法是长时延操作，而整数加法不是。

最后，为了将高速缓存缺失引起的拖延影响限定在局部范围内，您需要将每个子图中的内存操作数量减至最少，尤其是在需要寻址存储空间中的不同部分时更是如此。

第一个要求——防止依赖循环遍历多个子图——很容易满足，只需要找到原始数据流图中的强连通分量(SCC)，并在将它们分为不同集群之前将其打开变成节点。这样，我们就得到一个有向的非循环图，其中有些节点是简单指令，其它则为一组相关的操作。

要满足第二和第三个要求，即分离内存操作和局部化拖延的影响，我们可以对这些节点进行拓扑排序，然后将它们分区。最简单的分区方法是在每个内存操作 或长时延SCC节点后画一条“边界”。图3展示了如何将此方案应用于我们的实例。集群与图1中流水线结构之间的对应关系应该做到显而易见。每个子图都是一 个新的C函数，可独立通过HLS推送。这些子图在执行时相互间的步调并不一致。