Name
Abstract | ||
|---|---|---|
Graphs are a fundamental data representation that has been used extensively in various domains. In graph-based applications, a systematic exploration of the graph such as a breadth-first search (BFS) often serves as a key component in the processing of their massive data sets. In this paper, we present a new method for implementing the parallel BFS algorithm on multi-core CPUs which exploits a fundamental property of randomly shaped real-world graph instances. By utilizing memory bandwidth more efficiently, our method shows improved performance over the current state-of-the-art implementation and increases its advantage as the size of the graph increases. We then propose a hybrid method which, for each level of the BFS algorithm, dynamically chooses the best implementation from: a sequential execution, two different methods of multicore execution, and a GPU execution. Such a hybrid approach provides the best performance for each graph size while avoiding poor worst-case performance on high-diameter graphs. Finally, we study the effects of the underlying architecture on BFS performance by comparing multiple CPU and GPU systems, a high-end GPU system performed as well as a quad-socket high-end CPU system. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/PACT.2011.14 | PACT |
Keywords | Field | DocType |
parallel graph exploration,graph size,high-diameter graph,bfs performance,bfs algorithm,gpu execution,graph increase,real-world graph instance,poor worst-case performance,best performance,multi-core cpu,parallel bfs algorithm,memory bandwidth,system performance,coprocessors,bandwidth,bfs,graph,parallel processing,data representation,graph theory,optimization,breadth first search | Graph theory,Memory bandwidth,Computer science,CUDA,Parallel computing,Breadth-first search,Coprocessor,Graphics processing unit,Multi-core processor,Graph500 | Conference |
Citations | PageRank | References |
130 | 4.60 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sungpack Hong | 1 | 864 | 33.20 |
| Tayo Oguntebi | 2 | 360 | 13.47 |
| Kunle Olukotun | 3 | 4532 | 373.50 |