An FPGA-Based Hardware Accelerator for the k-Nearest Neighbor Algorithm Implementation in Wearable Embedded Systems

The k-Nearest Neighbor (k-NN) is one of the most used Machine-Learning based algorithm performing the classification task. The latter is very used in many application fields, especially in the context of Body Sensor Networks (BSNs) where features of interest have to be extracted from the data collected by wearable sensors. In the last few years, the ever increasing size of the collected data, as well as low-power and high-speed constraints, have brought out the need for hardware-based implementations of the k-NN algorithm. This paper describes an effective approach to design k-NN FPGA-based hardware accelerators. Low-power and high-speed are achieved by exploiting the dedicated Digital Signal Processing (DSP) slices and their fast interconnections typically available in commercial FPGA devices. Moreover, an effective hardware-friendly strategy is proposed in order to avoid the computational bottleneck shown by the sorting step of the algorithm when implemented in software. The new design has been implemented within a complete embedded system on the FPGA platform hosted on the Xilinx Zynq XC7Z020-1CLG400C heterogeneous System on Chip (SoC), and it has been tested for a real wearable application. Compared to the pure software implementation, the new design has shown an execution speed-up of several orders of magnitude, with a total power dissipation of only 198 mW.