GPU-based graph traversal on compressed graphs

• Main Authors: SHA, Mo, LI, Yuchen, TAN, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Computer and Systems Architecture; Computer Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4619; https://ink.library.smu.edu.sg/context/sis_research/article/5622/viewcontent/Sha_2019_Gpu_based_graph_traversal_on_compre.pdf
• Institution: Singapore Management University

Graph processing on GPUs received much attention in theindustry 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 loadedon chip. In this paper, we introduce GPU-based graph traversal on compressed graphs, so as to enable the processingof graphs having a larger size than the device memory. Designed towards GPU’s SIMT architecture, we propose twonovel parallel scheduling strategies Two-Phase Traversal andTask-Stealing to handle thread divergence and workload imbalance issues when decoding the compressed graph. Wefurther optimize our solution against power-law graphs byproposing Warp-centric Decoding and Residual Segmentationto facilitate parallelism on processing skewed out-degreedistribution. Extensive experiments show that with 2x-18xcompression rate, our proposed GPU-based graph traversal on compressed graphs (GCGT) achieves competitive efficiency compared with the state-of-the-art graph traversalapproaches on non-compressed graphs.