An Asynchronous Graph Computing System On GPU With Hybrid Coloring Algorithm

Large-scale graph computing has become an important part of big data processing. It can be found whether in the social networks, Web applications, or biological information networks. And research on graph processing systems becomes one of the hot fields of High Performance Computing(HPC). With the development of GPGPU technology, it becomes a trend that GPU is used to accelerate the graph processing. However, current GPU based graph computing systems are developed based on the synchronous processing model, which needs a barrier to complete the data synchronization after each iteration of the execution. These systems cannot make full use of GPU computing resources because of the unbalanced data partitioning. And the overhead of data synchronization is huge, which also slows the convergence speed of graph algorithms.The graph computing system Frog is based on the asynchronous processing model. Frog does not need the data synchronization barrier. And Frog solves the problem that synchronous systems cannot make full use of GPU computing resources and slow the convergence speed of graph algorithms. Firstly, Frog uses asynchronous model to avoid the overhead of data synchronization barrier and ensures the graph processing consistency at the same time. Secondly, Frog adopts a novel data partitioning strategy, which colors all vertices of the input graph and assigns some vertices into the hybrid chunk to ensure enough computing tasks for each GPU kernel. So Frog can improve the utilization of GPU parallel computing resources. Finally, Frog accelerates the transfer speed of messages of updated vertices. As all vertices are able to access to the latest updates inside the current iteration, Frog accelerates the convergence speed of graph algorithms. In addition, by dividing graphs into a number of sub graphs adapted to the memory size, Frog can process graphs with the scale out of the GPU device memory.We design the system Frog based on the CUDA programming framework and provide some open APIs so that users can conveniently complete the graph processing on Frog. Experiments based on real-world graphs show that Frog outperforms other state-of-the-art approaches by over 3.2X. And for out-of-GPU-memory graphs that cannot be processed by other systems, Frog achieves a speedup of 5.3X than other CPU-based graph computing systems.