Scaph: Scalable GPU-Accelerated Graph Processing with Value-Driven Differential Scheduling

Authors: 

Long Zheng, Xianliang Li, Yaohui Zheng, Yu Huang, Xiaofei Liao, and Hai Jin, Huazhong University of Science and Technology; Jingling Xue, UNSW Sydney; Zhiyuan Shao and Qiang-Sheng Hua, Huazhong University of Science and Technology

Abstract: 

We introduce Scaph, a GPU-accelerated graph system that achieves scale-up graph processing on large-scale graphs that are initially partitioned into subgraphs at the host to enable iterative graph computations on the sub-graphs on the GPU. For active subgraphs to be processed on GPU at an iteration, the prior work always streams each in its entirety to GPU, even though only the neighboring information for its active vertices will ever be used. In contrast, Scaph boosts performance significantly by reducing the amount of such redundant data transferred, thereby improving drastically the effective utilization of the host-GPU bandwidth. The key novelty of Scaph is to classify adaptively at each iteration whether a subgraph is a high-value subgraph (if it is likely to be traversed extensively in the current and future iterations) or a low-value subgraph (otherwise). Scaph then schedules a sub-graph for graph processing on GPU using two graph processing engines, one for high-value subgraphs, which will be streamed to GPU entirely and iterated over repeatedly, one for low-value subgraphs, for which only the neighboring information needed for its active vertices is transferred. Evaluation on real-world and synthesized large-scale graphs shows that Scaph outperforms the state-of-the-art, Totem (4.12×), Graphie (8.93×) and Garaph (3.71×), on average.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {254475,
author = {Long Zheng and Xianliang Li and Yaohui Zheng and Yu Huang and Xiaofei Liao and Hai Jin and Jingling Xue and Zhiyuan Shao and Qiang-Sheng Hua},
title = {Scaph: Scalable GPU-Accelerated Graph Processing with Value-Driven Differential Scheduling},
booktitle = {2020 {USENIX} Annual Technical Conference ({USENIX} {ATC} 20)},
year = {2020},
isbn = {978-1-939133-14-4},
pages = {573--588},
url = {https://www.usenix.org/conference/atc20/presentation/zheng},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Video