그래프 기반 근사 최근접 이웃 검색(ANNS, Graph-based Approximate Nearest Neighbor Search)은 추천 시스템, 자연어 처리, 컴퓨터 비전 등 다양한 응용 분야에서 널리 채택되고 있다. GPU 기반 가속을 다룬 최근 연구들이 ANNS 성능을 상당히 향상시켰음에도 불구하고, 데이터셋의 규모가 계속 증가함에 따라 효율적인 다중 GPU 솔루션이 요구된다. 그러나 기존 연구들은 다중 GPU 확장성을 설계 관점에서 간과한 결과, 추가 GPU를 대규모 데이터셋의 메모리 용량을 확장하기 위한 수단으로 취급하는 단순한 접근이 이루어지고 있다. 이러한 비효율성은 데이터셋을 분할한 뒤 각 GPU에서 질의와 유사한 데이터 포인트를 독립적으로 탐색함으로써 발생한다. 이에 우리는 대규모 데이터셋에 대한 ANNS를 확장하고 가속하도록 설계된 새로운 다중 GPU 프레임워크 PathWeaver를 제안한다. 첫째, 우리는 GPU를 고려한 파이프라이닝 메커니즘인 파이프라이닝 기반 경로 확장(pipelining-based path extension)을 제안하며, GPU 간 통신을 활용하여 선행 연구의 중복 탐색 반복을 감소시킨다. 둘째, 대표 데이터셋을 활용하여 질의의 최적 시작 지점을 식별하는 ghost staging을 설계함으로써, 어려운 질의에 대해 탐색 공간을 줄인다. 마지막으로, 탐색 과정 초기에 관련 없는 포인트를 필터링하는 데이터 선택 기법인 direction-guided selection을 도입하여 불필요한 메모리 접근과 거리 계산을 최소화한다. 다양한 데이터셋에 대한 종합적인 평가 결과, PathWeaver는 95% recall rate에서 최첨단 다중 GPU 기반 ANNS 프레임워크 대비 3.24$\times$ geomean 속도 향상과 최대 5.30$\times$ 속도 향상을 달성함을 보여준다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.