Application Of GPU Acceleration Technology In Graph Algorithms

Graphs are popular data representations in many computing, scientific and engineering areas, graph operations are building blocks to many applications. Designing efficient graph algorithms has been an important research content of Mathematics and Computer Science. With the maturity of the theory of algorithms, the researchers realized that the traditional serial graph algorithms, which almost reached the theoretical limit of tim complexity, encountered performance bottlenecks in the face of massive data generated by emerging applications such as genetic engineering, Web network analysis, geographic information systems, etc. It’s imperative to develop parallel graph algorithms. However, most studies have focused on the traditional CPU-based parallel architecture, being challenged in terms of the number of processor cores and the communication cost.Modern Graphics Processing Units(GPUs) have advantages of multiple computing cores, high computation power and high bandwidth. In recent years, the use of GPU for general purpose computing(GPGPU) has become a new trend in high performance computing. At present, research on graph algorithms in GPGPU is still in its infancy, and irregular memory access increases the difficulty of designing efficient parallel algorithms on GPU. In addition, not all graph algorithms can be effectively in parallel, for example, depth first search is inherently sequential.The thesis studies and summarizes current research situation of designing and implementing parallel graph algorithms on CPU and GPU, analyzes graph representation on GPU, and develop CUDA-based algorithms in order to sovle three types of graph problems: Strongly Connected Components(SCCs), the Minimum Spanning Tree(MST), and All-Pairs Shortest Paths(APSP). First, we implements CUDA-based FB algorithm to compute SCCs, in which the trim procedure is introduced and the impact of thread divergence is considered. Second, we design a Kruskal-Boruvka hybrid algorithm, which uses CUDA-based radix sort and the prefix sum Scan primitive to split graph, construct structure for subgraph, filter edges, and uses CUDA-based Boruvka algorithm to achieve the Minimum Spanning Forest(MSF) from the subgraph. Then, inspired by the CUDA-based single-source shortest path(SSSP) algorithm, we develop a parallel scheme to solve APSP. The solution packs multiple SSSP problems into a group to solve in parallel at a time, which can effectively utilize on-chip shared memory of GPU.Finally, by means of experiment, we explore the performance of algorithms in three synthetic graph Random, RMAT, SSCA#2 of different size. It turned out that these CUDA-based algorithms indeed achieved some speedup.