ThunderRW: An In-Memory Graph Random Walk Engine

Download PDF

Abstract

As random walk (RW) is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient in-memory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a single graph operation, ThunderRW supports massive parallel random walks. The core design of ThunderRW is motivated by our profiling results: RW algorithms have as high as 73.1% CPU pipeline cycles stalled due to irregular memory access, which suffers significantly more memory stalls than the conventional graph workloads of a single graph operation such as BFS and SSSP. To improve the memory efficiency, we first design a generic step-centric programming model named Gather-Move-Update to abstract different RW algorithms. Based on the programming model, we develop the step interleaving technique to hide memory access latency by switching the execution of different random walk queries. In our experiments, we use four representative RW-algorithms including PPR, DeepWalk, Node2Vec and MetaPath to demonstrate efficiency and programming flexibility of ThunderRW. Experiment results show that ThunderRW outperforms state-of-the-art approaches by an order of magnitude, and the step interleaving technique significantly reduces the CPU pipeline stall from 73.1% to 15.0%.