WolfPath: 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

Introduction

Iterative graph algorithms, such as Breadth-First Search (BFS) and Single Source Shortest Path (SSSP), are fundamental to modern data analysis. While GPUs offer massive parallelism, they face a significant "synchronization bottleneck" when executing these algorithms. WolfPath is a novel framework designed to eliminate this bottleneck, achieving performance gains of up to 4000x over traditional systems.

The Problem: The Synchronization Bottleneck

Standard GPU implementations rely on a host-driven loop. After each iteration, the GPU must send a completion flag back to the CPU to determine if another step is required. This data exchange is surprisingly costly because current GPU architectures (like CUDA) do not support global synchronization across all thread blocks during kernel execution.

Table 1: Memory copy vs. computation time across different datasets.

As shown in the table above, the time taken for memory copying (synchronization) can be orders of magnitude greater than the actual computation time. For instance, in the Web-Google dataset, memory copy takes 0.6ms while computation takes only 0.004ms—a 150x difference. In some cases, this overhead is 1500 times longer than the actual work.

Methodology: Structural Transformation

WolfPath eliminates this bottleneck by removing the need for CPU-side checks. The core of this approach is a structural transformation of the graph during a one-time preprocessing step.

Figure 1: Converting a general graph (a) into a layered tree representation (b).

Layered Tree Representation

WolfPath converts the input graph into a tree-like structure where vertices are grouped into layers based on their distance from the source. This allows for:

  • Coalesced Memory Access: Storing layers as contiguous arrays ensures the GPU reads and writes data with maximum efficiency.
  • Diameter-Guided Execution: By pre-calculating the graph's diameter (the longest shortest path), WolfPath can run a fixed number of iterations on the GPU, completely bypassing the host-GPU synchronization loop.

Key Innovations

Beyond the layered structure, WolfPath introduces several optimizations to maximize hardware utilization:

  • Combined Edge List: To prevent GPU under-utilization in sparse layers, multiple consecutive layers are grouped into a single list to keep all GPU cores active.
  • Out-of-GPU Memory Engine: For massive datasets that exceed VRAM, the framework partitions the layered structure into sub-graphs, processing them in order while retaining updated vertex values in global memory to minimize data movement.

Performance and Results

The results are transformative. WolfPath demonstrates dominant performance across diverse datasets, ranging from 3 million to 640 million edges:

  • In-Memory Systems: It outperformed CuSha by over 100x and Virtual Warp Centric (VWC) by over 400x on average.
  • Out-of-Memory Systems: When handling graphs larger than GPU memory, WolfPath achieved an average speedup of 3000x over GraphChi and 4000x over X-Stream.

In a specific test with the RoadNet-CA graph, the "diameter-guided" approach reduced execution time from 196ms to just 2ms.

Conclusion

WolfPath demonstrates that "over-computation"—running the GPU for a fixed duration based on graph diameter—is significantly more efficient than the traditional approach of stopping to check for convergence. While the preprocessing step is more intensive and the memory footprint is roughly 1.37x larger than standard formats, the massive gains in execution speed make it a superior choice for traversing-based graph algorithms.

Summary updated

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.
BibTeX
@article{zhu2019wolfpath,
  author = {Huanzhou Zhu and Ligang He and Songling Fu and Rui Li and Xie Han and Zhangjie Fu and Yongjian Hu and Chang-Tsun Li},
  title = {{WolfPath: Accelerating Iterative Traversing-Based Graph Processing Algorithms on GPU}},
  journal = {Int. J. Parallel Program.},
  year = {2019},
  doi = {10.1007/s10766-017-0533-y},
}
Figure