A distributed-memory approximation algorithm for maximum weight perfect bipartite matching

Ariful Azad, Aydin Buluç, Xiaoye S. Li, Xinliang Wang, Johannes LanggutharXiv 2018 · arXiv

Introduction

In high-performance computing (HPC), solving massive systems of linear equations ($Ax = b$) is a foundational task. As datasets scale to billions of entries, traditional sequential bottlenecks become increasingly problematic. One such bottleneck is the process of choosing stable pivots for sparse direct solvers. This paper presents a novel distributed-memory approximation algorithm designed to find heavy-weight perfect matchings in bipartite graphs, effectively shattering the serial limitations of industry-standard tools.

The Bottleneck of Static Pivoting

For numerical stability in sparse matrix factorization, solvers like SuperLU_DIST employ "static pivoting." This involves permuting the matrix so that the diagonal contains the largest possible values, minimizing rounding errors during division. Mathematically, this is modeled as finding a Maximum Weight Perfect Matching (MWPM) in a bipartite graph, where rows and columns are vertices and non-zero entries represent weighted edges.

For decades, the sequential MC64 algorithm has been the gold standard for MWPM. However, in distributed-memory environments, MC64 forces thousands of processors to idle while a single node computes the matching. Because MWPM algorithms involve global data dependencies, they are notoriously difficult to parallelize. The authors address this by relaxing the requirement for an exact maximum weight, focusing instead on a "heavy" matching that is computationally efficient to find in parallel.

The HWPM Algorithm

The proposed Heavy-Weight Perfect Matching (HWPM) algorithm is a primal method that maintains a feasible perfect matching and iteratively improves it. The pipeline transitions from a raw matrix to a high-quality matching through distinct phases of cardinality maximization and weight refinement.

The complete pipeline from input matrix to a heavy-weight perfect matching, illustrating the progression from a bipartite graph to a refined matching via weight-increasing cycles.

Phase 1: Initial Matching with Tie-Breaking

The algorithm begins by finding a Maximum Cardinality Matching (MCM) using a distributed-memory approach. A key innovation here is the introduction of a weight-aware tie-breaking heuristic. When the algorithm identifies multiple potential augmenting paths to increase the matching size, it prioritizes those containing edges with higher weights. This ensures that the initial perfect matching is already "heavy" before any refinement begins.

Illustration of the tie-breaking heuristic. Option 2 (using the heuristic) selects an augmenting path that results in a higher-weight matching compared to the standard approach in Option 1.

Phase 2: Weight-Increasing Alternating Cycles (WIAC)

Once a perfect matching is established, the algorithm enters an iterative refinement phase. It searches for alternating cycles of length four—the shortest possible alternating cycles—that can be "flipped" to increase the total weight. By restricting the search to length-4 cycles, the algorithm maintains linear time complexity and requires only a constant number of communication rounds. The matrix is distributed across a 2D process grid, allowing each process to identify potential cycles locally and resolve collisions with neighbors in parallel.

Experimental Evaluation

The algorithm was implemented as part of the Combinatorial BLAS library and evaluated using over 100 sparse matrices from the SuiteSparse Matrix Collection. These ranged from small-scale benchmarks to massive matrices with over 200 million non-zeros, such as NaluR3 and nlpkkt240.

Scalability and Speed

Testing on the Cray XC40 "Cori" supercomputer demonstrated exceptional scalability. The HWPM algorithm scaled up to 256 nodes (17,408 cores), achieving speedups of up to 2500x over the sequential MC64. Even when compared to parallel implementations on a single node, the distributed approach provided a 114x performance boost.

Solution Quality

Despite being an approximation, the HWPM algorithm consistently found matchings with weights within 99% of the optimal values calculated by MC64. When integrated into the SuperLU_DIST solver, the algorithm reduced the pre-pivoting phase from a multi-second bottleneck to a negligible task taking only milliseconds.

Conclusion

The HWPM algorithm represents a significant step forward for distributed sparse solvers. By prioritizing locality and employing clever heuristics, the authors have created a tool that maintains high numerical stability while scaling to the limits of modern supercomputers. Future work aims to establish theoretical approximation bounds and develop methods for generating distributed dual variables to further enhance solver performance.

Summary updated

Abstract

We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length four in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.
BibTeX
@misc{azad2018distributed,
  author = {Ariful Azad and Aydin Buluç and Xiaoye S. Li and Xinliang Wang and Johannes Langguth},
  title = {{A distributed-memory approximation algorithm for maximum weight perfect bipartite matching}},
  year = {2018},
  eprint = {1801.09809},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.09809},
}
Figure