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 SizeFormat 
Post_print_version.pdf195.79 kBAdobe PDFThumbnail
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


Plumx

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