Processing-in-Memory를 위한 십억 규모의 그래프 기반 근사 최근접 이웃 탐색 공동 설계

근사 최근접 이웃 탐색 (Approximate Nearest Neighbor Search, ANNS)은 현대 AI 시스템의 핵심 프리미티브 (primitive)이며, 현재 그래프 기반 방식이 대규모 환경에서 최적의 정확도-효율성 트레이드오프 (accuracy-efficiency trade-off)를 제공합니다. 이 워크로드 (workload)는 근본적으로 메모리 대역폭 제한 (memory-bound) 문제를 가집니다. 그래프 탐색 (graph traversal)은 빈번하고 불규칙한 메모리 액세스 (memory access)를 발생시켜 CPU 처리량 (throughput)을 메인 메모리 대역폭 수준으로 제한하는 반면, GPU는 십억 규모의 인덱스 (index)를 수용할 만큼의 고대역폭 메모리 용량이 부족합니다. Processing-in-Memory (PIM)는 데이터 옆에 연산을 배치함으로써 이러한 대역폭 부족 워크로드가 요구하는 풍부한 내부 대역폭을 활용할 수 있으므로 자연스러운 후보입니다. 그러나 그래프 기반 ANNS를 PIM으로 이식하는 과정에서 몇 가지 아키텍처 불일치 (architectural mismatches)가 드러납니다. 각 프로세싱 유닛 (processing unit)은 작은 로컬 메모리만을 가지고 있고, 유닛 간 통신 비용이 높으며, 호스트 (host) 조정에 따른 오버헤드가 발생하고, 인메모리 연산 유닛 (in-memory compute units)의 성능이 상대적으로 낮습니다. 이러한 한계로 인해 기존의 PIM 기반 ANNS 설계들은 클러스터 기반 인덱싱 (cluster-based indexing)에 의존할 수밖에 없었으며, 이는 그래프 방식의 재현율 (recall) 상한선보다 훨씬 낮은 성능을 보입니다. 본 논문은 세 가지 구성 요소를 통해 이러한 장애물을 극복하는 알고리즘-아키텍처 공동 설계 (algorithm-architecture co-design)를 제시합니다: PIM 상주 메모리 점유율 (memory footprint)을 14.5배 축소하는 압축된 인덱스 레이아웃 (compacted index layout), 호스트-PIM 상호 연결 (interconnect)을 포화 상태로 유지하는 비동기 파이프라인 스케줄러 (asynchronous pipelined scheduler), 그리고 재현율 손실이 0.08% 미만인 곱셈 없는 거리 커널 (multiplication-free distance kernel)입니다. 세 가지 십억 규모 벤치마크 (benchmarks) 전반에 걸쳐, 제안된 설계는 CPU 및 GPU 베이스라인 (baselines) 대비 각각 최대 20배 및 17.1배 높은 처리량을 달성하였으며, 높은 재현율 영역 (high-recall regime)에서 기존 PIM 가속기보다 129배 뛰어난 성능을 보였고, 멀티 노드 배포 (multi-node deployments) 및 신흥 PIM 아키텍처 전반에 걸쳐 원활하게 확장됩니다.