PIMCQG: Co-Designing Billion-Scale Graph-Based Approximate Nearest Neighbor Search for Processing-in-Memory

Abstract

Graph-based Approximate Nearest Neighbor Search (ANNS) has emerged as the dominant approach for large-scale AI applications, offering superior accuracy-efficiency trade-offs over alternative methods. However, graph-based ANNS is inherently memory-bound due to frequent and irregular graph traversal. This constrains CPU throughput due to limited memory bandwidth, while GPUs lack sufficient HBM capacity for billion-scale indexes. Processing-in-Memory (PIM) offers massive internal bandwidth by co-locating computation with data, making it a natural fit for irregular, memory-bound workloads. However, directly mapping graph-based ANNS onto PIM exposes severe algorithm-architecture mismatches: restricted per-PU local memory, costly inter-PU communication, heavy coordination overhead, and weak compute capability, forcing existing PIM-based ANNS to rely on cluster-based algorithms that plateau at low recall. We propose PIMCQG, an algorithm-hardware co-design framework through three optimizations: (1) a compact index reducing PIM-resident footprint by 14.5x; (2) an asynchronous pipelined scheduler fully utilizing host-PIM bandwidth; and (3) a multiplication-free distance kernel with less than 0.08% recall loss. Evaluations on three billion-scale datasets show up to 20x/17.1x throughput over CPU/GPU baselines, 129x over prior PIM accelerators at high recall, and scale well across multi-node and emerging PIM architectures.

arXiv commentAccepted by SC26