Research And Design Of General Accelerator For Various Clustering Algorithms

With the rapid development of artificial intelligence,many traditional algorithms are endowed with new vitality,and cluster analysis plays an increasingly important role in all walks of life.Since the information age brings massive data,people put forward higher requirements on the processing speed of clustering algorithm.Regarding the acceleration of clustering algorithm,in addition to modifying its own algorithm,hardware acceleration platform can also be used to achieve acceleration.As one of the commonly used hardware devices,Field-Programmable Gate Array(FPGA)has the advantages of high performance,low power consumption and repeatable combination of a large number of internal logic blocks.Nowadays,hardware acceleration methods are usually aimed at a single algorithm,and there are few common designs for multiple algorithms.Therefore,in this paper,while improving the execution speed of the algorithm,the universality and flexibility of the accelerator are fully considered.A general accelerator including a variety of clustering algorithms is designed to avoid resource waste and other problems.The specific work of this paper is as follows:(1)Software and hardware functions of the accelerator are divided.K-means,single-linkage,DBScan and Clique algorithms were selected from the clustering algorithms based on partition,hierarchy,density and grid.By reading the key codes of the four clustering algorithms and analyzing their operational characteristics in detail,the same functional modules are taken out directly or transformed.The distance computing unit and the minimum value finding unit are obtained.Then,the heat analysis of the proposed common unit is carried out,and the time-consuming modules are divided into hardware devices,and the rest of the algorithm is kept on the CPU.So that the accelerator to meet the universality and at the same time maximize the acceleration performance.(2)Parallel optimization design is carried out for the general modules allocated on the accelerator.For the distance computing unit,this paper designs the data parallel and dimensional parallel respectively.Data parallelism is reflected in the design of parallel operations between multiple processing units by utilizing a large number of logic blocks embedded in the FPGA.The distance between multiple data objects can be calculated simultaneously to realize the parallel processing of data.Dimensional parallelism is reflected in the following aspects: change the internal execution mode of each processing unit,and design the computation of the distance from point to point of each pair as parallel processing mode,so as to maximize the utilization of resources.For the minimum value search unit,this paper USES a large number of comparators to design a multi-bit comparison tree,which can quickly find the minimum value from multiple data objects and effectively improve the efficiency of the algorithm.This paper uses different data sets to verify the correctness of many clustering algorithms.Then,according to the number of clock cycles required by the common module to execute on the FPGA,the algorithm execution time under the collaborative work of software and hardware is calculated.The acceleration performance of the accelerator is evaluated by the acceleration ratio of the algorithm running on the CPU and the hardware and software working together.The results show that the scheme of replacing some software algorithms with accelerators can effectively improve the overall running speed.