Execução Eficiente do Algoritmo de Leilão nas Novas Arquiteturas Multicore
Resumo
O algoritmo de leilão tem sido amplamente utilizado para resolver o problema de emparelhamento de grafos bipartidos e sua implementação paralela é empregada para encontrar soluções ótimas em um tempo computacional aceitável. Além disso, as novas arquiteturas multicore, além de seus vários núcleos de processamento, possuem um conjunto de instruções SIMD que pode aumentar o desempenho da aplicação quando exatamente as mesmas operações necessitam ser realizadas em múltiplos dados. Nesse contexto, o objetivo deste trabalho é explorar todo o potencial dessas arquiteturas na execução do algoritmo de leilão. Para alcançar este objetivo, versões vetorizadas foram implementadas e avaliadas. Em seguida, essas versões foram executadas em paralelo utilizando a biblioteca OpenMP. Os resultados mostram que a versão vetorizada consegue, em média, um desempenho dez vezes melhor que a versão sequencial, enquanto a versão vetorizada paralela é capaz de aproveitar todo o potencial das novas arquiteturas multicore, atingindo um desempenho até 200 vezes melhor do que a versão sequencial.
Referências
Bertsekas, D. P. (1992). Auction algorithms for network ow problems: A tutorial intro- duction. Computational Optimization and Applications, 1(1):7–66.
Bertsekas, D. P. and Casta˜non, D. A. (1991). Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput., 17(6-7):707–732.
Bus, L. and Tvrdík, P. (2009). Towards auction algorithms for large dense assignment problems. Computational Optimization and Applications, 43(3):411–436.
Carpaneto, G., Martello, S., and Toth, P. (1988). Algorithms and codes for the assignment problem. Annals of Operations Research, 13(1):191–223.
Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., and McDonald, J. (2000). Parallel Programming in OpenMP. Morgan Kaufmann, 1st edition.
Intel (2007). Intel c++ intrinsic reference. Technical report, Intel.
Intel (2017). Intel intrinsics guide. Technical report, Intel.
Kollias, G., Sathe, M., Mohammadi, S., and Grama, A. (2013). A fast approach to global alignment of protein-protein interaction networks. BMC Research Notes, 6(1):1–11.
Kollias, G., Sathe, M., Schenk, O., and Grama, A. (2012). Fast parallel algorithms for graph similarity and matching. Technical report RR12-010, Department of Computer Science, Purdue University.
Kollias, G., Sathe, M., Schenk, O., and Grama, A. (2014). Fast parallel algorithms for graph similarity and matching. Journal of Parallel and Distributed Computing, 74(5):2400 – 2410.
Mark-Sabahi (2012). A guide to auto-vectorization with intel c++ compilers. Technical report, Intel.
Nascimento, A. P., Vasconcelos, C. N., Jamel, F. S., and Sena, A. C. (2016). A hybrid parallel algorithm for the auction algorithm in multicore systems. In Inter. Symp. on Computer Architecture and High Perf. Comp. Workshops (SBAC-PADW), pages 73–78.
Sathe, M., Schenk, O., and Burkhart, H. (2012). An auction-based weighted matching implementation on massively parallel architectures. Parallel Computing, 38(12):595 – 614.
Shokoufandeh, A. and Dickinson, S. (1999). Applications of bipartite matching to pro- blems in object recognition. In In Proceedings, ICCV Workshop on Graph Algorithms and Computer Vision, page http://www.cs.cornel.
Vasconcelos, C. N. and Rosenhahn, B. (2009). Bipartite Graph Matching Computation on GPU. Springer Berlin Heidelberg, Berlin, Heidelberg.
