推动 OpenCL™ 在 FPGA 上的发展

现场可编程门阵列（FPGA）具有非常高的性能，尤其是功耗性能。这也许并不令人惊讶。毕竟，FPGA硬件本身是可塑的——可配置以匹配应用程序，而不是反过来。同样令人惊讶的是，这种额外的自由度——应用程序开发人员可以同时更改硬件和软件——应该会增加应用程序开发工作流程中各个方面的复杂性。

事实上，情况确实如此。直到最近，大多数FPGA应用程序的开发人员都依赖于与硬件设计师而非软件程序员所使用的工具和方法更为相似的工具和方法。使用的语言是硬件描述语言（HDL），如Verilog*和VHDL*。它们描述的是逻辑的性质，而不是指令流。编译时间（称为综合）非常长。并且需要相当多的系统知识，尤其是在调试和测试方面。

这一切现在都正在改变。英特尔（Intel）创建了Intel® FPGA SDK for OpenCL™技术¹，它提供了HDL编程的替代方案。该技术和相关工具属于一类称为高级综合（HLS）的技术，它使得设计能够以更高的抽象级别进行表达。Intel FPGA SDK for OpenCL技术现已得到广泛应用。对于长期的FPGA应用程序开发人员来说，令人惊讶的是，所实现的性能常常接近甚至优于HDL代码。但似乎也显而易见，要实现这种性能，往往仅限于那些已经知道C到硬件转换工作原理的开发人员，以及拥有内部优化方法工具集的开发人员。

在波士顿大学，我们致力于枚举、表征和系统化一个这样的优化工具集。已经有很多关于FPGA OpenCL的最佳实践文档。这项工作在很大程度上通过应用高性能计算（HPC）社区2已经熟知的其他方法来补充它们。在这种方法论中，我们相信我们走在正确的道路上。HPC性能编程已经花费了几十年才达到目前精密的水平。我们不应该对Intel FPGA SDK for OpenCL技术用户需要遵循类似的路径和学习曲线感到惊讶。

请注意，您可以在文章末尾的参考文献3和4中看到此处所述工作的更多细节。第一篇使用FFT作为详细的案例研究。第二篇描述了经验引导的优化框架。另外，在相关工作中，参考文献5和6展示了我们如何增强工具流程，该工具流程可用于在不生成整个系统的硬件的情况下测试/验证设计功能和性能。因此，我们可以更准确地识别设计瓶颈和优化影响，从而实现快速周转。**图1**展示了这些部分如何与现有工具流程结合。

经验引导的代码优化

我们提出了一系列系统化和经验引导的代码优化方法，用于OpenCL，以补充当前最佳实践并显著提高性能。我们的工作对所有这些优化的影响进行了表征和测量。这不仅使程序员能够遵循脚本来优化自己的内核，而且为开发自动调优器来自动执行优化开辟了道路。

我们将代码优化广泛地分为三类

1. 英特尔的最佳实践（IBP）
2. 通用代码优化（UCO）
3. FPGA特定优化（FSO）

IBP是在Intel最佳实践指南7中给出的设计策略，它展示了如何使用OpenCL语义表达硬件。我们将它们与UCO和FSO分开，因为IBP对于FPGA OpenCL社区来说是众所周知的，并且已经有几项研究对其行为进行了表征。

UCO由一般的程序优化方法组成，在很大程度上与计算平台无关，例如

• 使用一维数组
• 数组记录
• 谓词
• 循环合并
• 标量替换
• 预计算常量

虽然已作描述（例如，在参考文献2中），但它们在IBP文档中基本缺失。FSO由一系列FPGA特定优化组成，通常补充IBP。它们基于

• **获取**IBP中未找到的特定FPGA映射
• **IBP中陈述的事实，但我们已加以利用并转化为优化
• **通常**使用的（我们发现）实际上应该避免的做法

有七个代码版本，在参考文献4和6中详细讨论，它们是逐步开发的。每个版本都包含一个或多个已应用的优化。**表1**总结了优化及其类型（IBP、FSO和/或UCO）。

表1. 代码版本和优化总结

版本	优化	类型
0	（用于移植到FPGA OpenCL的GPU代码）	—
1	带缓存优化的单线程代码	IBP, FSO
2	在单独的内核中实现任务并行计算，并使用通道连接它们	IBP
	使用#pragma unroll完全展开所有循环	IBP, UCO
	最小化计算循环外部的变量声明（尽可能使用临时变量）	IBP, UCO
	使用常量作为问题大小和数据值（而不是依赖于片外内存访问）	IBP, FSO, UCO
	合并内存操作	IBP, UCO
3	在单个内核中实现整个计算，避免使用通道	FSO
4	减小数组大小，以便将流水线寄存器推断为寄存器而不是BRAM	FSO
5	详细执行计算，使用临时变量存储中间结果	FSO, UCO
6	当定义数据路径中的分叉时，使用谓词而不是条件分支语句	FSO, UCO

版本0：次优基线代码

一个流行的起点（例如，在参考文献8中）是基于多个工作项（MWI）的内核，这对于GPU来说是合适的。从这里开始的优点包括易于利用SIMD和计算单元复制（CUR）的数据并行性，而CUR仅限于MWI结构。

算法1展示了一个V0类型的内核（基于参考文献9）。核心操作是使用第一行和第一列的已知值填充矩阵。每个未知条目是根据其左、上和左上位置的值计算的。这是通过按顺序遍历所有矩阵条目的循环来实现的。max函数使用“if-else”语句实现。在算法1中，SIZE代表正在处理的矩阵条目块的维度。

算法1. Needleman Wunsch-V0

版本1：首选基线代码（用作参考）

一个不那么直观但更受欢迎的替代方案是使用（作为基线）单线程CPU代码。特别是，初始设计应实现为IBP推荐的单工作项（SWI）内核。SWI内核可以有效地推断和利用所有形式的并行性，并且比MWI内核更有效。CPU风格的基线代码也应该针对缓存性能进行优化。这

• **有助于**编译器推断并行流水线之间的连接（即，数据是否可能直接在流水线之间传输，而不是存储在内存中）
• **提高**片上数据访问的带宽
• **高效利用**负责片外内存事务的内部加载存储单元缓存

**算法2**展示了首选基线内核。矩阵的第一行和第一列分别是向量A和向量B。

算法2. Needleman Wunsch-V1

版本2：IBP

给定首选的基线代码，我们然后应用以下常用的IBP

• 多任务并行内核
• 完全展开所有循环
• 最小化状态寄存器使用
• 常量数组
• 合并

算法3展示了应用IBP后的Needleman Wunsch内核结构。并行性通过 systolic array 来利用，每个处理单元（PE）实现为单独的内核。通道用于将PE以指定的顺序连接起来。对于每个内部循环迭代，PE在同一行中计算连续的列。这保证了内存事务的空间局部性。缺点是内核之间存在数据依赖，编译器无法可靠地打破这些依赖，因为它将每个内核视为独立实体进行优化。因此，数据路径同步的开销可能导致性能下降。

算法3. Needleman Wunsch-V2

版本3：单内核设计

在版本3中，我们将经过IBP优化的任务并行内核合并，并将所有计算循环声明在同一个内核中。这是因为编译器仍然能够自动推断任务并行流水线。与多内核方法相比，单个内核具有许多优点，例如

• **固有的**全局同步
• **通过流水线合并/重排序减少**资源使用和延迟
• **简化的**控制逻辑

**算法4**展示了将systolic array实现为单个内核的内核结构。现在编译器可以优化整个计算，而不是单个PE。同步开销也减少了，因为几乎所有计算都与单个循环变量（j）相关联。使用了嵌套循环，因为在这种特定情况下，启动间隔的成本低于资源使用的减少。这是因为编译器在循环合并时无法推断数据访问模式。

算法4. Needleman Wunsch-V3

版本4：减小数组大小

大型变量数组会导致流水线寄存器被推断为BRAM而不是寄存器，这可能对设计产生重大不利影响。由于BRAM无法像寄存器那样以相同的吞吐量进行数据输入和输出，因此需要移位寄存器和内存复制。这极大地增加了资源使用。此外，编译器还无法启动计算循环的无中断迭代，因为存在内存依赖。解决方案是将大型数组（对应于中间变量）分解为更小的数组。

**算法5**展示了将流水线寄存器推断为寄存器的内核结构。所有数组都表示为单个变量，通过脚本生成，但存储在“left”中的向量B的本地存储除外，因为它的吞吐量要求较低。

算法5. Needleman Wunsch-V4

版本5：详细计算

OpenCL编译器不能可靠地将分配给单个变量的大型计算分解为中间阶段。这减少了可能的流水线阶段数量，并可能导致更大的关键路径和数据依赖停顿。我们的解决方案是通过使用中间变量将计算尽可能详细地进行，以帮助编译器推断流水线。如果逻辑已经最优，这些变量将被综合掉，不会浪费资源。

**算法6**展示了在执行详细计算并添加了许多中间变量后的内核结构。“max”函数也显式实现。

算法6. Needleman Wunsch-V5

版本6：谓词

我们通过显式指定确保计算有效性的架构状态来优化条件操作。由于硬件是持久的，并且一旦综合就始终存在，因此我们避免使用条件分支语句。相反，变量值被条件性地赋值，使得无效操作的输出不会被提交，从而不会影响整体结果。**算法7**展示了用条件赋值替换的“if-else”操作。

算法7. Needleman Wunsch-V6

硬件规格

这些设计使用Intel® Arria® 10AX115H3F34I2SG FPGA和Intel® FPGA SDK for OpenCL™技术16.0实现。该FPGA拥有427,200个ALM，1506K逻辑单元，1518个DSP块，以及53 MB的片上存储。对于GPU实现，我们使用NVIDIA Tesla* P100 PCIe 12GB GPU和CUDA* 8.0。它拥有3,584个CUDA核心，峰值带宽为549 GB/s。CPU代码在14核、2.4 GHz的Intel® Xeon® E5-2680v4处理器上使用Intel® C++ Compiler v16.0.1实现。

优化表征

使用以下基准测试对完整的OpenCL编译流程进行了优化测试

• Needleman Wunsch (NW)
• 快速傅里叶变换（FFT）
• 范围限制分子动力学（Range Limited）
• 粒子网格Ewald（PME）
• 稠密矩阵-矩阵乘法（MMM）
• 稀疏矩阵稠密向量乘法（SpMV）和循环冗余校验（CRC）

**表2**提供了这些基准测试、它们的关联矮人8、测试问题大小以及开发的代码版本的摘要。

表2. 基准测试摘要

基准测试	矮人	问题大小	V1	V2	V3	V4	V5	V6
NW	动态编程	16K x 16K整数表	•	•	•	•	•	•
FFT	谱方法	64点Radix-2 1D FFT，8,192个向量	•	•	•	•	•	•
范围限制	N体	每单元180个粒子，15%通过率	•	•	•	•	•	•
PME	结构化网格	1,000,000个粒子，323个网格，3D三三次	•	•	•			•
MMM	稠密线性代数	1K x 1K矩阵，单精度	•	•			•	•
SpMV	稀疏线性代数	1K x 1K矩阵，单精度，5%稀疏度，NZ=51,122	•	•	•		•	•
CRC	组合逻辑	100 MB CRC32	•	•	•		•	•

**图2**显示了各个优化的结果。在几乎所有情况下，我们都可以看到相同的趋势，即传统的优化（V2）只能实现部分加速。通过在V2的基础上应用其他优化，性能可以提高几个数量级。

**图3**显示了各个优化平均影响。通常，每个连续应用的一组优化都会带来性能的提高。例外的是V5。这是因为V5在NW和SpMV上的执行时间较长。在这两种情况下，尽可能详细地进行计算会导致使用条件语句，这抵消了优化的好处。一旦在V6中删除了这些语句，加速就会提高。

为了证明该方法的整体有效性，我们将优化内核的性能与现有的CPU、GPU、Verilog和FPGA-OpenCL实现进行了比较。**表3**列出了这些设计的参考文献。它们要么来自文献，要么使用可用的源代码/库（用星号*表示）实现。参考3中的Verilog FFT测量已扩展为包括片外访问开销。

表3. 现有实现参考文献

基准测试	CPU	GPU	Verilog*	OpenCL™
NW	Rodinia*9	Rodinia*9	Benkrid*10	Zohouri*11
FFT	MKL*12	cuFFT**13	Sanaullah*3	Intel14
范围限制	—	—	Yang*15	Yang15
PME	Ferit16	Ferit*16	Sanaullah17	—
MMM	MKL*12	cuBLAS*18	Shen*19	Spector*20
SpMV	MKL*12	cuSPARSE*18	Zhou*22	OpenDwarfs*8
CRC	Brumme*23	—	Anand*24	OpenDwarfs8

**图4**显示了相对于CPU代码的平均加速比，而**图5**显示了所有实现的总化执行时间。从结果中，我们观察到我们的工作由于使用了Intel® Math Kernel Library (Intel® MKL)编写的代码的性能，比多核CPU实现平均快约1.2倍。我们还实现了比现有FPGA OpenCL工作平均低约5倍的执行时间。与我们的工作相比，GPU的2.4倍加速比是由于使用了高端GPU（Tesla* P100）而不是中端FPGA（Intel® Arria® 10 FPGA）。因此，我们还通过保守的4倍因子对Stratix 10使用的高端FPGA性能进行了估算，以考虑资源增加。结果显示，Stratix 10上的优化内核预计平均比GPU设计快65%。

结论

与现有的Verilog*实现相比，OpenCL内核平均而言，与手动优化的HDL相差12%。这表明优化能够弥合FPGA的性能-可编程性差距，并使用OpenCL提供HDL级别的性能。