Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2019

Abstract

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.

Discipline

Computer and Systems Architecture | Computer Engineering

Research Areas

Data Science and Engineering

Publication

Proceedings of the 2019 International Conference on Management of Data, Amsterdam, Netherlands, 2019 June 30-July 5

First Page

775

Last Page

792

Identifier

10.1145/3299869.3319871

City or Country

Amsterdam

Additional URL

https://doi.org/10.1145/3299869.3319871

Download

Share

COinS