Exploring Parallelism in the Maximum Subarray Sum Problem

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

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

Abstract

This paper explores parallelization techniques applied to an algorithm addressing the problem of computing the maximum sum of an increasing subsequence of length K within a vector of N elements. The main challenges discussed revolve around determining the optimal parallelization strategy and managing the overheads introduced by the implementations. Consequently, versions utilizing OpenMP and CUDA were developed, with the latter exhibiting more efficient performance, attributed to the enhanced functionality provided by its architecture.

References

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.