一种基于GPU集群的深度优先并行算法设计与实现

发布时间：2018-10-13 18:01

【摘要】：深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低。为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排。提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡。为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作。实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销。在一个GPU集群中,它可以对含有数十亿节点的图有效地执行分布式DFS。
[Abstract]:The simple execution of the depth-first search algorithm on a large graph in a GPU cluster will lead to the imbalance of the load between threads and the inability to merge memory access, which makes the performance of the algorithm low. In order to improve the performance of the algorithm in a single GPU and multiple GPU environments, a series of effective operations are taken to rearrange the data before processing. A new technique is proposed to construct the mapping between threads and data, which can achieve perfect load balance by using prefix summation and binary lookup operations. In order to reduce communication overhead, pruning operations are performed on edge sets that need to be exchanged in each branch of DFS. Experimental results show that the algorithm can achieve the best parallelism on a single GPU and minimize the communication overhead in a multi-GPU environment. In a GPU cluster, it can effectively execute distributed DFS. on a graph with billions of nodes
【作者单位】： 衡阳师范学院计算机科学系;湖南大学信息科学与工程学院;
【基金】：国家自然科学基金项目(61370095,61370098,61070057,90715029) 湖南省教育厅科学研究一般项目(13C074) 衡阳市科技局科技发展计划项目(2011KJ22)资助
【分类号】：TP338.6

【参考文献】

相关期刊论文 前4条

1 卢风顺;宋君强;银福康;张理论;;CPU/GPU协同并行计算研究综述[J];计算机科学;2011年03期

2 李文超;严洪森;;一种基于PFSP性质的深度优先搜索算法[J];控制与决策;2009年08期

3 王海峰;陈庆奎;;图形处理器通用计算关键技术研究综述[J];计算机学报;2013年04期

4 吴鸿伟;汤伟宾;李晓潮;郭东辉;;GPU编程原理及其在网络安全领域的应用算法分析[J];计算机科学;2012年S3期

【共引文献】

相关期刊论文 前10条

1 王加亮;秦勃;刘健健;刘妮;;基于MapReduce的交互可视化平台[J];电信科学;2012年09期

2 杨芳菊;;基于CPU/GPU异构平台并行优化的研究[J];电脑编程技巧与维护;2012年18期

3 刘军志;朱阿兴;秦承志;陈腊娇;吴辉;江净超;;分布式水文模型的并行计算研究进展[J];地理科学进展;2013年04期

4 邹航;王华秋;黄勇;;基于GPU加速的彩虹表分析MD5哈希密码[J];重庆理工大学学报(自然科学);2013年07期

5 方留杨;王密;李德仁;;CPU和GPU协同处理的光学卫星遥感影像正射校正方法[J];测绘学报;2013年05期

6 刘艺;陈明生;吴先良;齐琦;;应用GPU加速结合压缩传感技术解宽角度电磁散射问题[J];合肥师范学院学报;2013年06期

7 杨清山;刘X;熊飞;钟立俊;邴丕浩;;基于GPU的并行区域场强计算[J];电子信息对抗技术;2013年06期

8 李杰;陈庆奎;;基于蓝牙4.0的GPU集群功耗测量系统设计[J];电子测量与仪器学报;2014年03期

9 方留杨;王密;李德仁;潘俊;;负载分配的CPU/GPU高分辨率卫星影像调制传递补偿方法[J];测绘学报;2014年06期

10 洪亮;周松涛;罗伊;石婷婷;胡飞;;海量遥感数据的GPU通用加速计算技术[J];地理空间信息;2014年03期

相关会议论文 前1条

1 ;Research on DSP-GPU Heterogeneous Computing System[A];Information Technology and Computer Science—Proceedings of 2012 National Conference on Information Technology and Computer Science[C];2012年

相关博士学位论文 前7条

1 曹闻;时空数据模型及其应用研究[D];解放军信息工程大学;2011年

2 江涵;大规模电力系统暂态稳定并行计算研究[D];浙江大学;2012年

3 周勇;基于并行计算的数据流处理方法研究[D];大连理工大学;2013年

4 韩宇韬;数字正射影像镶嵌中色彩一致性处理的若干问题研究[D];武汉大学;2014年

5 刘寿生;虚拟现实仿真平台异构并行计算关键技术研究[D];中国海洋大学;2014年

6 杨蒙召;人体面部真实感快速渲染方法研究[D];哈尔滨工业大学;2014年

7 崔树林;基于GPU的并行矢量数据分析与索引技术研究[D];中国科学院研究生院（东北地理与农业生态研究所）;2014年

相关硕士学位论文 前10条

1 杨博;深穿透粒子输运蒙特卡罗模拟的CPU/GPU协同算法研究[D];国防科学技术大学;2011年

2 石志才;异构平台上协同计算的相关研究[D];国防科学技术大学;2011年

3 王翔;球谐函数展开快速算法及其并行算法研究[D];国防科学技术大学;2011年

4 吕东川;基于并行计算的脑电信号分析方法研究[D];燕山大学;2012年

5 栗超;一种三维可视化系统的优化策略[D];燕山大学;2012年

6 刁兴光;独立成分算法在GPU上的实现[D];大连理工大学;2012年

7 赵琳琳;非均匀地层随钻电磁波测井电磁响应的研究[D];山东大学;2012年

8 李国栋;基于异构计算平台的列数据库并行查询技术研究与实现[D];华南理工大学;2012年

9 沈玉琳;通用GPU计算技术在高性能计算平台上的应用研究[D];兰州大学;2012年

10 周智强;基于图像融合和模糊聚类的SAR图像变化检测[D];西安电子科技大学;2012年

【二级参考文献】

相关期刊论文 前10条

1 越民义,韩继业;n个零件在m台机床上的加工顺序问题(Ⅰ)[J];中国科学;1975年05期

2 ;Multi-scale HPC system for multi-scale discrete simulation—Development and application of a supercomputer with 1 Petaflops peak performance in single precision[J];Particuology;2009年04期

3 吴恩华,柳有权;基于图形处理器(GPU)的通用计算[J];计算机辅助设计与图形学学报;2004年05期

4 韩博;周秉锋;;GPGPU性能模型及应用实例分析[J];计算机辅助设计与图形学学报;2009年09期

5 伍楠;文梅;何义;荀长庆;任巨;柴俊;张春元;;一种流处理器体系结构MASA及其在流体力学计算中的评测[J];计算机学报;2008年01期

6 周国亮;陈红;李翠平;王珊;郑涛;;基于图形处理器的并行方体计算[J];计算机学报;2010年10期

7 越民义,韩继业;同顺序m×n排序问题的一个新方法[J];科学通报;1979年18期

8 金锋;宋士吉;吴澄;;一类基于FSP问题Block性质的快速TS算法[J];控制与决策;2007年03期

9 李建明;迟忠先;万单领;;一种基于GPU加速细粒度并行遗传算法的实现方法[J];控制与决策;2008年06期

10 李建明;胡祥培;庞占龙;钱昆明;;一种基于GPU加速的细粒度并行蚁群算法[J];控制与决策;2009年08期

相关硕士学位论文 前2条

1 吴强;GPU加速高速粒子碰撞模拟[D];国防科学技术大学;2009年

2 方旭东;面向大规模科学计算的CPU-GPU异构并行技术研究[D];国防科学技术大学;2009年

【相似文献】

相关期刊论文 前10条

1 龚建华;;深度优先搜索算法及其改进[J];现代电子技术;2007年22期

2 张选平,杭省策;利用深度优先搜索方法求解作业排序[J];系统工程与电子技术;1998年08期

3 虞成诚;钟声;胡绍华;;基于深度优先搜索的一般图匹配算法[J];计算机工程与科学;2008年12期

4 袁和金;张艳宁;周涛;;基于矢量量化和深度优先搜索的轨迹分布模式学习算法[J];计算机应用;2007年05期

5 蔡乐才;朱颢东;;基于AI问题的一种“最优”解方法及实现[J];四川理工学院学报(自然科学版);2008年05期

6 刘中华;张颖超;;深度优先搜索的非递归算法[J];科技信息;2010年25期

7 苏兆锋;求解连通图关节点的一种新的思考方法[J];微机发展;2002年04期

8 梅义;丘东元;张波;;基于深度优先搜索的潜在电路计算机辅助分析法[J];中国电机工程学报;2008年24期

9 姚佳;谭学琴;;利用深度优先搜索实现无线频率规划[J];电脑编程技巧与维护;2014年08期

10 刘萍;冯桂莲;;图的深度优先搜索遍历算法分析及其应用[J];青海师范大学学报(自然科学版);2007年03期

相关会议论文 前1条

1 张洪波;杨海峰;王进杰;;CAPP和PCCAD中工艺树的规划与建立[A];制造业与未来中国——2002年中国机械工程学会年会论文集[C];2002年

相关硕士学位论文 前2条

1 郑丹;流体网络中单向回路问题的研究[D];辽宁工程技术大学;2004年

2 石佳玉;基于时延特性的网络拓扑推断技术研究[D];兰州交通大学;2014年

，

本文编号：2269462