Execuc¸a˜ o Eficiente do Algoritmo de Leila˜ o nas Novas Arquiteturas Multicore

Resumo

Resumo. O algoritmo de leila˜o tem sido amplamente utilizado para resolver o problema de emparelhamento de grafos bipartidos e sua implementac¸ a˜o paralela e´ empregada para encontrar soluc¸ o˜es o´timas em um tempo computacional aceita´vel. Ale´m disso, as novas arquiteturas multicore, ale´m de seus va´rios nu´cleos de processamento, possuem um conjunto de instruc¸ o˜es SIMD que pode aumentar o desempenho da aplicac¸ a˜o quando exatamente as mesmas operac¸o˜es necessitam ser realizadas em mu´ltiplos dados. Nesse contexto, o objetivo deste trabalho e´ explorar todo o potencial dessas arquiteturas na execuc¸ a˜o do algoritmo de leila˜o. Para alcanc¸ar este objetivo, verso˜es vetorizadas foram implementadas e avaliadas. Em seguida, essas verso˜es foram executadas em paralelo utilizando a biblioteca OpenMP. Os resultados mostram que a versa˜o vetorizada consegue, em me´dia, um desempenho dez vezes melhor que a versa˜o sequencial, enquanto a versa˜o vetorizada paralela e´ capaz de aproveitar todo o potencial das novas arquiteturas multicore, atingindo um desempenho ate´ 200 vezes melhor do que a versa˜o sequencial.