Nested-Pipeline Delta-Stepping Scalable FPGA Accelerator for Parallel Single-Source Shortest Path with High-Level Synthesis

Delta-Stepping is a parallel algorithm commonly used to solve Single Source Shortest Path (SSSP) problems in graph benchmarks like Graph500.Although it is highly effective for very large graphs (over one billion edges), its advantages greatly diminish for medium-to-large graphs (around 100,000 to 10 million edges).Moreover, Delta-Stepping's complex bucket structure makes hardware implementation challenging, resulting in few hardware accelerators for this algorithm.In this paper, we propose a Delta-Stepping hardware accelerator using a nested pipeline structure designed with High-Level Synthesis (HLS), supporting up to 32 parallel units.Our design simplifies the handling of nested loops and resource conflicts.Simulation results show frequency improvements of 1.19 to 3.07 compared to traditional accelerators based on Dijkstra or Bellman-Ford algorithms.Our approach achieves a self-speedup of 17.63 at 32 parallelism.Compared to previous FPGA implementations, our accelerator provides up to 11.77 higher performance.Furthermore, it achieves a speedup of up to 23.08 compared to software-based Delta-Stepping implementations, enabling Delta-Stepping to be effectively applied to a wider range of practical graph processing tasks.