Processing-in-Memory Acceleration of HNSW-PQ-based Approximate Nearest Neighbor Search = HNSW-PQ 방식의 근사 최근접 이웃 알고리즘의 프로세싱-인-메모리에서의 가속

국문 초록 (Abstract)

ANNS(Approximate Nearest Neighbor Search)는 벡터 데이터베이스의 핵심 연산이며, HNSW-PQ는 높은 재현율과 낮은 지연 시간 사이의 균형을 컴팩트한 메모리 사용량으로 제공한다. 하지만 HNSW-PQ는 PQ 거리 계산 과정에서 질의에 따라 달라지는 LUT를 매우 세밀하게 반복 조회하고 PQ 코드를 자주 가져와야 하여서, 전체 성능이 메모리 대역폭에 의해 제한되는 경우가 많다. 본 연구는 FALA 스타일의 PIM 프리미티브를 활용해 LUT 값 수집과 거리 누적을 HBM-PIM으로 오프로딩함으로써 HNSW-PQ를 가속한다.

제안 기법은 질의 LUT를 메모리에 고정(pinning)하고 PQ 거리 계산을 배치로 처리하며, all-bank gather 커멘드와 스케줄링을 통해 병렬성을 활용하여 커맨드 오버헤드를 줄인다. Ramulator 기반 HBM2 모델에서 BIGANN/TexMex의 SIFT 데이터셋으로 평가한 결과, 제안 기법은 SIFT1M에서 최대 2.39x, SIFT10M에서 최대 2.42x의 사이클 감소를 보였다. 또한 커맨드 트레이스 기반의 IDD 에너지 분석을 통해, 제안하는 COLLECT 기반 설계가 READ-only baseline 대비 DRAM 에너지를 최대 1.46x 절감함을 보였다.

다국어 초록 (Multilingual Abstract)

Approximate nearest neighbor search (ANNS) is a key primitive in vector databases, and HNSW-PQ provides a good recall--latency trade-off with compact memory usage. However, HNSW-PQ is often memory-bound: PQ distance evaluation requires many fine-grained LUT reads and PQ-code fetches. We accelerate HNSW-PQ on HBM-PIM by offloading LUT gathering and distance accumulation to PIM using FALA-style primitives, while keeping the original FAISS-CPU HNSW search logic unchanged.

Our design pins the query LUT in memory, batches PQ distance computations, and uses an all-bank gather schedule to exploit bank-level parallelism and reduce command/activation overhead. Using a Ramulator-based HBM2 model with the BIGANN/TexMex SIFT datasets, our design achieves up to 2.39x cycle reduction on SIFT1M and 2.42x on SIFT10M compared with READ-only naive PIM LUT fetch baseline execution. An IDD-based energy analysis over command traces shows that our COLLECT-based designs reduce DRAM energy by up to 1.46x versus a READ-only baseline.

목차 (Table of Contents)

• Abstract i
• Contents ii
• 1 Introduction 1
• 1.1 Introduction 1
• 1.2 Research Questions and Contributions 4
• 1.2.1 Research Questions 4
• 1.2.2 Contributions 5
• 2 Background 6
• 2.1 Approximate Nearest Neighbor Search 6
• 2.1.1 Problem Definition and Evaluation Metrics 6
• 2.1.2 ANNS Algorithms 7
• 2.2 Hierarchical Navigable Small World (HNSW) 8
• 2.2.1 Offline - Index Structure and Construction 8
• 2.2.2 Online - Search Algorithm and Parameters 9
• 2.3 Product Quantization (PQ) 9
• 2.3.1 Vector Quantization and Product Quantization 10
• 2.3.2 Asymmetric Distance Computation and LUT-based Search 11
• 2.3.3 PQ in ANN Systems (IVF-PQ, HNSW-PQ) 12
• 2.4 HNSW-PQ in Modern Vector Databases 12
• 2.4.1 Graph Routing with Quantized Distances 13
• 2.4.2 End-to-end Query Pipeline and Hotspots 13
• 2.5 Processing-In-Memory (PIM) 14
• 2.5.1 PIM Architecture Overview 14
• 2.5.2 Programming Model and Constraints 15
• 3 Related Works 18
• 3.1 Hardware Acceleration of ANN and PQ-based Search 18
• 3.2 Processing-In-Memory for Data-Intensive Workloads 20
• 4 Motivation 24
• 4.1 Overhead of HNSW-PQ 24
• 4.2 Limitations of Vanilla HBM-PIM 26
• 5 Overview 29
• 6 Design 31
• 6.1 PIM-Aware HNSW-PQ Design 31
• 6.1.1 PIM Mapping of HNSW-PQ Distance Pipeline 32
• 6.1.2 All-Bank Parallelism 36
• 6.1.3 Cycle Reduction 38
• 7 Methodology 41
• 8 Experiment 45
• 8.1 Main Result 45
• 8.1.1 Generalization across dataset domain 47
• 8.1.2 Comparison with CPU Baseline 48
• 8.1.3 DRAM energy comparison 50
• 8.2 Ablation Study 52
• 8.2.1 Effect of all-bank, LUT permutation, and hot-node caching 52
• 8.2.2 Effect of batch size K 53
• 8.2.3 Overhead analysis 55
• 9 Conclusion 56
• Abstract (In Korean) 67
• Acknowledgement 68