Session: GPU Algorithms and Optimizations

C-SAW: A Framework for Graph Sampling and Random Walk on GPUs

Wednesday, November 18, 2020

1:30 PM – 2:00 PM ET

Channel: Track 3

Author(s)

Santosh Pandey

Stevens Institute of Technology, United States of America
Lingda Li

Brookhaven National Laboratory, United States of America
Adolfy Hoisie

Brookhaven National Laboratory, United States of America
Sherry Li

Lawrence Berkeley National Laboratory
Berkeley, United States of America
Hang Liu

Stevens Institute of Technology, United States of America

Many applications have requirements to analyze, transform, visualize and learn large scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Recent literatures convey that graph sampling/random walk could be an efficient solution. These methods generate reduced graph representations, while capturing the crucial properties of the original graph. In this paper, we propose, to the best of our knowledge, the first GPU-based framework for graph sampling/random walk. First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two optimizations for collision migration. Third, towards supporting graphs that exceed GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory sampling, such as workload-aware scheduling and batched (multi-instance) sampling. In its entirety, our framework constantly outperforms the state-of-the-art projects.