Paper Info
Title
Distributed-Memory Algorithms for Maximum Cardinality Matching in Bipartite Graphs
Abstract
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.
Year
DOI
Venue
2016
10.1109/IPDPS.2016.103
2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Keywords
Field
DocType
Cardinality matching,parallel algorithm,distributed-memory algorithm
Computer science,Implicit graph,Theoretical computer science,Distributed computing,Adjacency matrix,Folded cube graph,Bipartite graph,Parallel computing,Algorithm,Matching (graph theory),Hopcroft–Karp algorithm,3-dimensional matching,Blossom algorithm
Conference
ISSN
ISBN
Citations 
1530-2075
978-1-5090-2141-3
4
PageRank 
References 
Authors
0.43
23
2
Name
Order
Citations
PageRank
Ariful Azad113815.71
Aydin Buluc2105767.49