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

Helen Meng, Kazutoshi Wakabayashi, Makoto IkedaIEICE 2025 · DOI

TL;DR

Researchers from the University of Tokyo have developed a scalable FPGA accelerator for the "Delta-Stepping" graph algorithm, a hybrid approach that balances the speed of Dijkstra’s algorithm with the parallelism of Bellman-Ford. By leveraging High-Level Synthesis (HLS) and a novel nested-pipeline architecture, the design achieves up to a 23x speedup over software and significantly outperforms existing hardware accelerators on medium-to-large graph datasets.

What Problem Does This Paper Address?

The Single-Source Shortest Path (SSSP) problem—finding the quickest way from point A to all other points in a network—is a cornerstone of robotics, autonomous driving, and network routing.

Engineers usually choose between two algorithmic extremes:

  1. Dijkstra’s Algorithm: Very efficient but strictly sequential (it processes one node at a time), making it hard to speed up with parallel hardware.
  2. Bellman-Ford Algorithm: Highly parallel but "wasteful," as it often re-calculates paths unnecessarily, leading to massive computational overhead on large graphs.

Delta-Stepping is the "Goldilocks" solution. It groups nodes into "buckets" (deltas) that can be processed in parallel, reducing redundant work while maintaining high throughput. However, Delta-Stepping is notoriously difficult to implement in hardware because its "bucket" structure creates unpredictable workloads and complex data dependencies. Most existing FPGA accelerators stick to the simpler Dijkstra or Bellman-Ford, leaving a performance gap for medium-to-large graphs where Delta-Stepping shines.

Methods

The authors utilized High-Level Synthesis (HLS)—specifically NEC’s CyberWorkBench—to bridge the gap between complex software logic and hardware efficiency. The core of their contribution is a Nested-Pipeline Architecture consisting of three main stages:

  • EdgeDataBuffering: This module automatically manages memory partitions to allow multiple parallel reads from the graph data stored in on-chip BRAM.
  • EdgeSearch: This is the "engine room," containing up to 32 parallel Processing Elements (PEs). It uses a "Pipeline Auto-Stall" feature that dynamically adjusts the pipeline in real-time to handle memory access conflicts and uncertain workloads.
  • DataUpdate: This stage performs "atomic" updates to node distances and manages the bucket logic for the next iteration. It ensures that if two parallel units try to update the same node, the shortest distance is preserved without data corruption.

By using HLS, the team could scale the number of parallel units (from 1 to 32) simply by changing configuration parameters, rather than redesigning the hardware from scratch.

Datasets

The accelerator was evaluated using a mix of synthetic and real-world graph datasets:

  • Synthetic: BA-Graph (Barabási–Albert model) and R-MAT graphs, used to test scalability across different graph densities.
  • Real-World:
    • Usroad-48: A map of the US highway network.
  • Web-SPAM & Web-EPA: Web link graphs representing different connectivity patterns.

These datasets ranged from 100 to 126,000 nodes and up to 162,000 edges, focusing on the "medium-scale" range where software overhead typically slows down parallel execution.

Key Insights and Ideas

  • HLS as a Complexity Tamer: The most striking insight is that HLS is no longer just for simple filters. The authors show that "Pipeline Auto-Stall" features can handle the non-deterministic nature of graph processing, which was previously a major barrier for FPGA designers.
  • The Density Sweet Spot: The researchers found that the accelerator’s effectiveness is tied to "graph density" (edges per node). As density increases, the hardware can keep more PEs busy, leading to a "self-speedup" that scales almost linearly up to 32 units.
  • Overcoming Software Overhead: In software, managing threads for medium-sized graphs often costs more time than it saves. By moving the "bucket" management into dedicated hardware logic, the authors eliminated this overhead, allowing Delta-Stepping to be efficient even on smaller datasets.

Key Results

  • Peak Performance: The design achieved a 17.63x self-speedup when moving from 1 to 32 parallel units.
  • Hardware Comparison: It outperformed previous state-of-the-art FPGA SSSP accelerators (like SPLAG or HitGraph) by up to 11.77x in terms of Million Traversed Edges Per Second (MTEPS).
  • Software Comparison: Compared to optimized software implementations of Delta-Stepping running on high-end CPUs (Intel Xeon/AMD EPYC), the FPGA accelerator was up to 23.08x faster.
  • Frequency: The design maintained high clock frequencies (300–400 MHz) even as parallelism increased, thanks to the efficient handling of nested loops.

Limitations and Future Work

The primary limitation is memory capacity. Currently, the design relies entirely on on-chip BRAM, which limits the size of the graphs it can process. While it handles "medium-to-large" graphs (up to 10M edges in theory), truly massive "billion-edge" graphs would require integrating external memory like DDR4 or HBM (High Bandwidth Memory).

The authors suggest that future work will focus on:

  1. External Memory Integration: Moving beyond BRAM to handle massive datasets.
  2. Adaptive Delta Tuning: Automatically adjusting the "Delta" parameter (the bucket size) in real-time to optimize performance based on the specific graph being processed.
  3. Multi-Source Shortest Path: Expanding the architecture to handle multiple starting points simultaneously.

Summary updated

Abstract

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.
BibTeX
@inproceedings{meng2025nested,
  author = {Helen Meng and Kazutoshi Wakabayashi and Makoto Ikeda},
  title = {{Nested-Pipeline Delta-Stepping Scalable FPGA Accelerator for Parallel Single-Source Shortest Path with High-Level Synthesis}},
  booktitle = {IEICE},
  year = {2025},
  doi = {10.1587/transfun.2025vlp0009},
}
Figure