Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2665
Tipo: Dissertação
Título: Mapas de visibilidade em grandes terrenos representados por grades regulares
Título(s) alternativo(s): Visibility maps on large terrain represented as regular square grids
Autor(es): Ferreira, Cháulio de Resende
Primeiro Orientador: Andrade, Marcus Vinícius Alvim
Primeiro avaliador: Davis Júnior, Clodoveu Augusto
Segundo avaliador: Ferreira, Ricardo dos Santos
Abstract: Uma operação muito comum em sistemas de informações geográficas (SIG) consiste no cálculo de mapas de visibilidade, ou viewsheds. Um mapa de visibilidade indica quais regiões de um terreno são visíveis a partir de um determinado ponto de observação, normalmente chamado de observador. Este trabalho apresenta dois novos algoritmos para cálculo de viewshed em grandes terrenos representados por grades regulares, ambos mais eficientes do que os demais encontrados em literatura. O primeiro algoritmo chama-se TiledVS e foi projeto especialmente para memória externa, ou seja, para reduzir o número de operações de entrada e saída (E/S) re- alizadas. Para isso, ele utiliza uma estrutura de dados denominada TiledMatrix, que subdivide o terreno em diversos blocos retangulares e gerencia os acessos aos dados de forma eficiente. De acordo com os resultados experimentais obtidos, este algoritmo é mais de 4 vezes mais rápido do que todos os outros encontrados em literatura. O segundo algoritmo é um algoritmo paralelo que utiliza o modelo de memória compartilhada (OpenMP ). Este algoritmo subdivide o terreno em diversos setores em volta do observador, de modo que cada um destes setores possa ser pro- cessado de forma independente. Os resultados experimentais mostraram que com um computador com 4 cores é possível obter processamentos 4 vezes mais rápidos do que a versão sequencial do mesmo algoritmo. Já com um computador com 16 cores, foram obtidos processamentos até 12 vezes mais rápidos.
In geographical information science (GIS) it is usual to compute the viewshed of a given point on a terrain. This point is usually called observer, and its viewshed indicates which terrain regions are visible from it. In this work we present two novel algorithms for viewshed computation on large grid terrains, both more efficient than other approaches found in related work. The first algorithm is called TiledVS . It was specially designed for external memory processing, that is, it performs a smaller number of in/out (I/O) operations. To do that, it uses a special library called TiledMatrix, which subdivides the terrain into several rectangular blocks and efficiently manages the accesses to the terrain cells. According to our experimental results, TiledVS is more than 4 times faster than all other previous algorithms. The second one is a parallel algorithm that uses the shared memory model (OpenMP). It subdivides the terrain into several sectors around the observer, such that each sector may be processed independently. Our experimental results showed that, using a personal computer with 4 cores, it is possible to compute the viewshed 4 times faster than with the serial implementation of the same algorithm. Using a computer with 16 cores, we obtained up to 12 times speedups.
Palavras-chave: Geoinformática
Visibilidade
Algoritmos para memória extera
Computação de alto desempenho
Geoinformatcs
Visibility
Algorithm for external memory
High performance computing
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
Programa: Mestrado em Ciência da Computação
Citação: FERREIRA, Cháulio de Resende. Visibility maps on large terrain represented as regular square grids. 2014. 81 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/2665
Data do documento: 12-Fev-2014
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf3,49 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.