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.
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.
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