Authors: Sitian Chen (Hong Kong Baptist University); Yusen Li (Nankai University); Yao Chen (Huazhong University of Science and Technology (HUST)); Minwen Deng (Tencent); Jintao Meng (Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences); and Amelie Chi Zhou (Hong Kong Baptist University)
Abstract: Graph-based approximate nearest neighbor search (ANNS) delivers superior accuracy-efficiency trade-offs for large-scale AI applications, but remains fundamentally bottlenecked by the ”memory wall” on CPUs and GPUs. 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 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.5×; (2) an asynchronous pipelined scheduler fully utilizing host–PIM bandwidth; (3) a multiplication-free distance kernel with <0.08% recall loss. Evaluations on three billion-scale datasets show up to 20×/17.1× throughput over CPU/GPU baselines, 129× over prior PIM accelerators at high recall, and scale across multi-node and emerging PIM architectures.
Presentation: file