LAUSR

Due to the so-called curse of dimensionality and increase in the size of databases, there is an ever-increasing demand for computing resources and memory bandwidth when performing the k-nearest neighbors (kNNs) algorithm, resulting in a slow-down to process large datasets. This work presents an OpenCL-based framework for accelerating the kNN algorithm on field-programmable gate arrays (FPGAs) benefiting from the random projection dimensionality reduction. The proposed RPkNN framework includes two compute modules implementing a throughput-optimized hardware architecture based on random projection and the kNN algorithm and a host program facilitating easy integration of the compute modules in the existing applications. RPkNN also utilizes a new buffering scheme tailored to random projection and the kNN algorithm. The proposed architecture enables parallel kNN computations with a single memory channel and takes advantage of the sparsity features of the input data to implement a highly optimized and parallel implementation of random projection. We employ a computation storage device (CSD) to directly access the high-dimensional data on non-volatile memory express (NVMe) solid state drive (SSD) and store and reuse the compressed and low-dimensional data on the FPGA dynamic random access memory (DRAM), hence eliminating data transfers to the host DRAM. We compare RPkNN implemented on the Samsung SmartSSD CSD with the kNN implementation of the scikit-learn library running on an Intel Xeon Gold 6154 CPU. The experimental results show that the proposed RPkNN solution achieves, on average, $26\times $ and $46\times $ higher performance across different dimensions per a single kNN computation for the SIFT1M and GIST1M databases, respectively. Finally, RPkNN is $1.7\times $ faster than the similar FPGA-based reference method.