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.