RPkNN：基于 OpenCL 的 FPGA 实现的随机投影降维 kNN 算法
摘要
由于所谓的维度灾难以及数据库规模的增加，在执行 k-最近邻(kNN) 算法时，对计算资源和内存带宽的需求不断增长，导致处理大规模数据集变得缓慢。本文提出了一种基于 OpenCL 的框架，用于在现场可编程门阵列(FPGA)上加速 kNN 算法，并利用随机投影降维。所提 RPkNN 框架包含两个实现了基于随机投影和 kNN 算法的吞吐量优化硬件架构的计算模块，以及一个便捷集成这些计算模块的主机程序。RPkNN 还采用了一种针对随机投影和 kNN 算法量身定制的新缓冲方案。该架构支持单一内存通道下的并行 kNN 计算，并利用输入数据的稀疏特性，实现高度优化且并行的随机投影实现。我们使用计算存储设备(CSD)直接访问固态硬盘(NVMe SSD)上的高维数据，并将压缩后、低维的数据存储并重用于 FPGA 动态随机存取存储器(DRAM)，从而消除了对主机 DRAM 的数据传输。我们将 RPkNN 在 Samsung SmartSSD CSD 上的实现与在 Intel Xeon Gold 6154 CPU 上运行的 scikit-learn 库的 kNN 实现进行了比较。实验结果表明，所提出的 RPkNN 解决方案在 SIFT1M 和 GIST1M 数据库的单次 kNN 计算中，分别平均实现了 $26\times $ 和 $46\times $ 的更高性能。最终，RPkNN 比类似的基于 FPGA 的参考方法快 $1.7\times $ 。
作者
Erfan Bank Tavakoli 计算与增强智能学院，亚利桑那州立大学，Tempe，AZ，美国 ORCID: 0000-0002-3248-9301
Amir Beygi 内存解决方案实验室，三星半导体，Inc，San Jose，CA，美国
Xuebin Yao 内存解决方案实验室，三星半导体，Inc，San Jose，CA，美国
出版信息
期刊： IEEE Transactions on Very Large Scale Integration (VLSI) Systems 年份： 2022 卷号： 30 期号： 4 页码： 549-552 DOI： 10.1109/TVLSI.2022.3147743 文章编号： 9714070 ISSN： Print ISSN: 1063-8210, Electronic ISSN: 1557-9999
指标
论文引用： 9 总下载量： 739
关键词
IEEE 关键词： 现场可编程门阵列, 计算机体系结构, 随机存取存储器, 内核, 硬件, 稀疏矩阵, 带宽
索引术语： k最近邻, 随机投影, 降维, 稀疏性, 维数灾难, 随机存取存储器, 数据库大小, 硬件体系结构, 低维数据, 固态硬盘, 存储器带宽, 维空间, 维向量, 距离值, 应用程序编程接口, 距离计算, 随机矩阵, 存储单元, 高层综合, 芯片外存储, 芯片内存, 随机模块, 查询向量
Author Keywords: 可编程门阵列（FPGA），k 最近邻（kNNs），近存储加速，随机投影
未定义
第 I 节 引言
k-最近邻（kNN）算法有广泛的应用，例如图像分类 1 和生物信息学 2，并且是十大最具影响力的数据挖掘算法之一 3。然而，现有的基于 CPU 和 GPU 的 kNN 计算方案由于 CPU 和 GPU 的固定硬件架构及内存层次结构，导致性能受限，使得实现针对算法的定制化数据通路和缓冲方案变得不可能。
现场可编程门阵列（FPGA）的细粒度片上资源可以高效实现针对 kNN 算法的自定义缓冲方案，用于存储输入数据和中间结果 4。FPGA 的可重构性还支持实现细粒度的时序/流水线并行，以解决复杂的循环依赖数据，以提升整体性能 5。迄今为止，已有少量工作在 FPGA 上加速 kNN 算法。然而，它们提出的方案存在非通用性 6 或计算与片外内存访问开销 7、8。
在本简报中，我们提出了 RPkNN，一种基于 OpenCL 的框架，用于加速 FPGA 上的 kNN 算法。所提出的 RPkNN 框架由实现基于随机投影和 kNN 算法的吞吐量优化硬件架构的 FPGA 核心以及实现预处理功能的主机程序组成，用于将输入数据集转换为适配该架构的格式。该端到端框架可实现将计算模块无缝集成到遗留代码中，以加速现有应用。我们采用随机投影以降低数据点的维度，从而缓解维度灾难并降低内存带宽利用率和计算量，同时保持合理的准确性。我们利用三星 Smart 固态硬盘（SSD）计算存储设备（CSD）来降低主机 CPU 的 I/O 带宽负担，并通过直接访问嵌入式 SSD 上的高维数据集，避免向主机动态随机存取存储器（DRAM）的数据传输。
本工作的贡献概括如下：
我们提出了一个端到端的基于 OpenCL 的框架，用于加速 FPGA 上的 kNN 算法，包含一个利用 CSD 近存储特性的 FPGA 设计，以重用压缩且低维度的数据，以及主机程序功能用于预处理原始输入文件。
所提出的硬件架构支持参数化、可扩展且深度流水线化的 FPGA 核心，用于并行 kNN 计算，与单查询搜索场景相比，无需额外的内存带宽和通道。随机投影架构已进一步优化，以考虑其输入数据的稀疏模式，提供高吞吐量和低资源利用率的实现。
提出了一种针对随机投影和 kNN 算法量身定制的新缓冲方案，以利用高带宽的片上内存资源重用从外部存储器加载的数据，从而减少对外部存储器的访问。
我们评估了在 SmartSSD 上实现的 RPkNN 的性能，并将其与运行在 Intel Xeon Gold 6154 CPU 上的 scikit-learn 9（一款最先进的机器学习库）的 kNN 实现进行了比较。实验结果表明，所提出的 RPKNN 解决方案在单次 kNN 计算时，针对不同维度平均分别比 CPU 实现的 SIFT1M 和 GIST1M 的性能高出 26\times 与 46\times。此外，RPKNN 以 1.7\times 的优势超越了基于 FPGA 的参考方法。
SECTION II. 背景与相关工作
A. 背景
数据集由 N 个数据点组成，其中每个数据点用一个 D 维的向量来表示。 kNN 算法包含两个主要步骤：距离计算和前 k 排序。 在距离计算步骤中，查询数据点与数据集（候选数据点）中所有其他数据点之间的欧氏距离被计算，计算和数据访问复杂度为 O(N\times D)。 虽然 L1 范数具有更低的计算复杂度，但它无法捕捉多维空间中数据点之间的距离。 前 k 排序步骤选择上一阶段计算出的前 k 个最小距离，并返回对应候选数据点的索引。 复杂度随向量维度线性增加，凸显了降维的重要性。
在随机投影中，原始 D 维的数据通过将原始数据集乘以一个随机生成的矩阵 R_{D \times L}，投影到更低维度的 L 维空间。
\begin{equation*} X_{N\times L}^{\text {new}}=X_{N\times D}\times R_{D \times L}. \tag{1}\end{equation*}
根据 Johnson–Lindenstrauss 定理 10，随机映射保留了原始高维空间中数据点的欧氏距离。 为实现此功能，R 的元素应为独立同分布（i.i.d.）且均值为零 11。 R 在第 i 行、第 j 列（r_{ij}）的一个元素具有以下分布 12：
\begin{align*} r_{ij}=\sqrt {\frac {S}{L}}\begin{cases} \displaystyle 1, & \text {w.p.} ~1/\left ({2S}\right)\\ \displaystyle 0, & \text {w.p.}~1-1/S\\ \displaystyle -1, & \text {w.p.} ~1/\left ({2S}\right) \end{cases} \tag{2}\end{align*}
其中参数 S 控制投影的稀疏性与准确性的权衡。
B. 相关工作
已有几项工作关注在 FPGA 上加速 kNN 算法。13 中的工作提出了一种基于产品量化的近似最近邻（ANN）搜索方法，适用于高维空间，并使用粗量化器、产品量化器和旋转矩阵的代码本。然而，较大的代码本无法放入片上内存，需要访问片外内存，从而削弱了量化带来的优势。ZipNN 14 是一种近存储加速器，它利用 SSD 的高内部带宽，实施多条应用优化的、线速压缩算法管线，能够处理完整的存储带宽。其应用特定的优化仅适用于特定的数据集集合，缺乏通用性。CHIP-KNN 15 是一种基于高层合成（HLS）的 kNN 加速器，针对拥有多块 DRAM 或高带宽内存（HBM）银行的 FPGA 进行了优化的片外内存访问。其架构的可扩展性严重受限于片外内存通道的数量。
16 中的工作讨论了在 FPGA 上用于维度降低的随机投影。该工作展示了随机投影算法在 FPGA 上硬件实现的高性能和高效率。实现使用线性反馈移位寄存器 (LFSR) 生成随机矩阵，这种做法既耗费资源又不必要。17 中的工作采用低精度数据表示和基于主成分分析 (PCA) 的过滤，以减少对外部存储器的访问。PCA 用于维度降低，并在主处理器上实现，因为在 FPGA 设备上实现 PCA 内核会产生显著的资源开销。因此，主处理器的 I/O 与计算资源在每次使用 kNN 内核时都被占用，数据被反复压缩且没有任何重用。
章节 III. 框架设计
RPkNN 框架由在 FPGA 上运行的核程序和在 CPU 上运行的主机程序组成。实现于 FPGA 加速器上的核代码负责执行计算密集型任务。在主机端，OpenCL 应用程序编程接口 (API) 支持将 kNN 算法的计算卸载到 FPGA 并接收输出。预处理函数将原始输入数据集文件转换为对齐缓冲区（适用于 FPGA DRAM 并针对所提议的硬件架构定制），并向用户提供接口，以请求对多向量进行并行查询搜索。
图 1 显示了在计算存储设备（CSD）上提出的解决方案的整体结构。主机 CPU 以最低的额外延迟、且不影响 SSD 的 I/O 吞吐量与性能，透明地访问非易失性存储器 Express（NVMe）SSD。我们利用从 NVMe SSD 到 FPGA 全局内存（图 1 中的 FPGA DRAM）的直接外围组件互连 Express（PCIe）点对点（P2P）传输来访问未压缩数据。直接 P2P 访问通过消除对主机 DRAM 的数据传输来降低数据传输延迟，从而提升整体应用性能 18。随后 FPGA DRAM 用于缓存低维度和压缩数据。
图 1. RPkNN 的高级块图。灰色块为 FPGA 核心。
FPGA 上的两个主要核心是随机投影模块（RPM）和 kNN 模块（kNNM）。
A. 随机投影模块（RPM）
图 2 显示了 RPM 架构的高级块图，包括 \text {Buf}_{X} 内存和多个稀疏点乘（SpDot）单元。根据 (1)，随机投影需要在随机矩阵 R 与每个数据点的向量 x 之间执行稀疏矩阵向量乘法（SpMV）。SpMV 由 L 个点乘操作组成，每个操作在矩阵 R 的稀疏行与 D 维向量 x 之间进行。为提高吞吐量，L 个 SpDot 单元将并行工作，以同时生成输出向量的所有 L 个元素。我们建议将向量 x 存储在 \text {Buf}_{X} 内存单元中，并在 SpDot 单元之间重用，以减少芯片外内存访问。
图 2. RPM 的高级块图。
由于矩阵 R 是稀疏的，我们使用压缩稀疏行 (CSR) 格式来表示它。CSR 格式使用三个数组 V、COL_INDEX 和 ROW_PTR 来存储非零值、非零元素的列索引以及指向矩阵 R 每行第一个非零元素的指针，分别表示非零值、列索引和指针。根据 (2)，矩阵 R 的元素仅包含三种值：一个零值和两个互补的非零值。因此，我们建议在数组 V 中使用二进制值，其中 0 和 1 分别表示正非零值和负非零值。这导致了非常轻量的通信和高效实现的 SpDot 单元，如图 3 所示。
图 3. SpDot 单元的块图。
B. kNN 模块（kNNM）
图 4 展示了 kNNM 架构的高层模块图，其中包括 \text {Buf}_{C} 存储单元和多个处理单元 (PEs)。该框架支持并行 kNN 查询，适用于多个数据点，由所提出的硬件架构和缓冲方案提供支持，且对内存带宽或整体性能的额外负担几乎为零，相比单个 kNN 查询。PEs 的数量 (P) 等于并行查询的数量。kNNM 首先从 FPGA DRAM 加载 P 个查询向量，并将每个向量发送到一个 PE（如图 4 中蓝色箭头所示）。然后，kNNM 遍历数据集中的所有向量，将每个候选向量存储在 \text {Buf}_{C} 存储单元中，并在所有 PEs 之间共享使用。由于总体数据访问复杂度为 O(N \times D)，我们的方案将每个数据点查询的复杂度降低至 O(N \times D / P)。
图 4. kNNM 的高层模块图.
每个 PE 在给定查询向量上执行 kNN 算法。由于欧氏距离在 top-k 排序步骤中比较，我们提出在不影响精度的情况下避免平方根运算。因此，距离计算单元 (DisCal) 并行地计算两个向量 V_{1} 与 V_{2} 之间的距离为 (V_{1}(1) -V_{2}(1))^{2}+\cdots +(V_{1}(D)-V_{2}(D))^{2}，实现为完全展开的循环，采用 D 个并行减法器和乘法器，并随后以加法树的形式完成，如图 5 所示。由于 DistCal 单元需要对查询向量和候选向量 \text {Buf}_{Q} 与 \text {Buf}_{C} 的片上存储单元进行 D 并行访问，完整循环展开会导致对大 D 值需要大量 LUTRAM 资源，超过可用片上资源。在这种情况下，循环被部分展开以限制存储复制的数量。
图 5. PE 的块图.
The top-k 排序(kSort) 单元使用两个移位寄存器(Val 和 Ind in 5)来跟踪最近 k 个最近候选向量(邻居)的索引和距离值，并按距离值递增排序。当 DistCal 单元计算出新的距离值时，它会从元素 0 开始逐一与已注册的距离值进行比较，直到 k。如果当前距离值小于当前寄存器值，则两个寄存器的当前元素从当前位置向右移位，并用新值更新当前位置的索引和距离，如图 5 所示。
第四节 评估
A. 设置
我们评估 RPkNN 在 kNN 计算中的运行时性能。为评估 RPkNN 框架，我们选择了两个数据集 SIFT1M 和 GIST1M，分别具有 1 M 个数据点，向量尺寸为 128 和 960。我们设计中的数据格式为单精度浮点（32 位）。我们使用 Vitis Unified Software Platform 2019.2 开发并实现了 RPkNN。RPkNN 在 Xilinx KU15P FPGA 设备上的 LUT、FF、DSP 和 BRAM 利用率分别为 30%（156672）、22%（232802）、12%（233）和 34%（333）。
另外，为了在 Intel FPGA 上使用 OpenCL 实现所提出的设计，需要对内核和主机程序代码进行一些小的修改。对于内核代码，可以轻松地将 Xilinx OpenCL 属性替换为对应的 Intel OpenCL pragma。然而，开发者在设置优化的内存结构和配置时，应考虑诸如内存块架构等架构差异。对于主机代码，OpenCL API 接口相似，只需在设置所需依赖项时更新 API 调用。
我们将 RPkNN 与在 CPU 上运行的 scikit-learn 库的优化 kNN 实现进行比较。我们测量了在 Intel Xeon Gold 6154 CPU 上 CPU 实现的性能。我们的工作在三星 SmartSSD CSD 上进行评估。表 I 总结了 CPU 系统和评估中使用的 CSD 的规格。
表 I
B. 实验结果
1) 维度约简评估:
将数据集投影到低维空间可能无法完全保留数据点之间距离的顺序，并在计算 kNN 时引入一些误差。为衡量降维，特别是随机投影对 kNN 算法准确性的影响，我们使用常用指标 Recall@k (R@k)，该指标是查询中 1-最近邻被排在前 k 名的平均比率。
为衡量准确率，我们选择 k=10，因为它是最常用的数值。表 II 和表 III 显示不同降维比例下的 Accuracy 作为 R@k，其比例通过使用随机投影方法对数据集 SIFT1M 和 GIST1M 计算得到 1-L/D。如表 II 和表 III 所示，可以将 SIFT1M 和 GIST1M 的维度（从而尺寸）分别降低 0.625\times 和 0.67\times，同时实现 91% 和 93% 的准确率。
表 II
表 III
2) 性能比较:
表 IV 和 V 分别展示了 RPkNN 在 SIFT1M 和 GIST1M 数据集上的性能比较，比较指标为运行时间（秒），使用不同降维比例以及 P=1 和 P=2 的 CPU 版 kNN 算法。较低的运行时间表示更高的性能。
表 IV
表 V
图 6 与 7 显示了 RPkNN 在对应数据集上相较于 CPU 实现的性能提升。图 6 显示，RPkNN 在 SIFT1M 数据集上平均提升 CPU 实现的性能，提升幅度分别为 26\times 与 49\times，对应 P=1 与 P=2。从一次并行 kNN 查询提升到两次并行查询，几乎呈线性(49/26=1.9\times)加速，且对内存带宽利用率无任何开销。同理，图 7 显示，RPkNN 在 GIST1M 数据集上平均提升 CPU 实现的性能，提升幅度分别为 46\times 与 81\times，对应 P=1 与 P=2。两次并行 kNN 查询同样存在类似的加速（81/46=1.8\times）。
图 6. 在 SIFT1M 数据集上，FPGA 实现的 RPkNN 相比 scikit-learn 的 CPU 实现获得的运行时加速，采用 P=1 与 P=2.
图 7. 在 GIST1M 数据集上，FPGA 实现的 RPkNN 相比 scikit-learn 的 CPU 实现获得的运行时加速，采用 P=1 与 P=2.
为了评估无降维情况下所提出架构的性能，需要将 RPkNN 在 SIFT1M 与 GIST1M 数据集上，分别使用 128 与 960 维时的运行时间，与相应软件实现进行比较。使用 P=1 的 RPkNN 在 SIFT1M 与 GIST1M 数据集上，分别提升软件实现的性能 31\times 与 77\times。
在 19 中类似的基于 FPGA 的工作仅报告了 GIST1M 数据集的执行时间。采用相同数据格式（32 位）时，其运行时间为 64 ms，1.7\times 比 RPkNN（38 ms、93% 准确率及 P=1）慢。此外，我们的方法随着并行度提升，性能几乎呈线性增长。
第 V 节：结论
在本文中，我们提出了 RPkNN，这是一个基于 OpenCL 的框架，利用随机投影加速 FPGA 上的 kNN 算法。RPkNN 包含深度流水线且可扩展的 FPGA 内核，并且主机程序实现了预处理函数，以将原始数据集转换为框架所需的合适格式。基于 Samsung SmartSSD CSD 在两个数据集上的实验结果表明，相比最先进的 CPU 实现，平均性能提高了一个数量级。