Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2680
Tipo: Dissertação
Título: Método para o posicionamento de observadores em terrenos utilizando programação paralela em GPU
Título(s) alternativo(s): Method for siting observers on terrains using GPU parallel programming
Autor(es): Pena, Guilherme de Castro
Primeiro Orientador: Andrade, Marcus Vinícius Alvim
Primeiro avaliador: Lobosco, Marcelo
Segundo avaliador: Ferreira, Ricardo dos Santos
Abstract: 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.
This work presents an efficient algorithm , named SparseSite, to siting observers on terrains. This problem concerns visibility, that is, determining the set of points that are visible from a particular point, called observer, and the set of visible points from this observer is called viewshed. Thus, the goal of this problem is to select a set of observers in order to optimally cover the terrain. The applications include telecommunications, environmental planning, military monitoring and so forth. Ac- cording to Nagy [1994], the siting problem is NP-Hard and, therefore, there is no known efficient algorithm to find its optimal solution. Thus, in general, it is used a heuristic to obtain an approximate solution. But even obtaining approximate solutions for this optimization problem can demand a long processing time since sometimes it is necessary to process a huge amount of high-resolution geographic data. The algorithm described in this work adopts parallel programming strategy for graphics processing units (GPUs) and furthermore, it allows the processing of large data volumes rearranging the input data of the problem and enabling the user to manage the memory usage by the GPU. This algorithm extends the method Site proposed by Franklin [2002] and the heuristic used finds even better solutions than those found by the method Site. The experimental results showed that, compared against the mainly algorithms described in previous works, our method proved to be more efficient than all of them, more than 7000 times faster than the sequential method without improvement techniques and 20 times faster than a previous pa- rallel method. Additionally, some tests of the SparseSite were performed to process volumes of data which cannot be processed by the other methods due to memory limitations or to demand a lot of processing time. Lastly, compared against our previous algorithm SiteGSM , the SparseSite is almost 3 times faster and uses 10% of the amount of memory used by it.
Palavras-chave: 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: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: BR
Editor: Universidade Federal de Viçosa
Sigla da Instituição: UFV
Departamento: Metodologias e técnicas da Computação; Sistemas de Computação
Citação: PENA, Guilherme de Castro. Method for siting observers on terrains using GPU parallel programming. 2014. 74 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2014.
Tipo de Acesso: Acesso Aberto
URI: http://locus.ufv.br/handle/123456789/2680
Data do documento: 7-Ago-2014
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf2,68 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.