Accelerating kNN search in high dimensional datasets on FPGA by reducing external memory access
Accelerating kNN search in high dimensional datasets on FPGA by reducing external memory access
复制标题
DOI：
10.1016/j.future.2022.07.009
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Xiaojia Song;Tao Xie;Stephen Fischer
中科院分区：
文献类型：
--
作者：
Xiaojia Song;Tao Xie;Stephen Fischer
在 FPGA 上实现高效的 k 最近邻 (kNN) 算法变得越来越具有挑战性，因为 kNN 处理的数据集的大小和维数都在快速增长，这使得外部存储器访问成为性能瓶颈。为了减少瓶颈的影响，在本文中，我们通过采用低精度数据表示（LPDR）和基于主成分分析的过滤（PCAF）两种数据访问减少方法，在FPGA上通过高级综合（HLS）实现了两个kNN内核。一个内核称为 MBFS-kNN（内存高效暴力搜索 kNN），另一个内核称为 MPCAF-kNN（内存高效 PCAF kNN）。这两个内核自适应所有关键参数。通过将它们与高端 CPU 服务器上的两个最先进的 kNN 实现、FPGA 上现有的 BFS-kNN 内核以及 GPU 上现有的 BFS-kNN 内核进行比较，我们的实验结果表明，这两个内核通过大大减少外部内存访问而显着提高了性能。
Implementing an efficient k-Nearest Neighbors (kNN) algorithm on FPGA is becoming challenging due to the fact that both the size and dimensionality of datasets that kNN is working on have been rapidly growing, which makes external memory-access a performance bottleneck. To reduce the impact of the bottleneck, in this paper we implement two kNN kernels through high-level synthesis (HLS) on FPGA by employing two data access reduction methods: low-precision data representation (LPDR) and principal component analysis based filtering (PCAF). One kernel is called MBFS-kNN (Memory-efficient Brute-Force Searching kNN) and the other is called MPCAF-kNN (Memory-efficient PCAF kNN). The two kernels are adaptive to all key parameters. By comparing them with two state-of-the-art kNN implementations on a high-end CPU server, an existing BFS-kNN kernel on FPGA, and an existing BFS-kNN kernel on GPU, our experimental results show that the two kernels substantially improve the performance by greatly reducing external memory-accesses.