All-pairs Shortest Path Algorithm based on MPI+CUDA Distributed Parallel Programming Model

Wu Qingshuang, Tong Chunya, Wang Qiang, Cheng Xiangfu
College of Territorial Resources and Tourism, Anhui Normal University, Wuhu, Anhui, 241003, China
Journal of Networks, Vol. 8, No. 12, 2013


   title={All-pairs Shortest Path Algorithm based on MPI+ CUDA Distributed Parallel Programming Model},

   author={Wu, Qingshuang and Tong, Chunya and Wang, Qiang and Cheng, Xiangfu},

   journal={Journal of Networks},






Download Download (PDF)   View View   Source Source   



In view of the problem that computing shortest paths in a graph is a complex and time-consuming process, and the traditional algorithm that rely on the CPU as computing unit solely can’t meet the demand of real-time processing, in this paper, we present an all-pairs shortest paths algorithm using MPI+CUDA hybrid programming model, which can take use of the overwhelming computing power of the GPU cluster to speed up the processing. This proposed algorithm can combine the advantages of MPI and CUDA programming model, and can realize two-level parallel computing. In the cluster-level, we take use of the MPI programming model to achieve a coarse-grained parallel computing between the computational nodes of the GPU cluster. In the node-level, we take use of the CUDA programming model to achieve a GPU-accelerated fine grit parallel computing in each computational node internal. The experimental results show that the MPI+CUDA-based parallel algorithm can take full advantage of the powerful computing capability of the GPU cluster, and can achieve about hundreds of time speedup; The whole algorithm has good computing performance, reliability and scalability, and it is able to meet the demand of real-time processing of massive spatial shortest path analysis.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: