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

doi:10.1109/TCSII.2015.2505998

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

2016-05-01

21

PRE

AI

DOI：10.1109/TCSII.2015.2505998

Original

Original request for help

Save

Abstract

En 中文

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 5x over the CPU implementation and the power consumption is only 1/4 of the latter.

Keywords:

Field-programmable gate arrays (FPGAs)

single source shortest path (SSSP)

systolic array priority queue (SAPQ)

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

Abstract

Journal

Organization