Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2680
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.authorPena, Guilherme de Castro
dc.date.accessioned2015-03-26T13:10:42Z-
dc.date.available2015-02-03
dc.date.available2015-03-26T13:10:42Z-
dc.date.issued2014-08-07
dc.identifier.citationPENA, 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.por
dc.identifier.urihttp://locus.ufv.br/handle/123456789/2680-
dc.description.abstractEste 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.pt_BR
dc.description.abstractThis 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.eng
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.formatapplication/pdfpor
dc.languageporpor
dc.publisherUniversidade Federal de Viçosapor
dc.rightsAcesso Abertopor
dc.subjectProgramação paralela - Computaçãopor
dc.subjectVisibilidade em terrenospor
dc.subjectSistemas de informação geográficapor
dc.subjectOtimização combinatóriapor
dc.subjectParallel Programming - Computereng
dc.subjectVisibility on landeng
dc.subjectGeographic information systemseng
dc.subjectCombinatorial optimizationeng
dc.titleMétodo para o posicionamento de observadores em terrenos utilizando programação paralela em GPUpor
dc.title.alternativeMethod for siting observers on terrains using GPU parallel programmingeng
dc.typeDissertaçãopor
dc.contributor.authorLatteshttp://lattes.cnpq.br/5372125629958446por
dc.publisher.countryBRpor
dc.publisher.departmentMetodologias e técnicas da Computação; Sistemas de Computaçãopor
dc.publisher.programMestrado em Ciência da Computaçãopor
dc.publisher.initialsUFVpor
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.contributor.advisor1Andrade, Marcus Vinícius Alvim
dc.contributor.advisor1Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4785900Z5por
dc.contributor.referee1Lobosco, Marcelo
dc.contributor.referee1Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4763963U7por
dc.contributor.referee2Ferreira, Ricardo dos Santos
dc.contributor.referee2Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4723626E5por
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.