Efficient breadth first search on multi-GPU systems
Simple distributed BFS algorithms lead load unbalance among threads. Communication among tasks quickly becomes an issue. We propose a novel technique for mapping threads to data. We perform a pruning operation on the set of edges exchanged at each BFS level. Our implementation can efficiently traverse graphs with billions of nodes.
bfs gpu cuda distributed algorithm large graphs graph 500 benchmark