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

Abstract: 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.

Key words: GPU,DFS,Distributed algorithm,CUDA,MPI