Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/104263
Title: | Field programmable gate array-based acceleration of shortest-path computation | Authors: | Jagadeesh, George Rosario Srikanthan, T.. Lim, C. M. |
Keywords: | DRNTU::Engineering::Computer science and engineering | Issue Date: | 2011 | Source: | Jagadeesh, G. R., Srikanthan, T., & Lim, C. M. (2011). Field programmable gate array-based acceleration of shortest-path computation. IET Computers and Digital techniques, 5(4), 231 - 237. | Series/Report no.: | IET Computers and Digital techniques | Abstract: | There exist several practical applications that require high-speed shortest-path computations. In many situations, especially in embedded applications, an field programmable gate array (FPGA)-based accelerator for computing the shortest paths can help to achieve high performance at low cost. This study presents an FPGA-based distributed architecture for solving the single-source shortest-path problem in a fast and efficient manner. The proposed architecture is based on the Bellman-Ford algorithm adapted to facilitate early termination of computation. One of the novelties of the architecture is that it does not involve any centralised control and the processing elements (PEs), which are identical in construction, operate in perfect synchronisation with each other. The functional correctness of the design has been verified through simulations and also in actual hardware. It has been shown that the implementation on a Xilinx Virtex-5 FPGA is more than twice as fast as a software implementation of the algorithm on a high-end general-purpose processor that runs at an order-of-magnitude faster clock. The speed-up offered by the design can be further improved by adopting an interconnection topology that maximises the data transfer rate among the PEs. | URI: | https://hdl.handle.net/10356/104263 http://hdl.handle.net/10220/20133 |
DOI: | 10.1049/iet-cdt.2009.0072 | Schools: | School of Computer Engineering | Rights: | © 2011 The Institution of Engineering and Technology. This is the author created version of a work that has been peer reviewed and accepted for publication by IET Computers and Digital techniques, Institution of Engineering and Technology. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1049/iet-cdt.2009.0072]. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SCSE Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Post_print_version.pdf | 195.79 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
20
12
Updated on Mar 27, 2024
Web of ScienceTM
Citations
20
12
Updated on Oct 27, 2023
Page view(s) 50
610
Updated on Mar 27, 2024
Download(s) 20
319
Updated on Mar 27, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.