Multithreaded Algorithms for Maximum Matching in Bipartite Graphs

We design, implement, and evaluate algorithms for computing a matching of maximum cardinality in a bipartite graph on multi-core and massively multithreaded computers. As computers with larger number of slower cores dominate the com- modity processor market, the design of multithreaded algorithms to

solve large matching problems becomes a necessity. Recent work on serial algorithms based on searching for augmenting paths for this problem have shown that their performance is sensitive to the order in which the vertices are processed for matching. In a multithreaded environment, imposing a serial order in which vertices are considered for matching would lead to loss of concurrency and performance. But this raises the question: Would parallel matching algorithms on multithreaded machines improve performance over a serial algorithm? We answer this question in the affirmative. We report efficient multithreaded implementations of two key algorithms (Hopcroft- Karp based on breadth-first-search, and Pothen-Fan based on depth-first-search) and their variants, combined with the Karp- Sipser initialization algorithm. We report extensive results and insights using three shared-memory platforms (a 48-core AMD Opteron, a 32-core Intel Nehalem, and a 128-processor Cray XMT) on a representative set of real-world and synthetic graphs. To the best of our knowledge, this is the first extensive study of augmentation-based parallel algorithms for bipartite cardinality matching. I. INTRODUCTION We design, implement, and evaluate five parallel algorithms for computing a matching of maximum cardinality in a bipar- tite graph on multicore and massively multithreaded comput- ers. As multicore machines dominate the commodity proces- sor market, and the size of problems continue to increase, there is need for parallel algorithms for solving important combinatorial problems such as matching in graphs. However, achieving good performance and speedup on combinatorial problems is a challenge due to the large number of data accesses relative to computation, the poor locality of the data accesses, irregular nature of the concurrency available, and fine-grained synchronization required. An earlier study on parallel (weighted) matching algorithms [1] reported poor speedups, but said ideal platforms for such algorithms would have “relatively few numbers of powerful processors, support for block transfers, lots of memory, and a high processor- memory bandwidth to this memory”. We show that good speedups are achievable on emerging multicore machines via shared memory multithreaded algorithms that are designed here. Matching has several applications in computer science, scientific computing, bioinformatics, information science, and other areas. Our study of bipartite maximum matching is motivated by applications to solving sparse systems of linear equations, and for computing a decomposition known as the block-triangular form (BTF) of a matrix [2]. The rest of this paper is organized as follows. In Section II we describe two classes of parallel algorithms for...

Website: www.cs.purdue.edu | Filesize: -
No of Page(s): 12
Download Multithreaded Algorithms for Maximum Matching in Bipartite Graphs.pdf