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

• 作者: 方浩 赵国兴 邢星星 骆祖莹
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 全源最短路径 GPU 棋盘划分 Floyd算法
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 体系结构
• 页码范围: 299-303
• 分类号: TP311
• 字数: 5989字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.03.069

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邢星星	北京师范大学信息科学与技术学院	1	7	1.0	1.0
2	赵国兴	北京师范大学信息科学与技术学院	8	39	4.0	6.0
3	骆祖莹	北京师范大学信息科学与技术学院	28	143	7.0	11.0
4	方浩	北京师范大学信息科学与技术学院	1	7	1.0	1.0