Método para o posicionamento de observadores em terrenos utilizando programação paralela em GPU

• Ano de defesa: 2014
• Autor(a) principal: Pena, Guilherme de Castro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; BR; Metodologias e técnicas da Computação; Sistemas de Computação; Mestrado em Ciência da Computação; UFV
• Palavras-chave em Português: Programação paralela - Computação; Visibilidade em terrenos; Sistemas de informação geográfica; Otimização combinatória; Parallel Programming - Computer; Visibility on land; Geographic information systems; Combinatorial optimization; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://locus.ufv.br/handle/123456789/2680

Este trabalho apresenta um algoritmo eficiente, chamado SparseSite, para solucio- nar o problema do posicionamento de observadores em terrenos. Este problema é uma aplicação do conceito de visibilidade que consiste em determinar quais pontos do terreno são visíveis a partir de um ponto específico, denominado observador, e o conjunto de pontos visíveis por este observador é chamado mapa de visibilidade ou viewshed. Assim, o objetivo do problema é selecionar um conjunto de observa- dores cujos os viewsheds otimizem a cobertura do terreno, com aplicações nas áreas de telecomunicações, planejamento ambiental, monitoramento militar, entre outras. Segundo Nagy [1994], este problema é NP-Difícil e portanto, não se conhece um al- goritmo eficiente que encontre a sua solução ótima. Assim, em geral, este problema é solucionado usando métodos heurísticos. Porém, mesmo as soluções aproximadas podem demandar um longo tempo de processamento devido ao grande volume de dados a ser analisado. O algoritmo descrito neste trabalho adota estratégias de programação paralela voltadas para arquiteturas de placas gráficas (GPUs) e além disso, permite o processamento de grandes volumes reorganizando os dados de en- trada do problema e capacitando o usuário a gerenciar o uso de memória pela GPU. Ele é uma extensão do método Site proposto por Franklin [2002]. A heurística uti- lizada encontra soluções melhores do que as encontradas pelo método Site, isto é, usando um número menor de observadores. Os resultados experimentais mostraram que, comparado aos principais algoritmos descritos na literatura, o nosso método se mostrou muito mais eficiente do que eles, sendo mais de 7000 vezes mais rápido do que o método que não utiliza nenhuma técnica de melhoria e mais de 20 vezes mais rápido do que o método paralelo anterior. Além disso, foram realizados testes do SparseSite para processar volumes de dados que não puderam ser processados pelos outros métodos devido à limitações de memória ou por demandarem muito tempo de processamento. Por fim, comparado ao nosso algoritmo anterior SiteGSM , o SparseSite é quase 3 vezes mais rápido e usa 10% da memória usada por ele.