WolfPath: Accelerating iterative traversing-based graph processing algorithms on GPU: Accelerating Iterative Traversing-Based Graph Processing Algorithms on GPU

Huanzhou Zhu, Ligang He, Songling Fu, Rui Li, Xie Han, Zhangjie Fu, Yongjian Hu, Chang Tsun Li

Research output: Contribution to journalArticle

38 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1-24
Number of pages24
JournalInternational Journal of Parallel Programming
VolumeSpecial
DOIs
Publication statusPublished - 2018

Fingerprint Dive into the research topics of 'WolfPath: Accelerating iterative traversing-based graph processing algorithms on GPU: Accelerating Iterative Traversing-Based Graph Processing Algorithms on GPU'. Together they form a unique fingerprint.

  • Cite this