Paralelização e Otimização em GPU do Problema do Par de Pontos Mais Próximos - Baroni, Eduardo Ferreira; Braga, Gabriel Medina; Moreano, Nahri (Anais do Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance); 2020: Anais do XIX Workshop em Desempenho de Sistemas Computacionais e de ComunicaçãoDO - 10.5753/wperformance.2020.11115, 2020)
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.