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

李忠根 等: GPU 加速的高维向量聚类算法 1043

高效性, 采样节点集将被存储于 GPU 线程块的共享内存中.
(2) 去重. 由于采样所得节点不可避免地存在重复, 故需对采样节点进行去重, 以保证最终邻居列表各节点的
唯一性. 为了充分发挥 GPU 的大规模并行计算能力, 本文采用线程块内的并行双调排序算法 [49] . 该算法通过若干
O(logn). 形成有序序列后, 为序列中各元素分
次并行的两两元素比较与交换, 最终输出有序序列, 其时间复杂度为
配一个线程, 各线程判断该元素与其前一个元素是否相同, 若不同则写入位于共享内存中的候选点数组.
(3) 距离计算. NN-Descent 原算法中节点间距离计算由单线程串行累加各维度距离完成, 这种计算方式难以
充分利用 GPU 中的全部线程. 为了加速距离计算操作, 本文设计了面向 GPU 的高并发距离计算函数. 线程块中的
线程并行计算候选点与该线程块所在点的距离. 针对高维向量特性, 本文采用线程组协作计算每个点对的距离. 在
计算过程中, 为了加速数据访问, 采用向量化访存技术, 各线程一次加载多个操作数, 线程块所在点的数值加载至
共享内存, 为所有线程组共享, 各线程组负责的候选点数值则加载至寄存器. 线程组中各线程计算得到局部维度的
距离后, 使用 CUDA 的线程间通信函数__shuf_sync() 实现线程间的数据交换, 进而将各线程计算结果归并得到最
终距离. 线程间通信函数的使用避免了额外的内存访问, 进而提高了距离归约的效率. 最后, 为了进一步减小后续
邻居更新的开销, 将计算得到的距离与线程块所在点当前邻居列表中的最大距离进行比较, 由于大于最大距离的
候选点必定不会在更新阶段作为所在点的邻居, 因此仅保留小于最大距离的候选点.
(4) 邻居更新. 首先采用并行双调排序算法将候选点按距离进行排序, 随后将现有邻居列表与候选点数组按照
距离进行归并, 保留前 k 个数据点, 并确保最终形成的邻居列表的有序性. 在邻居列表更新后, 需同步更新反向邻
居, 以提高 K 近邻图的构建精度. 在 NN-Descent 原算法中, 可动态申请存放反向邻居的内存, 最后将所有更新的
反向邻居与当前反向邻居进行完全排序. 而在 GPU 中, 由于 GPU 难以实现动态内存分配, 反向邻居的数量无法预
先确定, 为了降低 GPU 的内存开销, 本文将各节点的反向邻居数量固定为 k, 当反向邻居数量超过 k 时, 通过模运
算确定替换位置, 比较新的候选点距离与对应位置的反向邻居距离, 保留距离较小的节点. 该策略在降低内存开销
的同时提升了近邻图的精度.
算法 1 描述了 GPU 加速的 K 近邻图构建算法. 该算法根据指定的迭代次数 it 进行计算 (第 1 行), 其中每个
线程块负责一个节点的计算 (第 2 行). 首先进行最近邻偏好采样 (第 3、4 行), 并对采样后的节点排序后去重 (第
5 行), 该过程的时间复杂度为 O(log|S |). 接着, 对采样得到的候选节点计算与节点 u 的距离 (第 6–9 行), 其时间复
O(|S |×logd/Warp), 其中, d 为向量维度, Warp N(u) 进
杂度为 表示线程组数量. 最后对 S 中的节点按距离排序后与
行归并, 并更新 u 的反向邻居, 其时间复杂度为 O(log|S |). 综上, 算法 1 的时间复杂度为 O(it×|S |×logd/Warp).
算法 1. GPU 加速的 K 近邻图索引构建算法.

输入: 向量数据集 D, 迭代次数 it, 近邻图度数 k;
输出: 构建的 K 近邻图索引.
1. for (i = 0; i < it; i++) do
2. for each u ∈ D in parallel at thread block level do
3. S 1 ← 对 N(u) 中前 M 个节点的邻居节点进行采样;
4. S 2 ← 对 {v|u ∈ N(v)} 中前 M 个节点的邻居节点进行采样;
5. S ← 对 S 1 ∪S 2 进行去重;
6. for each v ∈ S in parallel at the warp level do
7. v.dis = dis(v,u); /*warp 内线程并行计算距离*/
8. if v.dis > N(u) 中的最大距离 do

9. 在 S 中删除 v;
10. 对 S 中的节点按距离排序;
11. N(u) ← 将 S 与 N(u) 中的点按距离归并;