Research Of Graph Computation Based On GPU

Graph algorithms have always been the hot issue in academia and industry.With the explosive growth of social networks and big data in recent years,the applications based on big graph are increasing.Pregel was proposed by Google as a programming model to address distributed computing on big graph.Pregel programming model plays a significant role in abstracting architectural details of distributed computing from users and offers the simple API to express graph algorithm.With the development of the GPU hardware and software technology,GPUs have become a powerful platform for parallel computing.GPU has evolved into a highly paralleled,multithreaded,manycore processor with tremendous computational horsepower and very high memory bandwidth in comparison with CPU.GPU are increasingly leveraged to accelerate graph algorithms with GPU-specific optimization.However most of graph computing research on GPU is aimed at a specific graph algorithm so far.It is lack of Pregel system based on GPU that provides the general programming model on GPU for graph algorithms.In addition,state-of-the-art systems have not yet been used to optimization according to the characteristics of graph algorithms and the GPU architecture.This paper mainly studies graph computation on GPU,to improve the Pregel programming model on GPU and propose system level optimization algorithms by analyzing the performance bottleneck.At last,based on these studies,this paper implements a graph computation system optimized for GPU,called Pregel GPU.The contributions of this paper are as follows:First,we discuss some basic background on GPU architecture,and research progress on graph computation.We focus on the programming model and execution flow of graph computing system,and analyze the weakness of related systems.Second,in order to exploit the fine-grained parallelism on GPU,we improve the traditional vertex-centric programming model and present a general graph programming model called Edge-Vertex model,which provides Pregel-like API for developing graph algorithms.We design the execution flow of the graph system,and partition the overall executing procedure into preprocessing,Edge Compute and Vertex Compute on the basis of Edge-Vertex model.At the same time,we elaboratethe execution task and logical operation of each execution phase.Third,we analyze the performance bottlenecks of Edge-Vertex model and put forward the corresponding solutions.Because load imbalance among GPU threads in existing graph processing systems has important implications on performance,we introduce an approach called approximate sort to address this issue.In addition,according to the feature of coalesced memory access,we propose a data remap algorithm on the message buffer to mitigate non-coalesced GPU memory access and enhance the actual memory bandwidth.Our experiments show that the customized system implemented in this paper could achieve 1.6x to 4.5x speedup compared with state-of-the-art graph processing framework designed for GPUs with different workloads and graph algorithms.