RidgeWalker: Perfectly Pipelined Graph Random Walks on FPGAs

Graph Random Walks (GRWs) offer efficient approximations of key graph properties and have been widely adopted in many applications. However, GRW workloads are notoriously difficult to accelerate due to their strong data dependencies, irregular memory access patterns, and imbalanced execution behavior. While recent work explores FPGA-based accelerators for GRWs, existing solutions fall far short of hardware potential due to inefficient pipelining and static scheduling. This paper presents RidgeWalker, a high-performance GRW accelerator designed for datacenter FPGAs. The key insight behind RidgeWalker is that the Markov property of GRWs allows decomposition into stateless, fine-grained tasks that can be executed out-of-order without compromising correctness. Building on this insight, RidgeWalker introduces an asynchronous pipeline architecture with a feedback-driven scheduler grounded in queuing theory. This design enables perfect pipelining and adaptive load balancing. We prototype RidgeWalker on FPGAs and evaluate its performance across a range of GRW algorithms and real-world graph datasets. Experimental results demonstrate that RidgeWalker achieves an average speedup of 7.0× over state-of-the-art FPGA solutions and 8.1× over GPU solutions, with peak speedups of up to 71.0× and 22.9×, respectively. The source code is publicly available at https://github.com/Xtra-Computing/RidgeWalker.