Impacto da granularidade de tarefas em um programa OpenMP recursivo - Mergesort

Abstract

Este trabalho mostra o processo de paralelização de um clássico algoritmo de ordenação, explicitando as razões para a escolha do mesmo para a realização das análises e os principais fatores que impactam em seu desempenho ao executar de forma paralela juntamente com os maiores obstáculos encontrados para a obtenção de uma boa otimização com redução significativa de tempo de execução. O conteúdo aqui visto também pode ser usado em futuras reflexões para direcionar abordagens de paralelização e otimização com o uso de OpenMP tasks a programas geralmente vistos com uso apenas sequencial ou programas cujas versões paralelas já são conhecidas porém ainda possuem espaço para novas otimizações.

This work shows the parallelization process of a classic sorting algorithm, expliciting the reasons for its choice to the realization of the analyses and the key factors which impact on its performance when executing in parallel along with the biggest obstacles found to the obtention of a good optimization with significative runtime reduction. The content seen here can also be used in future reflections to direct parallelization and optimization approaches with the use of OpenMP tasks to programs usually seen only in sequential versions or programs which parallel versions are already known but still got room for further optimizations.