“Inteligência Artificial: A Nova Fronteira da Ciência Brasileira”
19 a 24 de outubro de 2020
Trabalho 13453
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Departamento de Informática |
| Bolsa | FUNARBIC/FUNARBE |
| Conclusão de bolsa | Não |
| Apoio financeiro | FUNARBE |
| Primeiro autor | Matheus Aguilar de Oliveira |
| Orientador | SALLES VIANA GOMES DE MAGALHAES |
| Título | Algoritmo de interseção 3D usando GPUs |
| Resumo | O cálculo de interseção entre objetos tridimensionais é uma operação bastante importante no campo de geometria computacional, visto que é amplamente utilizado por diversas ferramentas como sistemas de informação geográfica (SIGs), sistemas de desenho assistido por computador (CADs) e sistemas de mineração. Contudo, apesar de sua importância, essa operação ainda enfrenta desafios para ser executada de forma eficiente e robusta, em decorrência da grande quantidade de casos especiais do algoritmo, dos erros de arredondamento causados pela aritmética de ponto flutuante e do tamanho extenso dos dados utilizados por aplicações atuais, o que leva muitos algoritmos a sacrificarem performance para manter a exatidão dos cálculos ou vice-versa. Com base nisso, nesse projeto de pesquisa foi feito o trabalho de adaptar e aprimorar um algoritmo de interseção 3D, desenvolvido pelo orientador do projeto e capaz de realizar uma computação exata e eficiente por meio do uso de GPUs e programação paralela, com o intuito de avaliar o potencial dessas estratégias, bem como utilizá-las para melhorar outros algoritmos geométricos já existentes. O grupo de pesquisa focou-se em uma etapa importante do processo de interseção de malhas 3D: a detecção de interseções entre segmentos e triângulos, de forma exata. De modo a manter a performance da computação, foram utilizadas diversas estratégias, como: utilizar uma grade cartesiana como índice geométrico, evitando testes de interseção entre pares desnecessários; utilizar aritmética intervalar na GPU ao invés de números racionais de precisão arbitrária, pois seu custo computacional é menor; utilizar a GPU para realizar os testes de interseção de vários pares de objetos em paralelo, o que não gera inconsistências, visto que tais testes são independentes uns dos outros; utilizar processamento paralelo na CPU para recalcular os testes que geraram resultados ambíguos na GPU (por causa da aritmética intervalar) utilizando números racionais. O algoritmo foi aplicado sobre o conjunto de dados geológicos de uma mina, representados por objetos tridimensionais e os resultados desses testes foram comparados com aplicação de um algoritmo de interseção sequencial sobre o mesmo conjunto. Nessa etapa, foi obtido um ganho de performance preliminar de cerca de 14 vezes em relação à versão sequencial, apesar de ter sido necessário realizar um balanceamento de threads na GPU para obter tal resultado. Outro ponto importante a se destacar, é o fato de que apenas 7 testes, de um total de cerca de 15 milhões, precisaram ser recalculados na CPU, o que indica que a aritmética intervalar consegue ser precisa sem afetar o desempenho. Portanto, com base nos resultados do algoritmo, é possível concluir que GPUs são capazes de calcular predicados geométricos de forma exata e eficiente, o que permite que diversos algoritmos possam ser melhorados. |
| Palavras-chave | Computação, Geometria, GPU |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|