A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA-Compatible GPU

Tomohiro Okuyama, Fumihiko Ino, Kenichi Hagihara
Graduate School of Information Science and Technology, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan
Proceedings of 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications (2008)


   title={A task parallel algorithm for computing the costs of all-pairs shortest paths on the CUDA-compatible GPU},

   author={Okuyama, T. and Ino, F. and Hagihara, K.},

   booktitle={Parallel and Distributed Processing with Applications, 2008. ISPA’08. International Symposium on},





Download Download (PDF)   View View   Source Source   



This paper proposes a fast method for computing the costs of all-pairs shortest paths (APSPs) on the graphics processing unit (GPU). The proposed method is implemented using compute unified device architecture (CUDA), which offers us a development environment for performing general-purpose computation on the GPU. Our method is based on Harish’s iterative algorithm that computes the cost of the single-source shortest path (SSSP) for every source vertex. We present that exploiting task parallelism in the APSP problem allows us to efficiently use on-chip memory in the GPU, reducing the amount of data being transferred from relatively slower off-chip memory. Furthermore, our task parallel scheme is useful to exploit a higher parallelism, increasing the efficiency with highly threaded code. As a result, our method is 3.4-15 times faster than the prior method. Using on-chip memory, our method eliminates approximately 20% of data loads from off-chip memory.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: