Accelerating SSSP for Power-Law Graphs.

Area of Science:

• Computer Science
• Graph Algorithms
• Hardware Acceleration

Background:

• The single-source shortest path (SSSP) problem is crucial for applications like navigation and network analysis.
• Efficiently solving SSSP on large-scale power-law graphs is challenging due to priority-order traversal, scalable priority queues, and random memory access.

Purpose of the Study:

• To present SPLAG, a novel system designed to accelerate SSSP for power-law graphs on Field-Programmable Gate Arrays (FPGAs).
• To overcome the limitations of existing SSSP algorithms on large, complex graph structures.

Main Methods:

• SPLAG utilizes a coarse-grained priority queue (CGPQ) for high-throughput, priority-order graph traversal.
• A customized vertex cache (CVC) is employed to minimize off-chip memory accesses and enhance vertex data throughput.
• The system is implemented using high-level synthesis C++ for easy portability.

Main Results:

• SPLAG demonstrates up to a 4.9× speedup over state-of-the-art SSSP accelerators.
• It achieves a 2.6× speedup compared to a 32-thread CPU and nearly matches an A100 GPU's performance with significantly less power.
• Achieves a high ranking on the Graph 500 benchmark for data-intensive applications using a single FPGA.

Conclusions:

• SPLAG offers a highly efficient solution for accelerating SSSP on power-law graphs using FPGAs.
• The system's design effectively addresses challenges related to graph traversal and memory access, providing substantial performance gains.
• SPLAG's open-source nature and parameterization facilitate its adoption across various FPGA platforms.