Hardware-accelerated shortest path computation

Abstract

Shortest path computations are used in numerous applications such as transportation and network routing. As our demand for speed increases, we would have to respond with new ideas to implement these computations. This paper presents an architecture for Bellman-Ford shortest path computation that will be implemented on FPGAs. In the proposed algorithm we have introduced a filtering process to the Bellman-Ford’s Shortest Path Algorithm in order to reduce the amount of redundant computations. This is achieved by relaxing only edges that can be potentially updated. Furthermore, by porting the algorithm into hardware, we can introduce parallelism into the architecture. As the computation is dependent on the availability of the data, we can pre-fetch the necessary data from external memories in parallel with the shortest path computations. Our simulation results, based on 10,000 random generated graphs with node size of 1000, show that the proposed architecture can achieve an average of 14.6% improvement in runtime over the conventional hardware implementation of Bellman Ford. Furthermore, when applied to a real world Singapore roadway network, we managed to attain a 94.7% improvement in runtime over the Bellman-Fords’ implementation. Hardware synthesis results show that the runtime improvement is achieved with only 65.7% increase in FPGA resource utilization.