.png){kind=icon}
返回
An FPGA Implementation for Solving the Large Single-Source-Shortest-Path Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TCSII.2015.2505998.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Field-programmable gate arrays (FPGAs)
single source shortest path (SSSP)
systolic array priority queue (SAPQ)
期刊
I
IF:
4.9
论文数:
8.8K
被引数:
2.5W
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏 没有更多内容
没有更多内容