oneAPI 并行产品展示中级 C++

加速 FPGA 压缩

Intel

0/5 (0投票)

2020年2月19日

CPOL

14907

在本文中，我们将讨论使用 oneAPI 实现的 Intel GZIP 示例设计，以及它如何帮助使 FPGA 更易于访问。

现场可编程门阵列 (FPGA) 提供了一个灵活的硬件平台，可以在各种工作负载上实现高. 在本文中，我们将讨论使用 oneAPI 实现的 Intel GZIP 示例设计，以及它如何帮助使 FPGA 更易于访问。（关于 oneAPI 的更多信息，请参阅本期特写文章使用 oneAPI 进行异构编程。）

该示例设计实现了 DEFLATE，这是一种无损数据压缩算法，对于许多存储和网络应用程序至关重要。该示例是用 SYCL 编写的，并使用 oneAPI 数据并行 C++ (DPC++) 编译器进行编译，展示了压缩时间显著加速和令人信服的压缩比。

FPGA 的工作原理

FPGA 是可重构设备，由许多低级计算和存储元素（例如，加法器/乘法器、逻辑运算、内存）组成，这些元素结构化为二维阵列并通过可重构布线连接。这些元素可以形成复杂的计算管道和专门的片上内存系统。与为执行通用代码而设计的传统架构相比，FPGA 可以重构以实现定制架构，从而提高目标应用程序的性能。例如，FPGA 可以实现专门的计算管道，可以在每个时钟周期执行整个循环迭代。FPGA 非常适合加速模型，具有片外附加内存（例如 DDR4）以及与主机 CPU 的连接（例如，通过 PCIe）。

DPC++ 编译到 FPGA

DPC++ 编译器的 FPGA 后端生成位流，该位流会为给定代码重新配置 FPGA。SYCL 程序中的每个内核都使用 FPGA 资源的一个子集来实现。所有实现的内核都可以并发执行。

在内核内部，每个循环体都将被翻译成一个深度和专门化的管道，其中包含处理整个循环迭代所需的所有功能单元。条件语句被重构为谓词执行。遍历管道一次即可执行整个循环迭代。

编译器识别可以并行执行的指令，并将它们放置在相同的管道阶段，以便它们可以在任意数量的功能单元上并行执行。此外，它通过确保数据可以被转发来优化管道，以便后续循环迭代尽快（通常在连续的周期内）发布，而不会出现数据冲突（**图 1**）。

1 - 生成的用户代码管道

编译到 FPGA 通常需要几个小时。为了加速开发周期，FPGA 后端附带一个仿真器、静态性能报告和一个动态分析器，以指导优化决策。仿真和静态报告生成只需几分钟而不是几小时，与传统的 RTL 开发流程相比，大大提高了 FPGA 应用程序开发的生产力。

oneAPI 的优势

GZIP 设计充分利用了关键的 oneAPI 编程特性，例如单源设计和多个加速器，以及异构计算，其中加速器运行热点代码，CPU 处理非热点代码。由于该设计是使用 oneAPI 编写的，因此任何了解 C++ 的人都可以编写适合编译到 FPGA 的算法，主要关注算法细节，并将硬件转换留给编译器后端。由于算法是用 C++ 表示的，因此可以轻松测试其功能是否正确。在提交硬件编译之前，可以通过检查报告来预测硬件性能。

示例设计

GZIP 设计的架构遵循 DEFLATE 的数据流。我们创建了三个内核来完成工作

LZ77
Huffman
CRC

我们的第一个内核计算 LZ77 数据，从文件中搜索并消除重复序列。其思想如图 **2** 所示。

2 - LZ77 压缩示例

重复的序列被替换为指向先前出现位置的相对引用。编码引用比原始文本需要更少的存储空间，从而减小了文件大小。

为了找到匹配项，我们需要记住所有已看到的序列，并选择最佳的匹配候选项。序列被替换，匹配过程从当前匹配的末尾开始——或者，如果我们找不到好的匹配，则从下一个符号开始。这比听起来要难。

我们的目标是每个 FPGA 时钟周期处理 16 个字节。因此，在一个时钟周期内，我们需要

**查看我们的历史记录**，为 16 个起始点中的每一个找到最佳匹配
**选择最佳匹配**（或多个不重叠的匹配）
**将结果**写入我们的输出
**将刚刚读取的字符串**存储回字典

这是否可以在不重叠的情况下并行完成并不明显。在知道没有更早的匹配已经覆盖它之前，我们无法选择从给定字节开始的匹配。（我们将在下一节详细介绍这一点。）

第二个内核将 Huffman 编码应用于数据，生成最终的压缩结果。在此步骤中，所有符号和引用都被替换为可变位宽编码，该编码为最频繁的符号提供更少的比特码，进一步减小文件大小。这个步骤如何并行化更容易看出：我们可以有 16 个（或更多）独立的硬件单元，每个单元为给定符号确定 Huffman 码。不过仍然存在一个问题。由于输出是可变长度的，因此我们需要最终将每个输出写入输出流中的正确位置——这意味着我们需要知道所有先前输出的大小。此外，Huffman 码不是字节对齐的，所以我们需要进行大量的位级操作。然而，从根本上说，这是一个比 LZ77 简单的问题，我们在这里不再详细介绍。

最后，第三个内核计算输入数据的 CRC32。这个内核与其他两个内核是独立的，可以并行运行。它在 FPGA 上实现起来也相对简单，因此我们在这里不再详细讨论。

FPGA 优化的 LZ77 实现

为了捕捉数据处理的顺序性，LZ77 编码器被描述为一个具有单个主循环的任务。也就是说，代码描述了一个执行线程，对整个文件逐个符号迭代。创建一组字典来存储数据文件中先前看到的序列。这些字典通过存储数据的哈希值进行索引，类似于哈希表。然而，为了性能起见，最近的（冲突的）条目会覆盖具有相同哈希键的早期条目的字典数据。通过将新看到的输入写入所有字典来更新字典。为了减少字典中冲突的影响，我们将先前看到的序列分在多个不相交的集合中。

我们为什么需要不止一个字典？回想一下，我们想在每个周期处理 16 个字节。这意味着在每个时钟周期将 16 个字符串（每个字符串从一个字节开始）存储到字典中并执行 16 次哈希查找。每个 FPGA 内存块只有两个端口。为了允许所有这些并发访问，我们创建了 16 个独立的内存系统，每个内存系统存储不同位置的字符串。现在我们的历史记录分布在 16 个字典中，因此我们的 16 次哈希查找中的每一次都需要在 16 个不同的字典中完成——总共 256 次查找。这似乎只是让问题变得更糟。

我们可以通过构建每个字典的 16 个副本（总共 256 个字典）来解决这个问题。所有这些字典都使用了 FPGA 片上内存的大部分，但我们已经实现了在每个时钟周期执行 16 次哈希查找和写入的目标。**图 3** 展示了如果我们只想在每个时钟周期处理四个字节所需的字典结构的示例。（顺便说一句，分配给字典的 FPGA 区域是我们无法在每个周期处理超过 16 个字节的主要限制。）

3 - 用于四字节并行访问的字典复制

表达并行行为可能很棘手。但实际上，编译器会自动识别查找之间的数据并行性。也就是说，代码将生成专门的 FPGA 逻辑，能够并发执行所有字典查找。在代码中，VEC 是每周期处理的字节数，LEN 是字符串的长度。在示例设计中，两者都设置为 16。我们使用了模板元编程（展开器）来复制内部函数中所有 i 和 j 的代码。所有查找的数据在同一个管道中作为类似规约的操作进行聚合。

我们的字典解决了其中一个问题，但如果我们想在每个时钟周期完成一个完整的循环迭代，还有很多其他处理工作要做。幸运的是，我们不需要。FPGA 编译器会自动流水线处理数据通路。因此，在循环的迭代 0 完成从字典读取后，迭代 1 可以开始，而迭代 0 可以开始选择最佳匹配。匹配选择可以在多个周期内分阶段进行，每个阶段处理循环的不同迭代。

在生成输出时，最后一个挑战是如何正确考虑匹配对后续匹配的影响。一旦识别出匹配项，就必须忽略重叠的匹配项。在我们的 `single_task` 代码表示中，这表现为一个循环相关的变量，在后续循环迭代可以继续之前需要计算它。如果计算过于复杂，可能会限制 FPGA 的时钟速度，或限制我们在每个时钟周期完成循环迭代的能力。

因为我们以 FPGA 为目标，所以我们可以自定义硬件来优化此依赖项的处理。我们通过最小化依赖于它的计算量来简化数据风险。例如，我们选择推测性地执行哈希查找，确定所有可能的匹配项，即使这些查找与重叠匹配相关。我们稍后只需修剪重叠的匹配项。FPGA 后端优化了所需的前向逻辑，完全避免了数据风险。**图 4** 演示了推测性匹配的修剪。

4 - 修剪推测性匹配，考虑了前一个循环迭代中确定的匹配、当前循环迭代中的重叠匹配以及质量差的匹配

任务级并行

为了压缩文件，三个处理内核由主机 CPU 异步提交。它们可以在 FPGA 硬件中并发运行。它们的运行速度略有不同，CRC 更快。LZ77 生成 Huffman 内核所需的数据。为了避免额外的延迟，并避免通过片外内存传输数据，我们使用了内核间通信管道，这是 SYCL 语言的一个提议的 Intel 扩展。如**图 5** 所示，此扩展允许不同的内核按顺序交换数据，而无需写入片外内存。