A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA-Compatible GPU
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)
@conference{okuyama2008task,
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},
pages={284–291},
year={2008},
organization={IEEE}
}
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.
November 5, 2010 by hgpu
