Hardware-accelerated shortest path computation
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/66755 |
| _version_ | 1811691892374503424 |
|---|---|
| author | Yeo, Wei Jie |
| author2 | Lam Siew Kei |
| author_facet | Lam Siew Kei Yeo, Wei Jie |
| author_sort | Yeo, Wei Jie |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T06:27:06Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/66755 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:27:06Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | ntu-10356/667552023-03-03T20:38:08Z Hardware-accelerated shortest path computation Yeo, Wei Jie Lam Siew Kei School of Computer Engineering Lam Siew Kei DRNTU::Engineering::Computer science and engineering::Hardware::Performance and reliability 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. Bachelor of Engineering (Computer Engineering) 2016-04-25T03:59:00Z 2016-04-25T03:59:00Z 2016 Final Year Project (FYP) http://hdl.handle.net/10356/66755 en Nanyang Technological University 52 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Computer science and engineering::Hardware::Performance and reliability Yeo, Wei Jie Hardware-accelerated shortest path computation |
| title | Hardware-accelerated shortest path computation |
| title_full | Hardware-accelerated shortest path computation |
| title_fullStr | Hardware-accelerated shortest path computation |
| title_full_unstemmed | Hardware-accelerated shortest path computation |
| title_short | Hardware-accelerated shortest path computation |
| title_sort | hardware accelerated shortest path computation |
| topic | DRNTU::Engineering::Computer science and engineering::Hardware::Performance and reliability |
| url | http://hdl.handle.net/10356/66755 |
| work_keys_str_mv | AT yeoweijie hardwareacceleratedshortestpathcomputation |