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

Implementation of Depth First Search Parallel Algorithm on Cluster of GPUs

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

Straightforward implementation of depth first search algorithm for large graph on GPU cluster,may lead to load imbalance between threads and un-coalesced memory accesses,giving rise to the low performance of the algorithm.In order to achieve improvement of the performance in a single GPU and multi-GPUs environment,a series of effective operations were used to reschedule before processing the data.A novel strategy for mapping between threads and data was proposed,and by using the prefix sum and binary search operations,load balancing was achieved perfectly.In order to reduce the communication overhead,we performed pruning operation on the set of edges which needs to be exchanged at all branches of DFS.Experimental results show that the algorithm can achieve its best parallelism available on a single GPU and minimize communication overhead among GPUs.GPU cluster can effectively perform the distributed DFS on graphs which contain billions of nodes.