Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKhoo, Gilbert Teng Sheng-
dc.description.abstractUndeniably, autonomous vehicles have found its position within the vehicle industry. In the absence of human drivers, the vehicle is fully reliant on the on-board computers for navigation, collision avoidance, etc. For transportation, shortest path computation plays a crucial role, where besides providing the shortest path, the demand for shorter computation time is increasing from time to time, so as to adapt to the frequent changing of traffic conditions. In this project, we investigate hardware efficient architectures for shortest path computations that is based on a novel shortest path algorithm. We show that the proposed architecture is able to reduce the total amount of computations for nodes relaxations compared to the hardware implementation of the conventional Bellman- Ford algorithm,. This is achieved by incorporating Node filtering to avoid unnecessary computations. In addition, the nodes relaxation process in the proposed architecture adopts the SIMD model, where the tentative distance for neighbours of a single node can be computed in parallel. We also explored the utilization of various caches and their configurations to determine a good trade-off between performance and logic area utilization. We compared the performance of the hardware simulation model of the proposed algorithm and conventional Bellman-Ford algorithms using Singapore Roadway Network, which consists of 140219 nodes and 193071 edges. The experimental results show that the proposed architecture leads to over 40% performance improvement.en_US
dc.format.extent58 p.en_US
dc.rightsNanyang Technological University-
dc.subjectDRNTU::Engineering::Computer science and engineeringen_US
dc.titleShortest path computation for roadway networken_US
dc.typeFinal Year Project (FYP)en_US
dc.contributor.supervisorLam Siew Keien_US
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.description.degreeBachelor of Engineering (Computer Engineering)en_US
item.fulltextWith Fulltext-
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)
Files in This Item:
File Description SizeFormat 
  Restricted Access
4.12 MBAdobe PDFView/Open

Page view(s)

Updated on Jun 23, 2021

Download(s) 50

Updated on Jun 23, 2021

Google ScholarTM


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