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

作者：Lei, Guoqing^*; Dou, Yong; Li, Rongchun; Xia, Fei

来源：IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2016, 63(5): 473-477.

DOI：10.1109/TCSII.2015.2505998

• Field-programmable gate arrays (FPGAs)
• single source shortest path (SSSP)
• systolic array priority queue (SAPQ)

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.

• 出版日期2016-5
• 单位中国人民解放军国防科学技术大学; 中国人民解放军海军工程大学