Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
14 November 2017Available
28 September 2017Accepted
DOI: 10.1007/s10766-017-0533-y
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
690907H2020 Marie Skłodowska-Curie Actionshttp://dx.doi.org/10.13039/100010665
201510010275Guangzhou City Science FoundationUNSPECIFIED
61370226National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809
61672156National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809
UNSPECIFIEDNanjing University of Information Science and Technologyhttp://dx.doi.org/10.13039/501100008045

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us