matchmaker2: Framework for Maximum Cardinality Matching on Bipartite Graphs

General information

We design, implement, and evaluate a GPU-based maximum cardinality matching algorithm on bipartite graphs. Such matchings on bipartite graphs have a variety of applications in computer science, scientific computing, bioinformatics, and other areas. To the best of our knowledge, ours is the first study which focuses on maximum cardinality matchings and provides a GPU implementation. We compare the resulting algorithms with serial and multicore implementations from the literature on a large set of real-life matrices where in majority of the cases our GPU-accelerated algorithm is demonstrated to be faster than both the sequential and multicore implementations.

matchmaker2 extends matchmaker with the additional GPU implementations.

Related Publications

• M. Deveci, K. Kaya, B. Ucar, U. V. Catalyurek "GPU accelerated maximum cardinality matching algorithms for bipartite graphs" Proc. of 19th Int'l. Euro-Par Conf. on Parallel Processing, 2013
• M. Deveci, K. Kaya, B. Ucar, U. V. Catalyurek "A Push-Relabel-based Maximum Cardinality Bipartite Matching Algorithm on GPUs" Proc. of 42nd Int'l. Conf. on Parallel Processing, 2013

Download

Latest release: matchmaker2-02-14-2013

Supplementary Materials

Supplementary materials can be found here.