Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/HiPC.2012.6507474 | High Performance Computing |
Keywords | DocType | ISSN |
graph theory,graphics processing units,multiprocessing systems,parallel processing,resource allocation,tree searching,bfs,cpu,gpu communication latency,ompss programming model,computation resource,fine-grained task-based parallelization scheme,graph traversal strategy,heterogeneous environment,hybrid environment,irregular data access pattern,load balancing,memory coherence,multicore processor,parallelization strategy,processing rate,task-based parallel breadth-first search,graphs | Conference | 1094-7256 |
ISBN | Citations | PageRank |
978-1-4673-2370-3 | 7 | 0.48 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lluis-Miquel Munguia | 1 | 7 | 0.48 |
| Bader, David A. | 2 | 2507 | 219.90 |
| Eduard Ayguadé | 3 | 23 | 2.38 |