GPU-based graph traversal on compressed graphs
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....
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2019
|
| Subjects: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|