Implementação e Avaliação do Algoritmo de Leilão nas Arquiteturas Xeon Phi

• Alexandre Sena IME, UERJ
• Aline de Nascimento Instituto de Computação, UFF
• Leandro Marzulo Universidade do Estado do Rio de Janeiro - UERJ

DOI: https://doi.org/10.5753/wscad.2019.8663

Resumo

O algoritmo de leilão tem sido amplamente utilizado para resolver problemas de várias áreas. Com seus vários núcleos de processamento e instruções vetorizadas de 512 bits, arquiteturas Xeon Phi tem potencial para aumentar consideravelmente o desempenho desse algoritmo. O objetivo deste trabalho é executar eficientemente o algoritmo de leilão nessas arquiteturas. As principais contribuições são: implementação de uma versão vetorizada; Análise de desempenho da versões vetorizada e paralela; comparação do desempenho entre Xeon e Xeon Phi. Resultados mostram que a versão vetorizada paralela é capaz de aproveitar todo o potencial das arquiteturas Xeon Phi, atingindo um desempenho até 750 vezes melhor do que a versão sequencial.

Referências

Bertsekas, D. P. (1979). A distributed algorithm for the assignment problem. Technical report, Lab. for Information and Decision Systems, M.I.T., Cambridge, MA.

Bertsekas, D. P. and Castañon, D. A. (1991). Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput., 17(6-7):707–732.

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. (2014). Fast parallel algorithms for graph similarity and matching. Journal of Par. and Dist. Comp., 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.

Sena, A. C., Nascimento, A., Vasconcelos, C., and Marzulo, L. A. J. (2017). Execução eficiente do algoritmo de leilão nas novas arquiteturas multicore. Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD), 18(1/2017).

Shokoufandeh, A. and Dickinson, S. (1999). Applications of bipartite matching to problems in object recognition. In In Proceedings, ICCV Workshop on Graph Algorithms and Computer Vision, page http://www.cs.cornel.

van der Pas, R., S. E. S. E. T. C. (2017). Using OpenMP – The Next Step:Affinity, Accelerators, Tasking, and SIMD. The MIT Press.

Vasconcelos, C. N. and Rosenhahn, B. (2009). Bipartite Graph Matching Computation on GPU. Springer Berlin Heidelberg, Berlin, Heidelberg.

Wende, F., Noack, M., Steinke, T., Klemm, M., Newburn, C. J., and Zitzlsberger, G. (2016). Portable simd performance with openmp* 4.x compiler directives. In Proc. of the Inter. European Conference on Parallel Processing, pages 264–277.