Design Of Graph Data Triangle Counting Algorithm In Complex Networks Based On GPU

With the rapid development of complex networks and big data,triangle counting has been widely used in important role recognition,spam detection,community discovery,and biological detection.The triangle counting algorithm is mainly used to calculate the number of intersections of adjacent lists to identify triangles in the graph.The number of triangles plays an important role in calculating the network clustering coefficient and transitivity.The traditional triangle counting algorithm traverses each vertex or edge in the graph to find the intersection of two lists.Once a common adjacent vertex is found,a triangle is found.With the advent of the era of big data,the magnitude of graph structure data studied by researchers has grown exponentially,and networks with tens of billions of nodes have even appeared in real social and engineering.In recent years,the use of GPU-accelerated graph data for triangle counting has attracted more and more researchers' attention.How to make full use of the GPU memory and use the computing characteristics of the GPU to design triangle counting schemes has become a focus of research.This dissertation presents two GPU-based graph triangle counting schemes,and do some experiments on a large number of data sets,showing better performance.The main contents and contributions of the dissertation can be summarized as follows:(1)A CSR-based graph partition algorithm is proposed.The CSR-based graph partition algorithm divides the entire task of triangle counting of large-scale graphs into multiple sub-tasks,thereby ensuring that data can be sent to GPU memory for calculation or to balance workload distribution among multiple GPUs.(2)A load balancing triangle counting scheme based on GPU is proposed.We have extended the set-based intersection algorithm based on merging,transplanted it to the GPU,and proposed a setbased intersection algorithm based on SIMD,using a neighbor list as a query list and another as a comparison list.Multiple GPU cores check the comparison based on the query list.This algorithm can solve the problems of branch divergence and low memory access efficiency of traditional algorithms.In the parallelization process,the traditional triangle counting algorithm distributes the nodes evenly to the threads of the GPU.Due to the different degrees of nodes,the workload of different threads is also different,which will reduce the performance of parallel computing.To this end,we designe a load balancing algorithm to dynamically schedule GPU workloads to improve parallel efficiency.(3)A set intersection triangle counting algorithm based on binary search is proposed.Aiming at the shortcomings of the serial set intersection algorithm based on binary search,a feasible solution is proposed in the process of parallelization,including combined memory access,load balancing,and GPU shared memory optimization.By analyzing the memory complexity of the set-based intersection algorithm based on the merge and the set-based intersection algorithm based on the binary search,it is concluded that the performance of the set-based intersection algorithm based on the binary search is better than that of the set-based intersection algorithm based on the merge in the parallel operation.And we implement the set intersection triangle counting algorithm based on binary search on GPU.(4)The experimental verification is performed on a large number of data sets.The experimental results show that compared with the traditional CPU graph-based triangle counting algorithm,the GPU-based performance is greatly improved.Compared with other parallel algorithms,our proposed algorithm has more operating efficiency.