Jasper让GPU加速的近似最近邻搜索更快更灵活,支持实时更新。
GPU-Accelerated ANNS: Quantized for Speed, Built for Change
- 用并行构造算法实现无锁批量插入,支持数据流式更新。
- 采用高效量化技术,内存占用减少8倍,且避免随机访问开销。
- 优化搜索内核提升计算利用率,查询速度比BANG快10到74倍。
近似最近邻搜索(ANNS)是机器学习与信息检索的核心问题。GPU凭借大规模并行计算、易获取性及与下游应用共置的优势,为高性能ANNS提供了可行路径。然而现有GPU加速ANNS系统存在三大瓶颈:一是动态数据集需快速批量更新,但多数索引需重建;二是高维向量耗尽内存带宽,现有量化技术无法在不引入随机访问代价的前提下降低数据移动;三是贪婪搜索导致数据依赖性内存访问,难以重叠计算与内存操作,影响性能。本文提出Jasper,一种原生于GPU的ANNS系统,在保持高查询吞吐的同时具备可更新性。Jasper基于Vamana图索引,通过三项改进克服瓶颈:(1) 设计CUDA批处理并行构建算法,支持无锁流式插入;(2) 实现高效的RaBitQ量化方案,内存占用最多降低8倍,且无随机访问惩罚;(3) 优化贪婪搜索内核,提升计算利用率,增强延迟隐藏能力,显著提高吞吐。在五个数据集上的评估显示,Jasper相比CAGRA查询吞吐最高提升1.84倍,峰值利用率达80%(按屋顶模型衡量)。其构建过程高效扩展,平均比CAGRA快7倍,并提供CAGRA所不具备的更新能力;相比此前最快的GPU Vamana实现BANG,Jasper查询速度提升10至74倍。
原文摘要 · Abstract (English)
Approximate nearest neighbor search (ANNS) is a core problem in machine learning and information retrieval applications. GPUs offer a promising path to high-performance ANNS: they provide massive parallelism for distance computations, are readily available, and can co-locate with downstream applications. Despite these advantages, current GPU-accelerated ANNS systems face three key limitations. First, real-world applications operate on evolving datasets that require fast batch updates, yet most GPU indices must be rebuilt from scratch when new data arrives. Second, high-dimensional vectors strain memory bandwidth, but current GPU systems lack efficient quantization techniques that reduce data movement without introducing costly random memory accesses. Third, the data-dependent memory accesses inherent to greedy search make overlapping compute and memory difficult, leading to reduced performance. We present Jasper, a GPU-native ANNS system with both high query throughput and updatability. Jasper builds on the Vamana graph index and overcomes existing bottlenecks via three contributions: (1) a CUDA batch-parallel construction algorithm that enables lock-free streaming insertions, (2) a GPU-efficient implementation of RaBitQ quantization that reduces memory footprint up to 8x without the random access penalties, and (3) an optimized greedy search kernel that increases compute utilization, resulting in better latency hiding and higher throughput. Our evaluation across five datasets shows that Jasper achieves up to 1.84x higher query throughput than CAGRA and achieves up to 80% peak utilization as measured by the roofline model. Jasper's construction scales efficiently and constructs indices an average of 7x faster than CAGRA while providing updatability that CAGRA lacks. Compared to BANG, the previous fastest GPU Vamana implementation, Jasper delivers 10-74x faster queries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。