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

作     者：余莹 李肯立 郑光勇 YU Ying;LI Ken-li;ZHENG Guang-yong

作者机构：衡阳师范学院计算机科学系衡阳421002 湖南大学信息科学与工程学院长沙410082 

基　　金：国家自然科学基金项目(61370095 61370098 61070057 90715029) 湖南省教育厅科学研究一般项目(13C074) 衡阳市科技局科技发展计划项目(2011KJ22)资助 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2015年第42卷第1期

页      码：82-85页

摘      要：深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低。为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排。提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡。为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作。实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销。在一个GPU集群中,它可以对含有数十亿节点的图有效地执行分布式DFS。

主 题 词：GPU 深度优先搜索(DFS) 分布式算法 CUDA MPI 

学科分类：08[工学] 080203[080203] 0802[工学-机械学] 

D　O　I：10.11896/j.issn.1002-137X.2015.1.019

馆 藏 号：203105873...