近日，2020级博士生刘超强（导师廖小飞教授）的论文“FNNG: A High-Performance FPGA-based Accelerator for K-Nearest Neighbor Graph Construction”被FPGA领域国际会议（The 31^th ACM/SIGDA International Symposium on Field-Programmable Gate Arrays，FPGA 2023）录用。

K最近邻图是许多应用的关键数据结构，然而在大型数据集上构建 K最近邻图非常耗时。过去学术界提出了许多K最近邻图构建算法，并且最近有工作使用GPU来加速 K最近邻图的构建，但是现有方案的图构建过程中仍然存在大量的内存访问和计算开销。为此，论文首先提出了基于块的调度机制，以充分利用块内顶点的数据局部性从而减少内存访问次数，具体做法是将空间上相近的顶点划分为块，在构建过程中按照块的粒度对顶点进行处理。其次，提出了无用计算提前中止技术，构建过程中大部分向量计算可以在计算部分维度之后提前中止，从而减少大量计算开销。最后，设计了高效的FPGA加速器架构以充分利用上述优化。实验结果表明，相比于现有CPU方案和GPU方案，该工作构建出相同精度的K最近邻图所需时间分别减少了190倍和2倍。。

FPGA会议于1993年创建，每年举办一次，旨在展现与FPGA技术相关的所有领域的最新进展。本届会议共收到82篇投稿，共录用23篇论文，录取率为28%。

（通讯员：刘超强）