Engineering A Workload-balanced Push-Relabel Algorithm for Massive Graphs on GPUs

Chou-Ying Hsieh, Po-Chieh Lin, Sy-Yen Kuo

Abstract: The maximum flow problem is a cornerstone of network optimization with applications spanning VLSI design to computer vision. However, existing GPU-based push-relabel implementations struggle with massive graphs due to $O(V^2)$ memory requirements and significant workload imbalances. This paper presents WBPR, a workload-balanced push-relabel algorithm that utilizes enhanced sparse representations (RCSR and BCSR) to reduce memory complexity to $O(V+E)$. By implementing a two-level vertex-centric parallel strategy using "tiles" (warps), WBPR achieves up to a 7.31x speedup over state-of-the-art solvers while maintaining high GPU utilization across diverse graph topologies.

Introduction

Finding the maximum flow in a network—determining the maximum amount of data or fluid that can move from a source to a sink—is a fundamental challenge. While the push-relabel algorithm is naturally suited for parallel processing, its application to massive graphs (billions of edges) on GPUs faces two primary hurdles. First, many solvers rely on adjacency matrices, leading to memory bloat that exceeds the capacity of modern hardware for even moderately sized graphs. Second, real-world networks often exhibit power-law distributions where a few "hub" nodes have disproportionately high degrees. Traditional "one thread per vertex" GPU models suffer from extreme workload imbalance, where most threads remain idle while a few process high-degree nodes.

Methodology

WBPR addresses these challenges through two main innovations: memory-efficient data structures and a hierarchical parallel execution model.

1. Enhanced Sparse Representations (RCSR & BCSR)

To overcome the $O(V^2)$ memory barrier, WBPR employs variants of the Compressed Sparse Row (CSR) format. Standard CSR is efficient for forward traversal but inefficient for the backward edge lookups required by push-relabel logic. The authors propose Reversed CSR (RCSR) and Bidirectional CSR (BCSR). RCSR adds an auxiliary index for instantaneous backward flow access, while BCSR co-locates incoming and outgoing neighbors to maximize memory coalescing.

Figure 4: Sparse graph representations (RCSR/BCSR) showing offset, column, and flow arrays to manage graph data with O(V+E) complexity.

2. Two-level Vertex-Centric Parallelism

The core of WBPR's performance lies in its workload balancing strategy. Instead of assigning a single thread to each vertex, WBPR uses a more sophisticated two-level approach:

  • Level 1: All threads scan the graph to identify "active" vertices (those with excess flow) and place them in an Active Vertex Queue (AVQ).
  • Level 2: For each active vertex in the AVQ, the algorithm assigns a "tile"—a group of threads (typically a warp of 32 threads). These threads collaborate using parallel reduction to find the optimal neighbor for flow pushing.
Figure 3: Comparison between (a) traditional thread-centric push-relabel and (b) the proposed vertex-centric approach with AVQ and tile-based processing.

This shift from thread-centric to vertex-centric processing effectively "flattens" the workload, ensuring that high-degree nodes do not become execution bottlenecks.

Experimental Results

The researchers evaluated WBPR across 13 diverse graphs from the SNAP, DIMACS, and KONECT repositories, including social networks, web graphs, and bipartite matching benchmarks.

  • Speedup: WBPR achieved an average speedup of 2.49x to 7.31x for maximum flow tasks and 1.89x to 2.29x for bipartite matching compared to existing thread-centric GPU implementations.
  • Memory Efficiency: By reducing memory complexity from quadratic ($O(V^2)$) to linear ($O(V+E)$), WBPR successfully processed massive graphs that were previously incompatible with single-GPU memory limits.
  • Hardware Utilization: The tile-based strategy significantly reduced the variance in execution time across GPU warps, indicating superior hardware utilization and reduced tail latency.

Conclusion and Future Work

WBPR demonstrates that combining linear-space sparse representations with a vertex-centric parallel model can dramatically improve the efficiency of maximum flow algorithms on GPUs. While the overhead of AVQ management makes it less suited for small, naturally balanced graphs (like road networks), its performance on massive, irregular networks represents a significant advancement. Future work will focus on porting these techniques to non-CUDA architectures and exploring their application to other complex graph algorithms.

Summary updated

BibTeX
@inproceedings{hsieh2025engineering,
  author = {Chou-Ying Hsieh and Po-Chieh Lin and Sy-Yen Kuo},
  title = {{Engineering A Workload-balanced Push-Relabel Algorithm for Massive Graphs on GPUs}},
  booktitle = {HPEC},
  year = {2025},
  doi = {10.1109/hpec67600.2025.11196651},
}
Figure