13258

A Parallel Recursive Approach for Solving All Pairs Shortest Path Problem on GPU using OpenCL

Manish Pandey, Sanjay Sharma
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}

}

Download Download (PDF)   View View   Source Source   

1053

views

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.
Rating: 0.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: