Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
6-2021
Abstract
GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further optimize the memory efficiency of SAGE through a lightweight and effective node reordering technique on the fly. Extensive experiments demonstrate that SAGE can achieve superior graph traversal performance over existing approaches under different architectural scenarios, i.e., singleGPU, out-of-core, and multi-GPU.
Keywords
Graph Processing, GPGPU, Parallel Task Scheduling
Discipline
Databases and Information Systems | Theory and Algorithms
Research Areas
Data Science and Engineering
Publication
Proceedings of the 2021 International Conference on Management of Data, Virtual Conference, 2021 June 20-25
First Page
1558
Last Page
1570
Identifier
10.1145/3448016.3457279
Publisher
ACM
City or Country
USA
Citation
1
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.