Ordenação Paralela com OpenMP e CUDA

• Heitor Colichio UFSCar
• Yago Pimenta UFSCar
• Pedro Borges UFSCar
• Matheus Menecucci UFSCar
• Luiz Barros UFSCar
• Hélio Guardia UFSCar

DOI: https://doi.org/10.5753/eradsp.2024.239919

Resumo

Este artigo apresenta um estudo da paralelização do problema da ordenação de valores. Para tanto, parte-se de uma versão do algoritmo QuickSort e explora-se o particionamento dos dados para ordenação de listas parciais, com a consequente integração dos resultados, de maneira semelhante às estratégias do algoritmo MergeSort. Duas implementações são apresentadas, uma para ambiente multiprocessado com memória compartilhada, programado com OpenMP, e outra em GPU, utilizando CUDA. Os resultados obtidos mostram a viabilidade do uso do paralelismo neste problema, com speedups significativos.

Referências

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). Cambridge, MA: MIT Press.

OpenMP (2021). Openmp application programming interface specification version 5.2. [link]. Acesso em 29 de março, 2024.

Nvidia (2023). Cudatoolkitdocumentation. [link]. Acesso em 1 de Abril, 2024.

Hoare, C. A. R. (1962). Quicksort. Communications of the ACM, 4(7), 321-322.

Satish, N., Harris, M., & Garland, M. (2009). Designing efficient sorting algorithms for manycore GPUs. In Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing (pp. 1-10).