Page 79 - 《软件学报》2026年第3期

1042 软件学报 2026 年第 37 卷第 3 期

广度优先搜索以扩展聚类簇范围, 形成分区内的局部聚类结果 (第 3.3.1 节). 最后, 基于核心近邻图进行局部聚类
簇合并, 形成最终的聚类结果 (第 3.3.2 节).

K-means
树分区 Tensor 核心加速

向量数据集 K-means 树 分区结果 聚类结果
Tensor 核心增强的层间并行 K-means 树分区 (ֻ3.2ࢫ) 聚类簇
K 近邻图 分区局部 合并
索引构建 并行聚类 核心近邻图

GPU 并行偏好采样
近邻查询
加速
×
×
×
GPU 并行距离计算 K 近邻图索引 并行广度优先遍历 局部聚类结果
GPU 加速的 K 近邻图索引构建 (ֻ3.1ࢫ) 基于广度优先搜索和核心近邻图的并行聚类 (ֻ3.3ࢫ)
图 2 GPU 加速的高维向量聚类算法

3.1 GPU 加速的 K 近邻图索引构建
根据第 2.2 节的讨论, K 近邻图可作为 DBSCAN 算法的索引, 并显著加速聚类过程中开销最高的近邻计算.
为此, 本节首先进行 K 近邻图的构建. 然而, 现有的 K 近邻图构建算法普遍基于 CPU, 其在处理大规模高维向量
时面临严重的效率瓶颈 [22,48] . 为了突破 K 近邻图构建的效率瓶颈, 本文基于 NN-Descent [48] 算法提出 GPU 加速的
K 近邻图并行计算优化框架, 以适配 GPU 高并发的计算特性.
NN-Descent 算法采用“邻居的邻居也可能是邻居”的思想, 首先随机初始化 K 近邻图, 而后图中每个节点对其
二阶邻居进行随机采样, 并以相同的方式对该节点反向邻居的二阶邻居也进行随机采样, 计算与其采样得到的二
阶邻居的距离, 而后将计算得到的距离和该节点与当前邻居的距离进行比较, 将距离更小的二阶邻居更新为其直
接邻居. 同时, 按照相同的方式根据距离由小到大更新该节点的反向邻居. NN-Descent 算法基于 CPU 架构设计,
未考虑大规模并行计算. 为了使用 GPU 加速 NN-Descent 算法, 如图 3 所示, 本文提出的 GPU 加速的 K 近邻图索
引构建算法将 NN-Descent 组织为 4 个阶段: 采样、去重、距离计算和邻居更新. 算法以近邻图节点为独立计算单
元, 将复杂邻居计算解耦, 各节点分配至 GPU 的各线程块内计算, 消除了同步代价.

1 2 3 5 6 7 9 10 9 8 4 12
4 6 线程组 1 候选点数组 向量 0 的邻居列表
2 7
线程组 2
5 10 2 7 5 3 6 2 1 9 1 2 3 5 6 7 9 3 8 4 9 5 3 2 1 2 4 6 7
0 并行双调排序 候选点距离 邻居列表向量距离
线程组 1 9 1 向量化访存 向量 1
6 的值 邻居更新 (候选点数组
3 12 1 2 2 3 5 6 7 9 向量数据集 和邻居列表按距离归并)
8 向量 0
K 近邻图 的值 10 9 1 7 8
并行去重 __shuf_sync( ) 更新后的邻居列表
2 7 5 3 6 2 1 9 1 2 3 5 6 7 9 3 8 4 9 5 3 2 1 2 3 3 4
二阶邻居样本 二阶反向邻居样本 候选点数组 候选点与向量 0 的距离 更新后的距离
(1) 采样 (2) 去重 (3) 距离计算 (4) 邻居更新
图 3 GPU 加速的 K 近邻图索引构建算法流程

(1) 采样. 与 NN-Descent 根据“邻居的邻居也有可能是邻居”的思想而采用的随机采样方法不同, 本文基于“最
近邻的邻居更有可能是邻居”的思想设计了最近邻偏好采样策略, 以提高采样质量并减小计算代价. 线程块内的线
程首先以线程组的形式并行对各节点的前 M 个最近邻的邻居节点实施采样, 而后采用同样的方式对反向邻居的
二阶邻居实施采样, 最终合并采样结果构建采样节点集. 为了节省 GPU 显存开销, 并保证后续对采样节点访问的