Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/66755
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Yeo, Wei Jie | - |
dc.date.accessioned | 2016-04-25T03:59:00Z | - |
dc.date.available | 2016-04-25T03:59:00Z | - |
dc.date.issued | 2016 | - |
dc.identifier.uri | http://hdl.handle.net/10356/66755 | - |
dc.description.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. | en_US |
dc.format.extent | 52 p. | en_US |
dc.language.iso | en | en_US |
dc.rights | Nanyang Technological University | - |
dc.subject | DRNTU::Engineering::Computer science and engineering::Hardware::Performance and reliability | en_US |
dc.title | Hardware-accelerated shortest path computation | en_US |
dc.type | Final Year Project (FYP) | en_US |
dc.contributor.supervisor | Lam Siew Kei | en_US |
dc.contributor.school | School of Computer Engineering | en_US |
dc.description.degree | Bachelor of Engineering (Computer Engineering) | en_US |
dc.contributor.supervisor2 | Lam Siew Kei | en_US |
item.fulltext | With Fulltext | - |
item.grantfulltext | restricted | - |
Appears in Collections: | SCSE Student Reports (FYP/IA/PA/PI) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2016 Yeo Wei Jie U1221209B - FYP Report.pdf Restricted Access | Final Year Project Report | 6 MB | Adobe PDF | View/Open |
Page view(s)
308
Updated on Mar 27, 2024
Download(s) 50
18
Updated on Mar 27, 2024
Google ScholarTM
Check
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.