Graph Sampling with Fast Random Walker on HBM-enabled FPGA Accelerators

Graph neural networks (GNNs) have gained increasing popularity among researchers recently and have been employed in many applications. Training GNNs introduce a crucial stage called graph sampling. One of the most important sampling algorithms is Random Walk. However, Random Walk and many of its variants share and suffer from the same performance problem caused by random and fragmented memory access patterns, leading to significant system performance degradation. In this work, we present an efficient graph sampling engine on modern FPGAs integrated with in-package high bandwidth memory (HBM), which brings data closer and faster to the core logic. The hardware walker design is modular and easily scalable for massive parallelism, to fully utilize the available HBM channels. Our design also provides the flexibility to support Random Walk and two of its variants on both homogeneous and heterogeneous graphs. On real-world graph datasets, we achieve a 1.39 × -3.74 × speedup with a 2.42 × -6.69 × higher energy efficiency over highly optimized parallel baselines on a Xeon CPU. We also implement these algorithms on a NVIDIA Tesla VIOO GPU and achieve comparable dynamic energy consumption.