Paralelização e Otimização em GPU do Problema do Par de Pontos Mais Próximos
Resumo
O Problema do Par de Pontos Mais Próximos (Closest Pair Problem -- CPP) consiste em encontrar o par de pontos mais próximos em um conjunto de pontos, e pode ser aplicado para resolver problemas de diferentes áreas. As soluções para o CPP encontradas na literatura são baseadas na abordagem de divisão e conquista, que permite a construção de um algoritmo ótimo para o CPP. Entretanto, essa abordagem não favorece a exploração de paralelismo na solução do CPP. As contribuições desse trabalho são: (a) a proposta de uma nova abordagem, baseada no particionamento espacial, para solução do CPP; (b) o desenvolvimento de uma solução sequencial para o CPP, baseada na nova abordagem, que obtém desempenho melhor que soluções baseadas na divisão e conquista; (c) o desenvolvimento de uma solução paralela para execução em GPU, também baseada na nova abordagem, que alcança de até 79,56 e 142,30 (para densidades de pontos baixa e alta, respectivamente), em relação à melhor solução sequencial; e (d) a proposta de otimizações para melhorar o desempenho das soluções sequencial e paralela desenvolvidas.
Referências
Bell, N. and Hoberock, J. (2012). Thrust: A Productivity-Oriented Library for CUDA,chapter 26 – GPU Computing Gems. Elsevier.
Blelloch, G. and Maggs, B. (2004).Parallel Algorithms, chapter 10 – Computer Science Handbook. Chapman & Hall/CRC, 2 edition.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2014).Introduction to Algorithms. MIT Press.
Nakano, J. and Carmo, L. (2017). Otimizações e paralelização do problema do par de pontos mais próximos. Technical report, Universidade Federal de Mato Grosso do Sul.
Rajasekaran, S. and Pathak, S. (2014). Efficient algorithms for the closest pair problem and applications. https://arxiv.org/abs/1407.5609. Acessado em fevereiro 2020.
Sedgewick, R. (1990). Algorithms in C. Addison-Wesley.
Sgier, S. (2016). Prototype implementation and evaluation on algorithmic motifs in scientific computing. Master’s thesis, Swiss Federal Institute of Technology Zurich.
Shamos, M. (1975). Geometric complexity. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, pages 224–233.
Wang, Y., Horng, S., and Wu, C. (2005). Efficient algorithms for the all nearest neighbor and closest pair problems on the linear array with a reconfigurable pipelined bus system. IEEE Transactions on Parallel and Distributed Systems, 16(3):193–206.
Yang, C. (1999).Computational geometry on the broadcast communication model. Journal of Information Science and Engineering, 16(3):383–395.
