Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909693872439296 |
|---|---|
| author | Jiang, Wenqi Hu, Hang Hoefler, Torsten Alonso, Gustavo |
| author_facet | Jiang, Wenqi Hu, Hang Hoefler, Torsten Alonso, Gustavo |
| contents | Vector search systems are indispensable in large language model (LLM) serving, search engines, and recommender systems, where minimizing online search latency is essential. Among various algorithms, graph-based vector search (GVS) is particularly popular due to its high search performance and quality. However, reducing GVS latency by intra-query parallelization remains challenging due to limitations imposed by both existing hardware architectures (CPUs and GPUs) and the inherent difficulty of parallelizing graph traversals. To efficiently serve low-latency GVS, we co-design hardware and algorithm by proposing Falcon and Delayed-Synchronization Traversal (DST). Falcon is a hardware GVS accelerator that implements efficient GVS operators, pipelines these operators, and reduces memory accesses by tracking search states with an on-chip Bloom filter. DST is an efficient graph traversal algorithm that simultaneously improves search performance and quality by relaxing traversal orders to maximize accelerator utilization. Evaluation across various graphs and datasets shows that Falcon, prototyped on FPGAs, together with DST, achieves up to 4.3x and 19.5x lower latency and up to 8.0x and 26.9x improvements in energy efficiency over CPU- and GPU-based GVS systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal Jiang, Wenqi Hu, Hang Hoefler, Torsten Alonso, Gustavo Hardware Architecture Vector search systems are indispensable in large language model (LLM) serving, search engines, and recommender systems, where minimizing online search latency is essential. Among various algorithms, graph-based vector search (GVS) is particularly popular due to its high search performance and quality. However, reducing GVS latency by intra-query parallelization remains challenging due to limitations imposed by both existing hardware architectures (CPUs and GPUs) and the inherent difficulty of parallelizing graph traversals. To efficiently serve low-latency GVS, we co-design hardware and algorithm by proposing Falcon and Delayed-Synchronization Traversal (DST). Falcon is a hardware GVS accelerator that implements efficient GVS operators, pipelines these operators, and reduces memory accesses by tracking search states with an on-chip Bloom filter. DST is an efficient graph traversal algorithm that simultaneously improves search performance and quality by relaxing traversal orders to maximize accelerator utilization. Evaluation across various graphs and datasets shows that Falcon, prototyped on FPGAs, together with DST, achieves up to 4.3x and 19.5x lower latency and up to 8.0x and 26.9x improvements in energy efficiency over CPU- and GPU-based GVS systems. |
| title | Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal |
| topic | Hardware Architecture |
| url | https://arxiv.org/abs/2406.12385 |