Hardware Implementation Of K-means Algorithm Based On A Reconfigurable Computing Platform

k-means is a commonly used clustering analysis algorithm,which can be applied to data mining,image analysis,air pollution prevention and control,user model analysis and many other fields.The algorithm divides the data set into several subsets by analyzing the distance between data points in the data set,so that the distance between data points in the same subset is small,and the distance between data points in different subsets is large.In order to improve the calculation speed of the algorithm,this paper studies the hardware implementation of the k-means algorithm based on the reconfigurable technology.The main work includes the following three aspects:1.This paper implements the k-means algorithm in hardware based on a reconfigurable architecture,in which the storage and computing resources are shared by sub-modules,and the storage and computing resource are utilized for different submodules through a state machine,so as to achieve efficient resource reuse.2.This paper adopts the k-means++ clustering center initialization algorithm,and completes the hardware design based on the initialization algorithm,thereby improving the algorithm clustering.Besides,by using reconfigurable technology,the paper reduces the additional resources for initialization computation.3.According to the storage control logic of each sub-module,this paper designs different loop unrolling schemes to reduce the pipeline gap between the loops;To increase the hardware implementation parallelism and improve computing speed,this paper designs a 16/32-way parallel computing for the operation control logic of each sub-module.In addition,this article also validates and analyzes the results of the hardware design through the UVM and FPGA platforms,and evaluates the coverage of the verification and the performance of the design.The throughput of FPGA implementation is about 27.17 Gbps,and the throughput of ASIC implementation under the CMOS 14 nm process is about 169.8Gbps.The speedup ratio is up to 8.37 compared with the related work.