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

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