基于GPU的全源最短路径算法

GPU-based Algorithm of Shortest Path

针对有向图中每对顶点之间的最短路径问题,基于CPU集群并行算法,根据GPU并行计算加速机制,提出了基于棋盘划分方式的GPU并行算法,以增加算法的并行性与数据的局部性。当有向图规模超过GPU显存限制时,进一步提出了异步并行处理的GPU最短路径算法。实验结果表明,与CPU上单核算法相比,本算法具有如下加速效果:(1)对于节点数少于10000的小规模有向图,可以实现约155倍的加速;(2)对于节点数超过10000的大规模有向图,可实现约25倍的加速。

As for the all-pairs shortest-path problem in the graph, based on parallel algorithm in the CPU cluster environment, depending on parallel speedup mechanism on the GPU, in order to increase the parallelism and locality, chessboard division method was chosen for task division in this parallel algorithm on the GPU. Because the graph scale is larger than the display memory, the asynchronous parallel algorithm on the GPU was presented. The experimental data proves that the algorithm has accelerating effects below compared with CPU with single core： first, for the small graph whose vertexes are less than 10000, it is about 155 times faster; second, for the large graph whose vertexes are more than 10000,it is about 25 times faster.