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

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

12. 更新反向邻居 {v|u ∈ N(v)} 的邻居列表;
13. return K 近邻图;

3.2 Tensor 核心增强的层间并行 K-means 树分区
为了充分利用 GPU 线程块间的并行性, 本文采用分而治之的思想, 对数据集进行分区处理, 各分区由不同线
程块并行执行 DBSCAN 聚类. 同时, 需确保分区内数据的相似性, 以减小后续簇合并的计算开销. 传统方法在低维
场景中采用基于 KD 树或基于网格划分的方式实现对数据集的分区, 但此类方法在高维场景下将造成较高的时间
开销. 为此, 本文采用 K-means 树对数据集进行高效分区. K-means 树通过递归聚类生成层级结构: 首先对所有数
据点进行 K-means 聚类, 将得到的 k 个聚类簇作为树的 k 个子节点, 各子节点内部再次执行 K-means 聚类生成下
一层节点. 与传统方法不同, K-means 树在计算时无须按维度划分数据, 且具有较高的效率. 值得注意的是, 分区过
程无须精确地聚类, 仅需通过少量迭代将相似的数据分至不同分区.
尽管 K-means 树各节点内部的聚类计算适合使用 GPU 并行化, 但随着树深度的增加, 高层节点包含的数据数
量呈指数级衰减. 顺序生成节点将导致 GPU 资源利用率不足, 进而引起计算性能的下降. 为了应对这一问题, 本文
提出了 Tensor 核心增强的层间并行 K-means 树分区算法. 该算法通过并行生成同一层的所有节点, 而非逐层顺序
生成, 确保 GPU 资源始终高效利用. 其核心在于, K-means 树各层总数据量不变, 因此层间并行可最大化并行度.
同时, 算法将 K-means 距离计算转换为矩阵乘法计算, 利用 Tensor 核心加速计算过程.
图 4 展示了 Tensor 核心增强的层间并行 K-means 树分区算法的一个示例. 在根节点, 随机初始化 k 个聚类中
心, 通过矩阵乘法计算数据点与聚类中心的距离, 并使用 GPU 的 Tensor 核心加速该计算过程. 由于 GPU 内部每
个线程块均可调用 Tensor 核心进行矩阵乘法运算, 为了充分发挥 GPU 的并行性, 将数据点均分至所有线程块, 各
线程块将聚类中心点载入其共享内存, 以加快访存速度. 各线程块分别调用不同的 Tensor 核心计算数据点与聚类
中心的距离, 将计算得到的距离写入共享内存. 此时, 各数据点与聚类中心的距离保存在对应线程块的共享内存
中, 为了确定与数据点最近的聚类中心, 对于每个数据点, 线程块内的线程分别取该数据点与各聚类中心的距离,
首先使用 CUDA 线程间通信函数__shuf_sync() 在线程组内 (32 个线程) 选出局部距离最小的聚类中心, 各线程组
将其结果写入共享内存, 线程块内的线程再进行线程块级别的归约操作, 最终选出全局距离最小的聚类中心. 完成
所有数据点的聚类中心分配后, GPU 并行更新聚类中心值. 按照上述流程迭代固定次数, 即可得到 k 个子节点包
含的数据点.

执行 K-means 线程块 1 …
v 0 线程块 2 …
v 1 v 0
线程块 3 …
线程块 4 … Tensor 核心 聚类中心点
数据点
线程块 1 …
v 1
并发执行 K-means …
v 1 线程块 2
v 1 v 2 线程块 3 …
v 2
v 2 动态划分线程块 线程块 4 … Tensor 核心 聚类中心点
数据点
v 3
线程块 1 … v 3
并发执行 K-means
v 4 线程块 2 … v 4
v 3 v 4 v 5 v 6
线程块 3 … v 5
v 5
动态划分线程块
线程块 4 … v 6 Tensor 核心
K-means 树 (k=2) v 6
数据点 聚类中心点
图 4 Tensor 核心增强的层间并行 K-means 树分区算法

第 1 层根节点聚类结束后, 即可得到第 2 层的 k 个子节点, 此时 k 个子节点需独立进行 K-means 聚类. 本文通
过动态线程块分配实现层间并行: 按照 k 个子节点包含的数据点数量重新分配线程块, 各线程块内部执行与根节
点 K-means 流程相同的计算. 例如, 在图 4 示例中, 第 2 层得到 2 个子节点. 由于 2 个子节点所包含的数据量相近,
因此分别分配 2 个线程块负责每个子节点的距离计算. 线程块为这 2 个子节点随机初始化 2 组聚类中心点, 线程
块 1 和 2 将子节点 v 1 包含的数据点读入共享内存, 并将第 1 组聚类中心点读入共享内存, 调用 Tensor 核心进行距