Research And Implemention Of Data Mining Algorithm Based On New Heterogeneous Computing Platform

The coming of big data age tremendously catalyzes the research and application of data mining. The KNN and K-means as the most famous sorting and clustering algorithms in “top 10 data mining algorithm”, have been applied widely in the area of textual information categorization, financial prediction, biogenetic engineering, and graphic information processing and so on. However, with the explosive gorwth of information and data, the fast implemention of KNN and K-means algorithms begin to face a serious challenge. The amount of data becomes lager and lager day by day, which greatly increase the complexity of algorithm implementation. Fortunately the new heterogeneous computing platform based on FPGA gives a new solution to implement these algorithm quickly. Compared with the computer clusters or workstation, the heterogeneous computing platform based on FPGA has the more acceptable price and smaller size. What’s more, FPGA also has the advantage of lower power and high energy efficiency compared to GPU platform. So, this paper did the research for heterogeneous implementation of KNN and K-means algorithm using OpenCL method based on FPGA platform.Fisrtly, this paper designs the heterogeneous implementation scheme named KBKNN for KNN algorithm based on the characteristic of FPGA platform. In order to take full advantage of heterogeneous platform, this paper designed a pipeline strategy between different devices, which will make the host and slave device work simultaneously. As to the kernel design in the device, this paper improved the conventional sorting strategy which only contains single dimension. We designed an easier and simpler parallel strategy named K parallel bubble method. In order to take full use of the global memory bandwidth of FPGA, this paper adopted memory coalescing optimization method, which could improve the throughput of the system.Secondly, this paper designs the implementation scheme named FP-Kmeans for Kmeans clustering algorithm based on FPGA platform. Consdering the characteristic of Kmeans algorithm, this paper designed a cooperative scheme containing FPGA and CPU, which increased the utilization of hardware resource. What’s more, some methods were used to optimize the memory access behavior. For example, use private memory or local memory as much as possible to reduce the global memory access.Finally, this paper implements and tests the KNN and K-means accelerate scheme based on FPGA+CPU platform and compared the performance with the existing strategy named CU-KNN and CU-Kmeans. The result of the tests showed that KB-KNN implemented on FPGA owned 1.7x speedup compared with the CU-KNN implemented on FPGA, and owned 1.5x energy efficiency radio compared with the CU-KNN implemented on GPU. FP-Kmeans implemented on FPGA owned 2.3x speedup compared with the CU-Kmeans implemented on FPGA, and owned 2.1x energy efficiency radio compared with the CU-Kmeans implemented on GPU.