基于GPU的Bor?vka最小生成树改进算法

• 作者: 刘成安 印茂伟 吴永存
• 来源期刊: 科技通报
• 学科: 工学
• 关键词: Bor?vka 最小生成树 GPU 邻接表
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 工业技术
• 页码范围: 95-99
• 页数: 5页
• 分类号: TP311.52
• 字数: 2800字
• 语种: 中文
• DOI: 10.13774/j.cnki.kjtb.2017.02.022

摘要

为了提高Bor?vka最小生成树算法的效率,本文基于NVIDIA GPU提出一种并行Bor?vka算法,设计了适用于GPU通用并行计算架构的邻接表图存储方式,通过避免Bor?vka算法每次迭代后的破圈操作以及合并超节点后的数据重组操作,并将算法中具有并行特性的部分移植到GPU并行执行,从而提高了算法的效率.实验表明,相比于CPU版Bor?vka算法,该算法具有较为明显的加速效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘成安	西南科技大学国防科技学院	33	177	8.0	12.0
2	印茂伟	西南科技大学国防科技学院	17	23	3.0	3.0
3	吴永存	西南科技大学国防科技学院	2	0	0.0	0.0