An Accelerator Platform Based On FPGA For Clustering Algorithms

Clustering analysis plays a more and more important role in our work and life. Presently, it has been applied in many different fields, such as market research, pattern recognition, data analysis, image processing, customer segmentation, web document classification and so on. With the rapid development of Internet and e-commerce, the collected or accumulated data in different fields presents mass growth. Vast amounts of data greatly slow down the efficiency of the clustering analysis, and the study on accelerating algorithm has been an important topic. Different application areas or different types of data set need to adopt different clustering algorithm to achieve good performance. It’s necessary to accelerate different clustering algorithms.The main platforms to accelerate clustering algorithm are cloud computing platform and hardware acceleration. The cloud platform firstly partitions the application and then maps each partitioned application to each computer. Each computer calculates the respective application and then returns the result to the main computer. This platform needs many computers, so the cost is very high. What’s more, the network bandwidth limits the performance of cloud computing platform. There are three methods to accelerating algorithm for hardware acceleration:the GPU, the FPGA and the ASIC. The hardware acceleration accelerates algorithm by adopting the parallel or pipeline method except for the hardware features. Compared with cloud computing platform, it has little cost and the performance will not be limited by network bandwidth. So the hardware acceleration is an effective method to accelerate algorithms.Currently most of the hardware accelerator is designed for a single specific algorithm, rarely making a research for versatility and flexibility of the hardware acceleration. Although the GPUs provide a straightforward solutions, their energy-efficiencies are limited duing to their excessive supports for flexibility. The FPGA can achieve better energy-efficiencies, but each accelerator based on FPGA often accommodates one algorithm. If the hardware accelerator is designed only for one single algorithm, the accelerator can’t work for other algorithms, which greatly limit the versatility and flexibility. Can we design a hardware accelerator accommodating multiple clustering algorithms?In this paper, we design a hardware accelerator platform based on FPGA by the combination of hardware and software. The hardware accelerator accommodates four clustering algorithm, namely K-means algorithm, PAM algorithm, SLINK algorithm and DBSCAN algorithm. Each algorithm can support two kinds of similarity metrics, namely Manhattan and Euclid. Through locality analysis, the hardware accelereator presents a solution to address the frequent off-chip memory access and then balances the relationship between flexibility and performance by finding the same operations. To evaluate the performance of the accelerator, the accelerator is compared with the CPU and GPU, respectively, and then it gives the corresponding speedup and energy efficiency. The last but not the least, we present the relationship between data sets and the speedup.