Bellman-Ford算法性能可移植的GPU并行优化  

Performance portable GPU parallel optimization technique on Bellman-Ford algorithm

作　　者：刘磊[1] 王燕燕[1] 申春[1] 李玉祥 刘雷[3] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]中信证券有限公司,北京100026 [3]中国科学院计算技术研究所,北京100190

出　　处：《吉林大学学报（工学版）》2015年第5期1559-1564,共6页Journal of Jilin University:Engineering and Technology Edition

基　　金：吉林省重大科技攻关项目(20130206052GX);'863'国家高技术研究发展计划项目(2012AA010902);'973'国家重点基础研究计划项目(2011CB302500)

摘　　要：提出了一种面向GPU的性能可移植的并行归约求极值优化算法和全局访存优化算法,对Bellman-Ford算法进行并行化改造,以解决不同类型GPU设备上都存在的并行粒度不足和全局内存访问不连续等问题。实验结果表明：本文的优化算法在NVIDIA和AMD的多款GPU设备上都取得了很好的效果,经本文算法优化后的程序性能较原始GPU并行版本提升3~6倍。A GPU-oriented performance portable parallel reduction algorithm for extreme value optimization and a global memory access optimization algorithm are presented to resolve the issues of deficient parallel granularity and global memory access conflict on different GPUs.Experimental results show that the presented optimization algorithms can obtain high performance on a variety of NVIDIA and AMD GPU devices,gaining a speedup of 3to 6times than existing methods.

关 键 词：计算机软件 Bellman-Ford算法 GPU并行编程及优化技术 并行归约算法 性能可移植性 

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