GStream: A Graph Streaming Processing Method for Large-scale Graphs on GPUs

Abstract

Fast processing graph algorithms for large-scale graphs becomes increasingly important as graphs become popular in a wide range of applications and the sizes of graphs are growing rapidly. Due to the relatively low cost and high computational power of GPUs, there have been many attempts to process graph applications by exploiting the massive amount of paral-lelism of GPUs. However, most of the existing methods fail to process large-scale graphs that do not fit in GPU device memory, mainly due to the irregular structure and the complex graph processing algorithms. Although the state-of-the-art method TOTEM can process large-scale graphs by partitioning a graph into two parts: the main memory part processed by CPUs and the device memory part processed by GPUs, it still has several fundamental problems such as a large amount of synchronization overhead and lack of scalability. We propose a fast and scalable parallel processing method GStream that processes large-scale graphs (e.g., billion vertices) beyond the capacity of GPU device memory very efficiently by exploiting the concept of so-called nested-loop join operation and the asynchronous GPU streams. It exploits multiple GPUs by uniformly distributing the workload among GPUs and also ex-ploits available GPU device memory by caching streaming graph data. GStream is the first scalable method in terms of both the data size and the number of GPUs, to the best of our knowledge. Extensive experimental results show that GStream consistently and significantly outperforms TOTEM in terms of absolute performance, scalability, and graph size to pro-cess, for both synthetic graphs and real graphs. ⓒ 2015 DGIST