"A Transversalidade da Ciência, Tecnologia e Inovações para o Planeta"
5 a 7 de outubro de 2021
Trabalho 15438
| 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 | Sim |
| Apoio financeiro | FUNARBE |
| Primeiro autor | Matheus Aguilar de Oliveira |
| Orientador | SALLES VIANA GOMES DE MAGALHAES |
| Título | Localização de pontos 3D usando GPUs |
| Resumo | O processo de localização de pontos tridimensionais é uma operação de grande relevância no campo da geometria computacional, dado que serve de base para algoritmos geométricos muito utilizados, como o cálculo da interseção de malhas 3D e a detecção de colisão entre objetos. Entretanto, apesar de tal importância, esse procedimento ainda lida com desafios para ser executado de forma eficiente e robusta, como a ampla quantidade de casos especiais a serem tratados, os erros de arredondamento causados pela aritmética de ponto flutuante e o crescente tamanho dos dados utilizados pelas aplicações atuais. Devido a tais adversidades, diversos algoritmos optam por sacrificar a exatidão de modo a manter uma boa performance ou vice-versa. Tendo esse problema como base, esse projeto de pesquisa teve como trabalho a adaptação e aprimoramento de um algoritmo de localização de pontos 3D, desenvolvido pelo orientador do projeto (que é capaz de realizar tal computação de forma exata e eficiente) por meio de artifícios de programação paralela, com o objetivo de avaliar o potencial dessas estratégias, bem como adicionar e testar novas (como o uso de aritmética intervalar e de GPUs). O grupo de pesquisa focou-se no processo de localização de pontos em tetra meshes, que são malhas tridimensionais formadas por tetraedros. O procedimento em questão tem o seguinte objetivo: dado um conjunto de pontos no espaço e uma tetra mesh, determinar em qual tetraedro cada ponto está ou se esse está fora do objeto. Com o intuito de acelerar o desempenho do algoritmo e manter a exatidão, foram utilizadas as seguintes estratégias: usar uma grade cartesiana uniforme como índice geométrico, evitando testes desnecessários entre pontos e poliedros; usar o método Simulation of Simplicity para tratar casos especiais, mantendo assim a consistência do resultado; usar artifícios de programação paralela e GPUs para realizar a localização de cada ponto de forma concorrente, um processo que não gera inconsistências, uma vez que os testes dos pontos são independentes. O algoritmo foi aplicado sobre um conjunto de testes contendo cerca de 2 milhões de pontos e uma tetra mesh composta de cerca 1,6 milhões de tetraedros e os resultados foram comparados com os de uma versão sequencial sobre o mesmo conjunto. Nessa etapa, foi obtido um ganho de cerca de 20 vezes em relação à versão sequencial, usando números de ponto flutuante, embora tenha sido necessário realizar um balanceamento de threads na GPU para obter esse resultado. Espera-se um ganho ainda maior ao se fazer uso de aritmética intervalar, visto que as operações sobre esse tipo de dados são mais caras do que as de ponto flutuante, logo se beneficiariam mais ainda do paralelismo massivo da GPU. Portanto, com base nesses resultados, é possível concluir que as estratégias utilizadas são capazes realizar os cálculos de forma eficiente e robusta, o que beneficia não só o processo de localização, mas também outros algoritmos geométricos. |
| Palavras-chave | Computação, Geometria, GPU |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|