Name
Title | ||
|---|---|---|
WolfPath : accelerating Iterative Traversing-Based Graph Processing Algorithms on GPU |
Abstract | ||
|---|---|---|
There is the significant interest nowadays in developing the frameworks of parallelizing the processing for the large graphs such as social networks, Web graphs, etc. Most parallel graph processing frameworks employ iterative processing model. However, by benchmarking the state-of-art GPU-based graph processing frameworks, we observed that the performance of iterative traversing-based graph algorithms (such as Bread First Search, Single Source Shortest Path and so on) on GPU is limited by the frequent data exchange between host and GPU. In order to tackle the problem, we develop a GPU-based graph framework called WolfPath to accelerate the processing of iterative traversing-based graph processing algorithms. In WolfPath, the iterative process is guided by the graph diameter to eliminate the frequent data exchange between host and GPU. To accomplish this goal, WolfPath proposes a data structure called Layered Edge list to represent the graph, from which the graph diameter is known before the start of graph processing. In order to enhance the applicability of our WolfPath framework, a graph preprocessing algorithm is also developed in this work to convert any graph into the format of the Layered Edge list. We conducted extensive experiments to verify the effectiveness of WolfPath. The experimental results show that WolfPath achieves significant speedup over the state-of-art GPU-based in-memory and out-of-memory graph processing frameworks. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10766-017-0533-y | International Journal of Parallel Programming |
Keywords | Field | DocType |
Graph processing, GPGPU, Parallel computing | Data structure,Data exchange,Iterative and incremental development,Shortest path problem,Computer science,Parallel computing,Breadth-first search,Algorithm,Distance,Theoretical computer science,General-purpose computing on graphics processing units,Speedup | Journal |
Volume | Issue | ISSN |
47 | 4 | 1573-7640 |
Citations | PageRank | References |
0 | 0.34 | 37 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huanzhou Zhu | 1 | 11 | 2.19 |
| Ligang He | 2 | 542 | 56.73 |
| Songling Fu | 3 | 0 | 0.34 |
| Rui Li | 4 | 209 | 59.97 |
| Xie Han | 5 | 0 | 0.34 |
| Zhangjie Fu | 6 | 405 | 19.78 |
| Yongjian Hu | 7 | 2 | 3.07 |
| Chang-Tsun Li | 8 | 937 | 72.14 |