An Efficient FPGA Implementation of Approximate Nearest Neighbor Search

Approximate nearest neighbor search (ANNS) plays an important role in modern artificial intelligence (AI) systems, being extensively utilized in search engines, advertising, and recommendation systems. With the advent of large language models (LLMs), ANNS is increasingly finding applications in edge scenarios such as personal assistants. The demand for efficient and fast ANNS solutions is, therefore, more pressing than ever. In this article, we propose a scalable and efficient field-programmable gate array (FPGA) implementation of ANNS based on the inverted file with product quantization (IVF-PQ) algorithm, thus marking the first hardware implementation supporting up to 1024-D datasets. First, we devise a novel architecture for the Top-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> module, capable of processing multiple input data streams simultaneously and linearly increasing throughput. Second, we adjust the data precision in several parts of our design, thus achieving obvious performance improvement without losing much recall. Moreover, we introduce a flexible distance calculation (Distance Cal) module that can be reused for various computational tasks at different query stages. We code our design in Verilog and implement it on Xilinx Alveo U280. The experimental results show that our search latency can be as low as 0.0071 ms at a 94% recall, while the power is 19.80 W. Compared to the state-of-the-art application-specified integrated circuit (ASIC) implementations, our design delivers a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4.5\times $ </tex-math></inline-formula> speedup in latency and a 20% reduction in energy consumption.