Parallel Maximum Cardinality Matching for General Graphs on GPUs

Area of Science:

• Computer Science
• Graph Theory
• Parallel Computing

Background:

• Maximum Cardinality Matching in General Graphs (MCMGG) is a fundamental graph problem.
• The Micali-Vazirani algorithm offers optimal asymptotic complexity for sparse graphs.
• Parallelizing MCMGG on GPUs is challenging due to recursive augmenting path procedures and graph partitioning requirements.

Purpose of the Study:

• To propose and implement a GPU-accelerated version of the Micali-Vazirani algorithm for MCMGG.
• To address the challenges of parallelizing graph matching algorithms on GPUs.

Main Methods:

• Implemented Micali-Vazirani algorithm on GPUs.
• Utilized thread-parallel breadth-first search for bridge edge identification.
• Employed block-parallel path augmentation and blossom contraction.
• Used stack-based iterative methods for augmenting path and Union-find with shared memory allocation.

Main Results:

• Achieved up to 15-fold speed-up on very sparse regular graphs compared to serial implementation.
• Observed up to 5-fold slowdown on denser regular graphs.
• Experienced a 50-fold slowdown on power-law distributed Kronecker graphs.

Conclusions:

• The proposed GPU implementation demonstrates potential for accelerating MCMGG on specific graph structures.
• Performance is highly dependent on graph sparsity and distribution.
• The open-sourced implementation facilitates further research in GPU-based combinatorial graph algorithms.