吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (5): 1559-1564.doi: 10.13229/j.cnki.jdxbgxb201505026

• • 上一篇    下一篇

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

刘磊1, 王燕燕1, 申春1, 李玉祥2, 刘雷3   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.中信证券有限公司,北京 100026;
    3.中国科学院 计算技术研究所,北京 100190
  • 收稿日期:2014-05-06 出版日期:2015-09-01 发布日期:2015-09-01
  • 通讯作者: 申春(1971-),女,讲师,博士.研究方向:软件理论与技术.E-mail:shenchun@jlu.edu.cn
  • 作者简介:刘磊(1960-）,男,教授,博士生导师.研究方向:软件理论与技术.E-mail:liulei@jlu.edu.cn
  • 基金资助:
    吉林省重大科技攻关项目(20130206052GX); “863”国家高技术研究发展计划项目(2012AA010902); “973”国家重点基础研究计划项目(2011CB302500)

Performance portable GPU parallel optimization technique on Bellman-Ford algorithm

LIU Lei1, WANG Yan-yan1, SHEN Chun1, LI Yu-xiang2, LIU Lei3   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Citic Securities Co., Ltd., Beijing 100026, China;
    3.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2014-05-06 Online:2015-09-01 Published:2015-09-01

RICH HTML

0   

PDF (PC)

402

摘要： 提出了一种面向GPU的性能可移植的并行归约求极值优化算法和全局访存优化算法,对Bellman-Ford算法进行并行化改造,以解决不同类型GPU设备上都存在的并行粒度不足和全局内存访问不连续等问题。实验结果表明:本文的优化算法在NVIDIA和AMD的多款GPU设备上都取得了很好的效果,经本文算法优化后的程序性能较原始GPU并行版本提升3~6倍。

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

Abstract: 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 3 to 6 times than existing methods.

Key words: computer software, Bellman-Ford algorithm, GPU parallel programing and optimization techniques, parallel reduction algorithm, performance portability

中图分类号: 

  • TP302
[1] Tehrani Pouya, Zhao Qing. Distributed online learning of the shortest path under unknown random edge weights[C]∥IEEE International Conference on Acoustics, Speech and Signal Processing, Vancouver,BC,2013:3138-3142.
[2] Carli M, Panzieri S, Pascucci F. A joint routing and localization algorithm for emergency scenario[J]. Ad Hoc Networks, 2014, 13:19-33.
[3] Tewari A,Kumar D A.Different routing algorithm for computer networks[J].Kaav International Journal of Science, Engineering & Technology,2014,1(1):21-34.
[4] Abouali M, Timmermans J, Castillo J E, et al. A high performance GPU implementation of Surface energy balance system (SEBS) based on CUDA-C[J]. Environmental Modelling & Software, 2013, 41: 134-138.
[5] Huang B, Mielikainen J, Oh H, et al. Development of a GPU-based high-performance radiative transfer model for the Infrared atmospheric sounding interferometer (IASI)[J]. Journal of Computational Physics, 2011, 230(6): 2207-2221.
[6] Singh D P, Khare N. A study of different parallel implementations of single source shortest path algorithms[J]. International Journal of Computer Applications, 2012, 54(10):26-30.
[7] 颜深根, 张云泉, 龙国平, 等. 基于OpenCL的归约算法优化[J]. 软件学报, 2011, 22(2): 163-171. Yan Shen-gen,Zhang Yun-quan,Long Guo-ping,et al.Reduction algorithm optimization based on the OpenCL[J].Journal of Software,2011,22(2):163-171.
[8] Kumar S, Misra A, Tomar R S. A modified parallel approach to single source shortest path problem for massively dense graphs using CUDA[C]∥2011 2nd International Conference on Computer and Communication Technology, Allahabod,2011: 635-639.
[9] Lee Jaejin, Kim Jungwon,Seo Sangmin.An OpenCL framework for heterogenous multicores with local memory[C]∥Proceeding of the 19th International Conference on Parallel Architectures and Compilation Techiniques,ACM New York,NY,USA,2010:193-204.
[10] 贾海鹏, 张云泉, 龙国平, 等. 基于 OpenCL 的拉普拉斯图像增强算法优化研究[J]. 计算机科学, 2012, 39(5): 271-277. Jia Hai-peng, Zhang Yun-quan, Long Guo-ping, et al. Research on laplace image enhancement algorithm optimization base on OpenCL[J]. Computer Science, 2012, 39(5):271-277.
[11] NVIDIA.NVIDIA's Next Generation CUDA Compute Architecture:Kepler GK110[EB/OL].[2013-06-28].http://www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf.
[12] NVIDIA. NVIDIA's next generation CUDA TM compute architecture, Fermi[EB/OL].[2013-05-22].http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf.
[1] 马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2] 罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[3] 应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[4] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[5] 王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[6] 特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[7] 康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[8] 陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[9] 冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[10] 李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[11] 王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[12] 黄宏涛，王静，叶海智，黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
[13] 范大娟1, 2, 黄志球1, 肖芳雄1, 祝义1, 王进1. 面向多服务交互的相容性分析与适配器生成[J]. 吉林大学学报(工学版), 2014, 44(4): 1094-1103.
[14] 贺秦禄1, 李战怀1, 王乐晓1, 王瑞2. 云存储系统聚合带宽测试技术[J]. 吉林大学学报(工学版), 2014, 44(4): 1104-1111.
[15] 康辉, 张双双, 梅芳. 一种递归π演算向Petri网的转换方法[J]. 吉林大学学报(工学版), 2014, 44(01): 142-148.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发