A Parallel Recursive Approach for Solving All Pairs Shortest Path Problem on GPU using OpenCL
Department of Computer Science Engineering, Maulana Azad National Institute of Technology, Bhopal, India
International Journal of Computer Science and Information Technologies (IJCSIT), Vol. 5 (6), 2014
@article{pandey2014parallel,
title={A Parallel Recursive Approach for Solving All Pairs Shortest Path Problem on GPU using OpenCL},
author={Pandey, Manish and Sharma, Sanjay},
year={2014}
}
All-pairs shortest path problem(APSP) finds a large number of practical applications in real world. We owe to present a highly parallel and recursive solution for solving APSP problem based on Kleene’s algorithm. The proposed parallel approach for APSP is implemented using an open standard framework OpenCL which provides a development environment for utilizing massive parallel capabilities of Multi core CPU and Many-Core-Processors such as Graphics Processing Unit (GPU). Moreover due to inherent nature of data reuse in the algorithm, shared memory of these processors is exploited to achieve considerable speedup. Our experiments demonstrate a speedup gain up to 521x over NVIDIA GeForce GT 630M GPU and a speedup up to 10x over Intel Core i3-2310M CPU.The proposed OpenCL solution for APSP is for directed and dense graphs with no negative cycles. Like Floyd-Warshall (FW), this approach is also in-place in nature and therefore requires no extra space.
December 20, 2014 by hgpu
