Name
Abstract | ||
|---|---|---|
Graph is a widely used data structure and graph algorithms, such as breadth-first search (BFS), are regarded as key components in a great number of applications. Recent studies have attempted to accelerate graph algorithms on highly parallel graphics processing unit (GPU). Although many graph algorithms based on large graphs exhibit abundant parallelism, their performance on GPU still faces formidable challenges, one of which is to map the irregular computation onto GPU's vectorized execution model. In this paper, we investigate the link between graph topology and performance of BFS on GPU. We introduce a novel model to analyze the components of SIMD underutilization. We show that SIMD lanes are wasted either due to the workload imbalance between tasks, or to the heterogeneity of each task. We also develop corresponding metrics to quantify the SIMD efficiency for BFS on GPU. Finally, we demonstrate the applicability of the metrics by using them to profile the performance for different mapping strategies. |
Year | Venue | Keywords |
|---|---|---|
2014 | ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2014, PT I | BFS,GPU,irregular computation,graph topology,SIMD underutilization,SIMD efficiency |
Field | DocType | Volume |
Graph theory,Data structure,Graph traversal,CUDA,Computer science,Parallel computing,SIMD,Execution model,Graphics processing unit,Topological graph theory | Conference | 8630 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.36 |
References | Authors | |
19 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yichao Cheng | 1 | 3 | 1.39 |
| Hong An | 2 | 58 | 24.15 |
| Zhitao Chen | 3 | 1 | 0.36 |
| Feng Li | 4 | 90 | 21.99 |
| Zhaohui Wang | 5 | 1 | 0.36 |
| Xia Jiang | 6 | 1 | 0.70 |
| Yi Peng | 7 | 1 | 0.36 |