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

Authors: Santosh Pandey (Stevens Institute of Technology), Lingda Li and Adolfy Hoisie (Brookhaven National Laboratory), Xiaoye S. Li (Lawrence Berkeley National Laboratory), and Hang Liu (Stevens Institute of Technology)

Abstract: 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.




Back to Technical Papers Archive Listing