A Malleable Vectorized Auction Algorithm for Modern Multicore Architectures

摘要

The auction algorithm has been widely used to solvev the bipartite graph matching problem and its parallel implementation is employed to find solutions in a reasonable computational time. Moreover, the new multicore architectures, besides its various cores, have a SIMD instruction set that can increase application performance when exactly the same operations are to be performed on multiple data objects. The aim of this paper is to efficiently execute the auction algorithm on these architectures. To achieve that, a vectorized version was implemented and evaluated. These versions were then run in parallel using the OpenMP library. Finally, to optimize the number of threads used during the execution, a malleable strategy is proposed and evaluated. Results show that the vectorized version outperforms the sequential one by a factor of 10, while the malleable vectorized version was able to adapt its execution to exploit the full potential of multicore architectures.