Asian Institute of Technology; Chulalongkorn University; National Science & Technology Development Agency - Thailand; National Electronics & Computer Technology Center (NECTEC); University System of Georgia; Georgia Institute of Technology; Universidade do Minho
Type
Article
Source Title
IEICE ELECTRONICS EXPRESS
Year
2016
Volume
13
Issue
6
Open Access
gold
Publisher
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
DOI
10.1587/elex.13.20160036
Format
PDF
Abstract
The bidirectional shortest path problem has important applications in VLSI floor planning and other areas. We introduce a new algorithm to solve bidirectional shortest path problems using parallel architectures provided by general purpose computing on graphics processing units. The algorithm performs parallel searches from the source and sink using Dijkstra's classic approach modified with pruning and early termination. We achieve substantial speedup over a parallel method that performs a single parallel search on the GPGPU from the source to all other nodes but early terminates when the shortest path to the specified target node is found. Experimental results demonstrate a speedup of nearly 2x over the parallel method that performs a parallel search from the source with early termination on the GPGPU.
