Search papers, labs, and topics across Lattice.
This paper introduces a co-designed algorithm and architecture for graph-based Approximate Nearest Neighbor Search (ANNS) on Processing-in-Memory (PIM) systems to overcome limitations of prior PIM-based ANNS designs. The co-design includes a compacted index layout, an asynchronous pipelined scheduler, and a multiplication-free distance kernel to improve throughput and recall. Results on billion-scale benchmarks show up to 20x and 17.1x higher throughput than CPU and GPU baselines, and 129x improvement over prior PIM accelerators in the high-recall regime.
Graph-based nearest neighbor search, previously bottlenecked by memory bandwidth, achieves 20x speedup on billion-scale datasets using a novel processing-in-memory co-design.
Approximate Nearest Neighbor Search (ANNS) is a core primitive in modern AI systems, and graph-based methods currently offer the best accuracy-efficiency trade-off at scale. The workload is fundamentally memory-bound: graph traversal produces frequent, irregular memory accesses that cap CPU throughput at main-memory bandwidth, while GPUs lack the high-bandwidth memory capacity to host billion-scale indexes. Processing-in-Memory (PIM) is a natural candidate, as placing computation next to data unlocks the abundant internal bandwidth that such bandwidth-starved workloads demand. Porting graph-based ANNS to PIM, however, exposes several architectural mismatches: each processing unit has only a small local memory, inter-unit communication is costly, host coordination adds overhead, and in-memory compute units are relatively weak -- limitations that have forced prior PIM-based ANNS designs to fall back on cluster-based indexing, whose recall ceiling is far below that of graph methods. This paper presents an algorithm-architecture co-design that overcomes these obstacles through three components: a compacted index layout that shrinks the PIM-resident memory footprint by 14.5x; an asynchronous pipelined scheduler that keeps the host-to-PIM interconnect saturated; and a multiplication-free distance kernel that loses under 0.08% recall. Across three billion-scale benchmarks, the proposed design achieves up to 20x and 17.1x higher throughput than CPU and GPU baselines, respectively, outperforms prior PIM accelerators by 129x in the high-recall regime, and scales gracefully across multi-node deployments and emerging PIM architecture.
