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

Improved Algorithm of GPU-based Bor?vka Minimum Spanning Tree

作　　者：吴永存[1] 刘成安[1] 印茂伟[1] Wu Yongcun;Liu Chengan;Yin Maowei(School of National Defense Science and Technology,Southwest University of Science and Technology,Mianyang Sichuan 621010,China)

机构地区：[1]西南科技大学国防科技学院,四川绵阳621010

出　　处：《科技通报》2017年第2期95-99,共5页Bulletin of Science and Technology

基　　金：国家科技支撑计划项目(20BBAH32F00);中国物理研究院横向项目(13zh0179);自然科学基金重点基金(11035004);自然科学基金青年基金(51407169);自然科学基金青年基金(51407169);中物院科学技术发展基金(2013A0402018);西南科技大学博士基金项目(13ZX7106);浙江省科技计划项目(2013C33073)~~

摘　　要：为了提高Bor?vka最小生成树算法的效率,本文基于NVIDIA GPU提出一种并行Bor?vka算法,设计了适用于GPU通用并行计算架构的邻接表图存储方式,通过避免Bor?vka算法每次迭代后的破圈操作以及合并超节点后的数据重组操作,并将算法中具有并行特性的部分移植到GPU并行执行,从而提高了算法的效率。实验表明,相比于CPU版Bor?vka算法,该算法具有较为明显的加速效果。In order to improve the efficiency of Boruvka minimum spanning tree algorithm, this paper propopsed a NVIDIA GPU- based parallel Boruvka algorithm, and designed a adjacency list graph storage suited to GPU CUDA. By avoiding breaking circle after each iteration and data reorganization operations after merging super node in Boruvka algorithm, and porting the parts of the algorithm with parallel characteristics to the GPU for executing parallel. Experimental results show that it has obvious acceleration effect over the GPU Bor?vka implementation.

关 键 词：Boruvka 最小生成树 GPU 邻接表 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]