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

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

离计算, 并采用上述归约流程得到各数据点的距离最小聚类中心. 同理, 线程块 3 和 4 按照相同的流程计算 v 2 包
含的数据点. 聚类中心点分别更新后, 迭代上述流程至指定次数, 即可形成第 3 层节点. 第 3 层节点的并行计算模
式与前两层相同, 基于此流程进行并行 K-means 树划分直至达到预设的树深度.
为了保证分区内数据的邻近性, 算法未添加分区均衡性的约束. 此外, 由于 GPU 共享内存的容量限制, 线程块
中一次计算能处理的分区大小有限, 算法输出的较大分区将被均分为能够被线程块一次计算处理的大小. 为了均
衡线程块间的负载, 在第 3.3.1 节分区局部聚类时, 本文将分区由大到小排序, 均衡分配给不同线程块, 以减小负载
不均衡对后续聚类效率的影响.
算法 2 描述了 Tensor 核心增强的层间并行 K-means 树分区算法流程. 首先初始化聚类中心, 并指定每个线程
块负责的分区序号 (第 1 行). 接着对 K-means 树的每一层 (第 2 行) 迭代计算 K-means 聚类 (第 3 行). 在计算过程
中, 每个线程块负责一部分数据与对应聚类中心的距离计算, 并按距离更新数据点对应的聚类中心 (第 4、5 行),
O(|D s |×k). 最后更新聚类中心的值 (第 7 行). 当 K-means 迭代计算结束后, 需按聚类中心编
该过程时间复杂度为
号由小到大重排数据点 (第 8 行), 并为线程块动态分配数据分区, 同时更新 BlockPar (第 9 行), 以便下一层计算.
由于第 7–9 行操作可并行执行, 因此时间复杂度由第 3–6 行决定, 整个算法的时间复杂度为 O(h×it×k×|D s |).

算法 2. Tensor 核心增强的层间并行 K-means 树分区算法.

输入: 向量数据集 D, 树高度 h, 迭代次数 it, 子节点数量 k;
输出: K-means 树分区结果.

,
1. 随机初始化聚类中心 C[0] BlockPar ← {0,...,0}; /*初始化每个线程块负责的分区序号为 0*/
2. for (i = 0; i < h; i++) do
3. for (j = 0; j < it; j++) do
4. for each D s ⊂ D in parallel at the thread block level do /*各线程块计算部分数据*/

5. dis(D s ,C[BlockPar[blockID]]) ← Tensor 核心计算数据点与聚类中心距离;
6. 根据 dis(D s ,C[BlockPar[blockID]]) 为 D s 包含的数据点选择聚类中心;
7. 更新聚类中心值;
8. 按聚类中心编号重排数据集 D;
BlockPar;
9. 为线程块分配分区并更新
10. return K-means 树分区结果;
3.3 基于广度优先搜索和核心近邻图的并行聚类
完成 K 近邻图构建以及数据集分区后, 下面基于构建好的 K 近邻图在各分区内进行 DBSCAN 局部聚类计
算, 最后将局部聚类结果合并为全局聚类结果. 为此, 本节分为两部分: 首先介绍基于广度优先遍历策略的分区局
部并行 DBSCAN 算法, 而后介绍基于核心近邻图的簇合并算法.
3.3.1 分区局部并行 DBSCAN 算法
通过 K-means 树对数据集分区后, 为各分区分配一个 GPU 线程块, 负责该分区的局部 DBSCAN 计算. 为了
充分利用 GPU 线程块内的大量线程, 局部并行 DBSCAN 算法采用广度优先的方式对聚类簇进行扩展. 算法依次
以一个核心点为起点, 并根据近邻关系收集核心点, 根据定义 8, 该过程中访问到的核心点密度与起点之间相连,

因此这些核心点及其密度邻域内的边界点与起点同属于一个聚类簇. 为此, 在每个线程块的共享内存中建立队列,
在线程块中设置一个主线程负责管理队列. 首先, 主线程选择一个核心点作为初始点入队列. 而后, 线程块中所有
线程并行判断该核心点在 K 近邻图中距离小于等于 ε 的所有邻居节点. 若邻居节点为核心点, 则标记后利用
CUDA 原子操作加入队列, 若为非核心点, 则仅做标记. 此外, 由于第 3.1 节中构造的 K 近邻图为全局 K 近邻, 为
了将搜索范围控制在分区内部, 需进一步核查遍历的点是否为当前分区的数据点, 若不位于当前分区, 则不进行任