Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/66755
Title: Hardware-accelerated shortest path computation
Authors: Yeo, Wei Jie
Keywords: DRNTU::Engineering::Computer science and engineering::Hardware::Performance and reliability
Issue Date: 2016
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.
URI: http://hdl.handle.net/10356/66755
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
2016 Yeo Wei Jie U1221209B - FYP Report.pdf
  Restricted Access
Final Year Project Report6 MBAdobe PDFView/Open

Page view(s)

227
Updated on Jun 25, 2022

Download(s) 50

16
Updated on Jun 25, 2022

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.