基于GPU的并行APSP问题的研究  

Research of parallel APSP on GPU

作　　者：张凌洁[1] 赵英[1] 

机构地区：[1]北京化工大学,北京100029

出　　处：《电子设计工程》2012年第17期15-18,22,共5页Electronic Design Engineering

摘　　要：Floyd-Warshall算法是图论中APSP(All-Pair Shortest Paths)问题的经典算法,为了加快计算速度,提出使用GPU通用计算来实现。文章先从算法的原理入手,层层深入,提出了可以在GPU上运行的并行F-W算法。之后,又根据矩阵分块的原理和GPU共享存储器的使用,实现了改进的GPU并行F-W算法。通过大量测试实验,得到了该GPU并行程序相对于传统CPU并行程序产生超过百倍的加速比的结论。How to use GPU-based Floyd-Warshall algorithm to deal with the APSP （All-Pair Shortest Paths） problem in graph theory is introduced. First, on the basis of the principle of F-W algorithm, its parallelized version is put forwards on GPU. Then, according to the matrix segmentation and the exploit of the shared memory in GPU, an improved parallel version of F-W algorithm on GPU is introdctced. At last, we make a comprehensive comparison and analysis of these algorithms, the speedup is over 100x.

关 键 词：Floyd—Warshall算法 APSP GPU 高性能计算 共享存储器 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]