FenWalker: Towards FPGA Accelerated Dynamic Graph Random Walks on Massive Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Abstract

Dynamic Graph Random Walk (DGRW) is a fundamental yet computationally intensive task for analyzing large-scale graphs. A critical challenge lies in performing DGRW efficiently on dynamically changing graphs, where existing systems often struggle to simultaneously achieve high-throughput queries, online updates, and low memory overhead. This paper explores the potential of FPGA to tackle this problem, leveraging their inherent capabilities for hardware customization to implement fine-grained pipelines and optimized memory access. Specifically, we propose FenWalker, an FPGA-based DGRW accelerator designed for large-scale dynamically changing graphs. From the algorithmic perspective, we introduce a novel sampling method based on the Fenwick tree data structure. This method reduces the sampling complexity to O(log d) and the dynamic update complexity to O(log d) with small memory overhead, where d is the degree of the given vertex. From an architectural perspective, we devise a deeply pipelined hardware architecture with co-optimized on-chip and off-chip memory management, designed to maximize parallelism and fully exploit available memory bandwidth. Experiments on diverse datasets using representative DGRW algorithms show FenWalker achieves query speedups of up to 19.7x, 14.3x, and 605.3x over the state-of-the-art FPGA, GPU, and CPU implementations, respectively. Additionally, it attains up to 21.2x higher update throughput than the state-of-the-art FPGA accelerator.

Author Affiliations