.png){kind=icon}
Return
Efficient breadth first search on multi-GPU systems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2013.05.007.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Simple algorithms for the execution of a Breadth First Search on large graphs lead, running on clusters of GPUs, to a situation of load unbalance among threads and un-coalesced memory accesses, resulting in pretty low performances. To obtain a significant improvement on a single GPU and to scale by using multiple GPUs, we resort to a suitable combination of operations to rearrange data before processing them. We propose a novel technique for mapping threads to data that achieves a perfect load balance by leveraging prefix-sum and binary search operations. To reduce the communication overhead, we perform a pruning operation on the set of edges that needs to be exchanged at each BFS level. The result is an algorithm that exploits at its best the parallelism available on a single GPU and minimizes communication among GPUs. We show that a cluster of GPUs can efficiently perform a distributed BFS on graphs with billions of nodes. (C) 2013 Elsevier Inc. All rights reserved.
Keywords:
GPU
CUDA
BFS
Distributed algorithm
Large graphs
Graph 500 benchmark
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave no more
no more