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

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

(bulk distance computation) 和数据结构维护 (data structure maintenance). 候选定位阶段从图索引中提取当前节点的
邻居顶点; 批量距离计算阶段利用 GPU 的并行计算能力高效完成高维向量的距离计算; 数据结构维护阶段则更新
优先级队列和哈希表以准备下一轮迭代. 通过这一解耦设计, SONG 将原本串行的距离计算转化为批量并行任务,
显著提升了 GPU 计算资源的利用率. 此外, SONG 针对 GPU 内存特性设计了多项优化, 包括采用固定度图 (fixed
degree graph) 存储, 通过全局内存的连续布局减少索引访问开销; 利用共享内存等方案; 使用布隆过滤器 (bloom
filter) 或 Cuckoo 过滤器替代传统哈希表, 在允许可控误报率的前提下减少显存占用; 提出选择性插入 (selected
insertion) 和访问删除 (visited deletion) 策略, 仅保留与当前最优候选相关的节点信息, 将哈希表内存消耗限制为
2K (K 为搜索参数). 为了进一步应对 GPU 的显存限制, 引入了随机投影来降维数据. 实验结果表明, SONG 在
GPU 上实现了基于图 ANNS 的突破性加速, 相比于单线程 HNSW 和 Faiss 分别提升 50–180 倍和 4.8–20.2 倍吞吐量.
GANNS [122] 是一个基于 GPU 加速的邻近图近似最近邻搜索与构建的框架. 该框架针对现有 GPU 图搜索方法
(如 SONG) 在数据结构操作上的瓶颈, 设计了惰性更新 (lazy update) 与惰性检查 (lazy check) 策略, 以充分释放
GPU 的并行计算潜力. GANNS 将传统串行搜索流程重构为如图 7 所示的 6 个并行化阶段: 候选定位 (candidate
locating)、邻域扩展 (neighborhood exploration)、批量距离计算 (bulk distance computation)、惰性检查 (lazy check)、
排序 (sorting) 和候选更新 (candidate update). 其中, 候选定位阶段通过线程束 (warp) 级别的位掩码操作快速定位
待探索节点; 邻域扩展阶段将当前节点的邻居批量加载至共享内存; 惰性检查阶段则通过并行二分搜索过滤已处
理节点, 避免冗余计算. 与传统方法不同, GANNS 采用固定长度数组 (而非动态优先级队列) 维护候选集, 并利用
GPU 友好的排序算法 (如 Bitonic Sort) 批量更新候选节点顺序. 这一设计不仅消除了动态内存分配的同步开销, 还
通过线程块 (thread block) 内的协作机制实现数据结构操作的并行化. 此外, 文献 [122] 中提出分治策略 GGraphCon,
将数据点划分为多个子集, 并行构建局部 NSW 图后逐步合并, 首次实现 GPU 端高效的 NSW 图与 HNSW 图构建.
实验结果表明, GGraphCon 在构建 NSW 图时相比于单线程 CPU 方法加速 40–50 倍.

① 候选定位 ② 邻域扩展 ③ 批量距离计算 ④ 惰性检查 ⑤ 排序 ⑥ 候选更新
定位首个未被 根据邻接表扩展节点 计算扩展出的节点 避免重复扩展 GPU双调排序
访问过的节点 与查询向量q的距离
图 7 GANNS 的工作流程

根据 GANNS 的实验结果 [122] , 其性能与 SONG 相比, 主要结论如下. (1) 在查询性能上, 相同召回率下,
GANNS 的 QPS 比 SONG 高 1.5–5 倍. 例如, 在 SIFT1M 数据集上, 当召回率为 0.795 时, GANNS 达到 458.5k QPS,
而 SONG 仅为 88.5k QPS. (2) 在召回率上, 两者在相同数据集上达到相似的召回范围, 表明 GANNS 的并行化未
牺牲结果精度. (3) 在性能瓶颈上, SONG 的瓶颈是数据操作 (占 50%–90% 时间), 因其依赖单线程处理优先级队列
和哈希表; GANNS 通过懒策略 (lazy update 和 lazy check) 减少数据操作开销, 使距离计算主导时间, 优化了 GPU
利用率. (4) 在查询性能鲁棒性上, 当返回邻居数 k 从 1 增至 100 时, GANNS 的速度提升稳定 (在 SIFT1M 上提升
5–5.3 倍, 在 GIST 上提升 1.5–2 倍), 而 SONG 因数据操作瓶颈在高 k 值时效率下降更明显. (5) 数据维度的影响:
GANNS 在低维数据集上性能提升更明显, 如将 GIST 从 960 维降到 60 维时, 相较于 SONG 的性能提升从 1.5 倍
提升至 6 倍, 因其能充分利用线程并行处理.
此外还有很多工作利用 GPU 优化性能. GENIE [123] 通过倒排索引将查询分解成子任务以充分利用 GPU 的并
行计算能力, 并提出了一种基于 GPU 实现的哈希表 c-PQ, 用于从候选集中选出 TopK 作为结果. PQT [124] 对乘积量
化进行拓展, 提出了一种双层次的乘积量化树以减少精确距离测试的次数, 通过设计遍历顺序与重排序算法提升
搜索性能, 并给出了基于 GPU 的实现. 文献 [125] 提出了在 GPU 上实现 IVFADC 的方法. RobustiQ [126] 提出了结合
基于量化的层次化倒排索引提升搜索效率与系统的鲁棒性的 GPU 上的搜索方法. GGNN [127] 设计了一种 GPU 友
好的线程块级别的搜索方式, 通过全并行多用途缓存与对节点近邻数量的固定提升了片上的资源利用率. GGNN
还设计了一种自下而上的图索引构建方法, 提升了索引构建的速度. GTS [128] 提出了一种基于 GPU 的索引. 该索引