TY - GEN
T1 - Task-based parallel breadth-first search in heterogeneous environments
AU - Munguia, Lluis Miquel
AU - Bader, David A.
AU - Ayguade, Eduard
PY - 2012
Y1 - 2012
N2 - Breadth-first search (BFS) is an essential graph traversal strategy widely used in many computing applications. Because of its irregular data access patterns, BFS has become a non-trivial problem hard to parallelize efficiently. In this paper, we introduce a parallelization strategy that allows the load balancing of computation resources as well as the execution of graph traversals in hybrid environments composed of CPUs and GPUs. To achieve that goal, we use a fine-grained task-based parallelization scheme and the OmpSs programming model. We obtain processing rates up to 2.8 billion traversed edges per second with a single GPU and a multi-core processor. Our study shows high processing rates are achievable with hybrid environments despite the GPU communication latency and memory coherence.
AB - Breadth-first search (BFS) is an essential graph traversal strategy widely used in many computing applications. Because of its irregular data access patterns, BFS has become a non-trivial problem hard to parallelize efficiently. In this paper, we introduce a parallelization strategy that allows the load balancing of computation resources as well as the execution of graph traversals in hybrid environments composed of CPUs and GPUs. To achieve that goal, we use a fine-grained task-based parallelization scheme and the OmpSs programming model. We obtain processing rates up to 2.8 billion traversed edges per second with a single GPU and a multi-core processor. Our study shows high processing rates are achievable with hybrid environments despite the GPU communication latency and memory coherence.
UR - http://www.scopus.com/inward/record.url?scp=84880279026&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880279026&partnerID=8YFLogxK
U2 - 10.1109/HiPC.2012.6507474
DO - 10.1109/HiPC.2012.6507474
M3 - Conference contribution
AN - SCOPUS:84880279026
SN - 9781467323703
T3 - 2012 19th International Conference on High Performance Computing, HiPC 2012
BT - 2012 19th International Conference on High Performance Computing, HiPC 2012
T2 - 2012 19th International Conference on High Performance Computing, HiPC 2012
Y2 - 18 December 2012 through 21 December 2012
ER -