3.8 Proceedings Paper

Self-adaptive Graph Traversal on GPUs

出版社

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3448016.3457279

关键词

Graph Processing; GPGPU; Parallel Task Scheduling

资金

  1. MoE Tier 2 grant in Singapore [MOE2019-T2-2-065, MOE2017T2-1-141]

向作者/读者索取更多资源

The paper introduces SAGE, a self-adaptive graph traversal method on GPUs that operates directly on common graph representations without the need for preprocessing. Through techniques such as Tiled Partitioning, Resident Tile Stealing, and Sampling-based Reordering, SAGE achieves superior graph traversal performance under different architectural scenarios.
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., single-GPU, out-of-core, and multi-GPU.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

3.8
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据