An FPGA Implementation for Solving the Large Single-Source-Shortest-Path Problem

Abstract

Single source shortest path (SSSP) is a fundamental problem in graph theory. However, the existing SSSP implementations on field-programmable gate arrays (FPGAs) are incapable of processing large graphs by storing the graph and results in internal memories. In this brief, we propose a parallel FPGA implementation to solve the SSSP problem, which is derived from a variant of the “eager” Dijkstra algorithm. In order to process a large graph problem, an extended systolic array priority queue called ExSAPQ is proposed to allow large-scale priority queue processing. The experimental results on the full United States road network show that our SSSP implementation on FPGA can achieve a speedup of 5× over the CPU implementation and the power consumption is only 1/4 of the latter.