Explorando Paralelismo no Problema da Subsequência de Soma Máxima

• Lucas Sciarra Gonçalves UFSCar
• Murilo Miranda UFSCar
• Hélio Guardia UFSCar

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

Resumo

Este artigo explora formas de paralelização sobre um algoritmo para o problema da soma máxima de uma subsequência crescente de tamanho K em um vetor de N elementos. A dificuldade de encontrar a melhor estratégia de paralelismo, e lidar com os overheads que as implementações geram são os pontos principais abordados. Por isso, foram feitas as versões em OpenMP e em CUDA, onde esta última teve um desempenho mais rentável, por conta de funções mais eficientes que a arquitetura proporciona.

Referências

Bentley, J. (1984). Programming pearls: Algorithm design techniques. Communications of the ACM, 27(9), 865-873.

Colichio, H., Pimenta, Y., Borges, P., Menecucci, M., Barros, L., & Guardia, H. (2023). Ordenação paralela com OpenMP e CUDA. In Anais da Escola Regional de Alto Desempenho de São Paulo (ERAD-SP). [link]

Fredman, M. L. (1975). On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1), 29-35. DOI: 10.1016/0012-365X(75)90103-X

Lima, A. C. de. (2015). Soluções para os problemas da soma máxima e do k-ésimo menor elemento de uma sequência usando o modelo BSP/CGM. Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brasil.

International Symposium on Computer Architecture and Simpósio em Sistemas Computacionais de Alto Desempenho High Performance Computing. 14th marathon of parallel programming sbac-pad wscad.