Name
Abstract | ||
|---|---|---|
Graph coloring has been broadly used to discover concurrency in parallel computing. To speed up graph coloring for large-scale datasets, parallel algorithms have been proposed to leverage modern GPUs. Existing GPU implementations either have limited performance or yield unsatisfactory coloring quality (too many colors assigned). We present a work-efficient parallel graph coloring implementation on GPUs with good coloring quality. Our approach uses the speculative greedy scheme, which inherently yields better quality than the method of finding maximal independent set. To achieve high performance on GPUs, we refine the algorithm to leverage efficient operators and alleviate conflicts. We also incorporate common optimization techniques to further improve performance. Our method is evaluated with both synthetic and real-world sparse graphs on the NVIDIA GPU. Experimental results show that our proposed implementation achieves averaged 4.1 x (up to 8.9 x) speedup over the serial implementation. It also outperforms the existing GPU implementation from the NVIDIACUSPARSE library (2.2x average speedup), while yielding much better coloring quality than CUSPARSE. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/cpe.4064 | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE |
Keywords | DocType | Volume |
GPU,graph coloring,speculative greedy | Journal | 29 |
Issue | ISSN | Citations |
10 | 1532-0626 | 0 |
PageRank | References | Authors |
0.34 | 5 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xuhao Chen | 1 | 40 | 7.43 |
| Pingfan Li | 2 | 3 | 1.11 |
| Jianbin Fang | 3 | 265 | 25.31 |
| Tao Tang | 4 | 42 | 7.44 |
| Zhi-Ying Wang | 5 | 870 | 127.04 |
| Canqun Yang | 6 | 188 | 29.39 |