Distributed-Memory Algorithms for Maximum Cardinality Matching in Bipartite Graphs

We design and implement scalable distributed-memory algorithms for maximum cardinality matching in bipartite graphs. Computing matchings on distributed-memory supercomputers is challenged by the irregular andasynchronous data access patterns in graph searches and the difficulty in processing long pathspassing through multiple processors. We address these challenges by developing an algorithm based on matrix algebra. We employ bulk-synchronous matrix algebraic modules to implement graph searches, and Remote Memory Access (RMA) operations to map asynchronous light-weight graph accesses. On real matrices, our algorithm achieves up to 18x speedup when we go from 24 cores to 2048cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where ouralgorithms show good scaling on up to 12,000 cores.