PathWeaver: A High-Throughput Multi-GPU System for Graph-Based Approximate Nearest Neighbor Search
Sukjin Kim, Seongyeon Park, Si Ung Noh, Junguk Hong, Taehee Kwon, Hunseong Lim, and Jinho Lee
基于图形的近似近邻搜索(ANNS)被广泛采用在许多应用中,如推荐系统,自然语言处理和计算机视觉。 虽然最近基于GPU的加速工作已经大大提升了ANNS的性能,但不断增长的数据集规模现在需要高效的多GPU解决方案。 然而,现有作品的设计忽略了多GPU的可扩展性,导致采用幼稚的方法,将额外的GPU视为扩展大型数据集内存容量的手段。 这种低效率源于对数据集的分区和独立搜索类似于每个GPU中查询的数据点。 因此,我们提出了PathWeaver,这是一种新颖的多GPU框架,旨在扩展和加速大型数据集的ANNS。 首先,我们提出了基于流水线的路径扩展,这是一种GPU感知的流水线机制,通过利用GPU到GPU通信来减少先前工作的冗余搜索迭代。 其次,我们设计使用具有代表性的数据集来识别最佳查询起点的幽灵分期,减少了具有挑战性的查询的搜索空间。 最后,我们介绍了方向引导选择,这是一种数据选择技术,可以在搜索过程早期过滤不相关的点,最大限度地减少不必要的内存访问和距离计算。 跨不同数据集的全面评估表明,PathWeaver在95上实现了3.24×地理均值加速和高达5.30倍的加速
Graph-based Approximate Nearest Neighbor Search (ANNS) is widely adopted in numerous applications, such as recommendation systems, natural language processing, and computer vision. While recent works on GPU-based acceleration have significantly advanced ANNS performance, the ever-growing scale of datasets now demands efficient multi-GPU solutions. However, the design of existing works overlooks multi-GPU scalability, resulting in naive approaches that treat additional GPUs as a means to extend m...