GPU-based Graph Traversal on Compressed Graphs

Graph processing on GPUs received much attention in the industry and the academia recently, as the hardware accelerator offers attractive potential for performance boost. However, the high-bandwidth device memory on GPUs has limited capacity that constrains the size of the graph to be loaded on chip. In this paper, we introduce GPU-based graph traversal on compressed graphs, so as to enable the processing of graphs having a larger size than the device memory. Designed towards GPU's SIMT architecture, we propose two novel parallel scheduling strategies Two-Phase Traversal and Task-Stealing to handle thread divergence and workload imbalance issues when decoding the compressed graph. We further optimize our solution against power-law graphs by proposing Warp-centric Decoding and Residual Segmentation to facilitate parallelism on processing skewed out-degree distribution. Extensive experiments show that with 2x-18x compression rate, our proposed GPU-based graph traversal on compressed graphs (GCGT) achieves competitive efficiency compared with the state-of-the-art graph traversal approaches on non-compressed graphs.