Paper Info
Title
A Hybrid Parallel Algorithm for the Auction Algorithm in Multicore Systems
Abstract
The bipartite graph matching problem is based on finding a point that maximizes the chances of similarity with another one, and it is explored in several areas such as Bioinformatics and Computer Vision. To solve that matching problem the auction algorithm has been widely used and its parallel implementation is employed to find matching solutions in a reasonable computational time. For example, image analysis may require a large amount of processing, as dense images can have thousands of points to be considered. Furthermore, to exploit the benefits of multicore architectures, a hybrid implementation can be used to deal with communication in both distributed and shared memory. The main goal of this paper is to implement and evaluate the performance of an hybrid parallel auction algorithm for multicore clusters. The experiments carried out analyzes the problem size, the number of iterations to solve the matching and the impact of these parameters in the communication costs and how it affects the execution times.
Year
DOI
Venue
2016
10.1109/SBAC-PADW.2016.21
2016 International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW)
Keywords
Field
DocType
auction algorithm,clusters multicore,bipartite graph matching
Algorithm design,Shared memory,Parallel algorithm,Computer science,Parallel computing,Bipartite graph,Assignment problem,3-dimensional matching,Multi-core processor,Auction algorithm
Conference
ISBN
Citations 
PageRank 
978-1-5090-4845-8
0
0.34
References 
Authors
6
4
Name
Order
Citations
PageRank
Aline P. Nascimento171.83
Cristina Nader Vasconcelos27612.15
F. S. Jamel300.34
Alexandre Sena4409.45