The Library
WolfPath : accelerating iterative traversing-based graph processing algorithms on GPU
Tools
Tools
Tools
Zhu, Huanzhou, He, Ligang, Fu, Songling, Li, Rui, Han, Xie, Fu, Zhangjie, Hu, Yongjian and Li, Chang-Tsun (2017) WolfPath : accelerating iterative traversing-based graph processing algorithms on GPU. International Journal of Parallel Programming . doi:10.1007/s10766-017-0533-y
|
PDF
WRAP-WolfPath-accelerating-iterative-traversing-based-graph-processing-algorithms-GPU-He-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1099Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s10766-017-0533-y
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.
| Item Type: | Journal Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory -- Data processing, Parallel processing (Electronic computers) | ||||||||||||||||||
| Journal or Publication Title: | International Journal of Parallel Programming | ||||||||||||||||||
| Publisher: | Springer | ||||||||||||||||||
| ISSN: | 0885-7458 | ||||||||||||||||||
| Official Date: | 14 November 2017 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Date of first compliant deposit: | 4 January 2018 | ||||||||||||||||||
| DOI: | 10.1007/s10766-017-0533-y | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Open Access | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
