ACRONYM: 동적 벡터 데이터베이스를 위한 메모리 내 가속 근사 최근접 이웃 탐색

빈번한 업데이트가 발생하는 벡터 데이터베이스 (Vector database) 검색은 검색 증강 생성 (Retrieval Augmented Generation, RAG), 추천 시스템 (Recommendation systems), 대규모 임베딩 검색 (Large-scale embedding retrieval)과 같은 애플리케이션에서 점점 더 중요해지고 있습니다. 그래프 기반 (Graph-based) 및 파티션 기반 (Partition-based) 근사 최근접 이웃 탐색 (Approximate Nearest Neighbor Search, ANNS)과 같은 기존 솔루션들은 데이터 분포에 의존적인 인덱싱으로 인해 빈번한 인덱스 재구축 (Index rebuilding) 문제를 겪으며, 이는 지속적인 배포에 영향을 미치고 긴 재구축 지연 시간 (Rebuilding latency)을 유발합니다. 본 논문은 최신 데이터베이스 검색의 주요 문제들을 해결하는 알고리즘-하드웨어 공동 설계 (Algorithm-hardware co-designed) 플랫폼인 ACRONYM을 제안합니다. 알고리즘 측면에서는 데이터 분포에 독립적인 효율적인 인코딩 (Encoding)과 효율적인 하드웨어 가속을 위한 해밍 거리 (Hamming-distance) 기반 검색을 활용합니다. 아키텍처 측면에서는 전수 조사 (Exhaustive search)를 가능하게 하기 위해 CAM 기반의 메모리 내 병렬 거리 계산 (In-memory parallel distance computation)과 그 뒤를 잇는 시분할 방식의 근사 top-k 선택 (Time multiplexed approximated top-k selection)을 제안합니다. 또한, 용량 및 워드라인 기생 성분 (Wordline parasitic)으로 인해 작은 벡터 차원에 크게 제한되는 CAM 기반 검색에서 높은 재현율 (Recall)을 달성하기 위해, 거친 검색 (Coarse search)에 이어 이진 정밀화 (Binary refinement)를 수행하는 2단계 검색을 제안합니다. ACRONYM은 중단 없는 지속적인 업데이트를 지원하며, 검색 중 효율적인 온칩 인코딩 (On-chip encoding)을 위해 새로운 XOR-and-Accumulate (XAC) 기반 시스톨릭 어레이 (Systolic-array) 인코더를 통합합니다. 백만 단위 규모의 데이터셋 전반에 걸쳐, 동적 데이터베이스를 서비스하는 동안 ACRONYM은 단 32MB의 메모리 사용량과 쿼리당 평균 2.56uJ의 에너지 소비로 초당 8e6 쿼리의 처리량에서 90% 이상의 재현율을 달성하였으며, 이는 HNSW (CPU) 대비 약 400배, FAISS-IVF (GPU) 대비 약 80배 빠른 속도입니다.