부산대학교 도서관

Implementing an efficient k-Nearest Neighbors(kNN) algorithm on FPGA is becoming challenging due to the fact that both the size and dimensionality of datasets that kNN is working on have been rapidly growing, which may incur a performance bottleneck on the memory-access. To reduce the impact of the memory-access constraint, in this paper we implement two kNN kernels through high-level synthesis (HLS) on FPGA by employing two data access reduction methods: low-precision data representation and principal component analysis based filtering (PCAF). One kernel is called MBFSkNN (Memory-efficient Brute-Force Searching kNN) and the other is called MPCAF-kNN (Memory-efficient PCAF kNN). Both kernels have been highly optimized to fully exploit the characteristics of FPGA. Besides, they are adaptive to the number of dimensions (D), number of data points in a database (N), number of nearest neighbors (k), number of bits per feature (B), and number of principal components (d). We evaluate the two kernels by comparing them with two state-of-the-art kNN implementations on a high-end CPU server, an existing BFS-kNN kernel on FPGA, and an existing BFS-kNN kernel on GPU. Our results show that the external memory accesses of these two kernels are greatly reduced and our design outperforms the existing ones.