A Push-Relabel-Based Maximum Cardinality Bipartite Matching Algorithm on GPUs

Abstract : We design, develop, and evaluate an atomic- and lock-free GPU implementation of the push-relabel algorithm in the context of finding maximum cardinality matchings in bipartite graphs. The problem has applications on computer science, scientific computing, bioinformatics, and other areas. Although the GPU parallelization of the push-relabel technique has been investigated in the context of flow algorithms, to the best of our knowledge, ours is the first study which focuses on the maximum cardinality matching. We compare the proposed algorithms with serial, multicore, and manycore bipartite graph matching implementations from the literature on a large set of real-life problems. Our experiments show that the proposed push- relabel-based GPU algorithm is faster than the existing parallel and sequential implementations.
Type de document :
Communication dans un congrès
42nd International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE Computer Society, pp.21 - 29, 2013, 〈10.1109/ICPP.2013.11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00923464
Contributeur : Equipe Roma <>
Soumis le : jeudi 2 janvier 2014 - 20:34:43
Dernière modification le : jeudi 11 janvier 2018 - 06:23:58
Document(s) archivé(s) le : samedi 8 avril 2017 - 10:34:50

Fichier

matchingGPU.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mehmet Deveci, Kamer Kaya, Bora Uçar, Umit Catalyurek. A Push-Relabel-Based Maximum Cardinality Bipartite Matching Algorithm on GPUs. 42nd International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE Computer Society, pp.21 - 29, 2013, 〈10.1109/ICPP.2013.11〉. 〈hal-00923464〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

303