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

摘要：

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

关键词：GPU、深度优先搜索(DFS)、分布式算法、CUDA、MPI

所属期刊栏目：42

分类号：TP391.9(计算技术、计算机技术)

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

在线出版日期：2015-02-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：82-85