Contact detection algorithms are needed in different areas of science and technology. From digital games and computer graphics to high-performance simulations and robotics. These algorithms require great computational effort and are prone to become the bottlenecks of its applications, even more when this computation must be done in real-time or large-scale systems. With the popularization of GPU cards use for both science and business, it is only natural that parallel implementations for this problem arise in the scientific community. In this work the main contact detection algorithms are analyzed and a numerical experiment is performed, with the goal of finding out which algorithm has better computational performance and memory use, or if they efficiency depends on different scenario features. For performing the experiment, a parallel Discrete ElementMethod application was developed using CUDA/C++ with the main algorithms presented in literature, besides these, the author proposes and implements the Sorting Contact Detection algorithm parallelization, that hadn’t been parallelized until now. The tests have found that the parallel Sorting Contact Detection algorithm is the most efficient in all studied scenarios, achieving a good performance and a superiormemory usage than its peers. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Algoritmos de detecção de contatos são necessários em diferentes áreas da ciência e tecnologia, de jogos digitais e computação gráfica à simulações de alto desempenho e robótica. Esses algoritmos exigem grande esforço computacional e tendem a ser os gargalos das aplicação as quais fazem parte, principalmente em sistemas de grande escala ou em tempo real. Com a popularização das placas GPUs para uso científico e comercial, é natural que surjam implementações paralelas para esse problema. Nesse trabalho os principais algoritmos de detecção de contatos para GPU são analisados e é realizado umexperimento numérico, com objetivo de descobrir qual algoritmo é o melhor emtermos de desempenho computacional e uso de memória, ou se a eficiência de cada umdepende das diferentes características do cenários. Para a realização do experimento, foi implementado em CUDA/C++ uma aplicação paralela doMétodo dos Elementos Discretos comos principais algoritmos apresentados na literatura, além desses o autor propõe e implementa a paralelização do algoritmo de detecção com ordenação e busca binária que ainda não havia sido paralelizado. Após os testes é constatado que o algoritmo com ordenação e busca é o mais eficiente para todos os cenários estudados, obtendo nos resultados um bom desempenho em tempo de execução e com uso de memória muito superior aos outros.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufal.br:riufal/1564 |
| Date | 25 November 2016 |
| Creators | Lins, Bruno Normande |
| Contributors | Pereira, Leonardo Viana, http://lattes.cnpq.br/1126995918085550, Aquino, André Luiz Lins de, http://lattes.cnpq.br/7957606883987162, Santana Júnior, Orivaldo Vieira de, http://lattes.cnpq.br/5050555219716698 |
| Publisher | Universidade Federal de Alagoas, Brasil, Programa de Pós-Graduação em Modelagem Computacional de Conhecimento, UFAL |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFAL, instname:Universidade Federal de Alagoas, instacron:UFAL |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | bitstream:http://www.repositorio.ufal.br:8080/bitstream/riufal/1564/2/license.txt, bitstream:http://www.repositorio.ufal.br:8080/bitstream/riufal/1564/1/Avalia%C3%A7%C3%A3o+de+desempenho+de+algoritmos+paralelos+de+busca+de+vizinhos+em+cen%C3%A1rios+com+distribui%C3%A7%C3%B5es+espaciais+distintas.pdf |
Page generated in 0.2954 seconds