基于GPU的并行最小生成树算法的设计与实现

• 作者: 王伟 王磊 郭绍忠
• 来源期刊: 计算机应用研究
• 关键词: 图形处理器 图论 最小生成树 Prim算法 数据并行原语
• 年，卷（期）: 2011,（5）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1682-1684,1702
• 分类号: TP311.52
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2011.05.025

摘要

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法.该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率.实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王磊	解放军信息工程大学信息工程学院	13	108	5.0	10.0
2	郭绍忠	解放军信息工程大学信息工程学院	15	124	7.0	11.0
3	王伟	解放军信息工程大学信息工程学院	3	15	2.0	3.0