PPGCC - Mestrado (Dissertações)
URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/597
Navegar
4 resultados
Resultados da Pesquisa
Item GeoCube : representação, computação, e visualização de cubos espaciais.(2012) Rocha, Tárik de Melo e Silva; Lima, Joubert de Castro; Carneiro, Tiago Garcia de Senna; Lisboa Filho, Jugurta; Pereira Junior, Álvaro Rodrigues; Santos, Haroldo GambiniA tecnologia SOLAP (Spatial On-Line Analytical Processing) oferece a junção das funcionalidades OLAP (Online Analytical Processing ) e SIG (Sistema de Informação Geográfica) e abre caminho para uma nova categoria de aplicações que fornecem suporte a manipulação, processamento e navegação em dados espaço-temporais organizados hierarquicamente. Os dados em um sistema OLAP são armazenados como cubos e estes são organizados segundo o conceito de dimensões, medidas e hierarquias. A materialização de um cubo de dados possui ordem de complexidade exponencial em relação ao consumo de memória e tempo de execução. Quando associamos informações espaciais ao cubo, a demanda de memória e processamento aumenta, tornando mais difícil a tarefa de oferecer respostas rápidas ao usuário. Atualmente, poucos trabalhos foram publicados na representação, computação e consulta de cubos espaço-temporais completos. As técnicas apresentadas como materialização seletiva, materialização baseada em aproximações e estruturas para indexação de regiões não oferecem soluções para computação de cubos completos e muitas vezes não podem ser aplicadas para uma grande variedade de funções de agregação espaciais. Arquiteturas de computadores baseadas em endereçamento compartilhado também não são utilizadas nos trabalhos correlatos. Nos trabalhos correlatos as hierarquias são especificadas manualmente por especialistas do domínio e muitas vezes as soluções limitam a quantidade e a variedade de medidas espaciais e não espaciais no cubo. Diante de tal cenário, é proposta uma abordagem para representação, computação e vi consulta de cubos espaço-temporais completos ou parciais, chamada GeoCube. A abordagem GeoCube pode ser executada em máquinas com múltiplos núcleos de processamento. Múltiplas funções de agregação espacial e estatística podem ser combinadas. Também é proposta uma abordagem para formação automática de hierarquias através de regras de vizinhança entre seus objetos espaciais. As regras de vizinhança podem ser definidas pelo usuário e executadas pelo GeoCube. O GeoCube já possui vizinhança nxn, onde n>1. Testes comparativos com um sistema implementado usando PostGIS e vistas materializadas mostram que a GeoCube consegue computar cubos de dados espaciais em até 1/6 do tempo gasto pela tecnologia PostGis em uma máquina com 8 núcleos de processamento.Item TerraME HPA : uma arquitetura de alto desempenho para simulação paralela de modelos ambientais.(2014) Silva, Saulo Henrique Cabral; Carneiro, Tiago Garcia de Senna; Lima, Joubert de CastroO contínuo aumento da complexidade dos modelos ambientais pode demandar o uso de múltiplos paradigmas de modelagem para descrever as interações entre sociedade e natureza. Além disto, o crescente volume de dados e de cálculos utilizados nestes modelos exige que as simulações tirem máximo proveito do paralelismo de hardware existente em arquiteturas multiprocessador e multicomputador. Neste contexto, este trabalho apresenta e avalia uma abordagem para o desenvolvimento e simulação de modelos ambientais concorrentes e baseados em múltiplos paradigmas. O objetivo principal é gerar simulações escaláveis e o objetivo secundário é produzir modelos concorrentes flexíveis. Isto é, modelos que possam ser facilmente verificados e evoluídos. A abordagem proposta consiste na tradução automatizada do código anotado do modelo sequencial em um código paralelo passível de ser executado por uma máquina virtual, cujo modelo de concorrência e mecanismo para balanceamento de carga independam dos paradigmas de modelagem utilizados. Para implementar esta abordagem, a plataforma de modelagem e simulação ambiental TerraME foi estendida de duas formas, dando origem a plataforma TerraME HPA (High Perfomance Architecture). Primeiro, a ela foi adicionada um pré-processador que traduz o código anotado dos modelos em programas concorrentes na linguagem de programação Lua. Depois, o interpretador Lua originalmente distribuído com o TerraME foi substituído pelo interpretador MOOM, também desenvolvido neste trabalho. O MOOM utiliza o mecanismo de bag-of-tasks para executar funções Lua em paralelo. Desta forma, ele reduz o nível de concorrência programado pelos modeladores e distribui a carga de trabalho das simulações entre os processadores disponíveis em hardware. Finalmente, vários benchmarks selecionados na literatura foram utilizados para avaliar o desempenho e a escalabilidade de diferentes plataformas de programação concorrente na linguagem Lua (ALua, Lane, Luaproc e MOOM) e de diferentes plataformas destinadas ao desenvolvimento simulações ambientais de alto desempenho: TerraME HPA, Repast HPC e D-MASON versões 1.5 e 2.1. Os resultados evidenciam que, quando comparados aos trabalhos correlatos, o interpretador MOOM e a plataforma TerraME HPA apresentaram uma escalabilidade muito boa em todos os cenários avaliados. As aplicações Lua resultantes desta abordagem são flexíveis, pois ao ignorar as anotações, os interpretadores permitem que elas sejam verificadas e evoluídas sequencialmente.Item Metaheurísticas de busca local para o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência.(2014) Silva, Cristiano Luís Turbino de França e; Santos, Haroldo GambiniEste trabalho apresenta uma proposta e a avaliação computacional de quatro métodos de busca local estocástica para o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência (UPMSP - unrelated parallel machine scheduling problem with sequence dependent setup times). As quatro abordagens metaheurísticas que são analisadas para o UPMSP baseam-se em: Simulated Annealing (SA), Iterated Local Search (ILS), Late Acceptance Hill Climbing (LAHC) e Step Counting Hill Climbing (SCHC). A estrutura das vizinhancas, bem como os parâmetros dos algoritmos, foram amplamente testados e analisados, sendo possível verificar como os parâmetros afetam o comportamento de cada algoritmo implementado e pesquisar os melhores parâmetros. As comparações dos resultados obtidos foram realizadas com os resultados apresentados por Vallada e Ruiz (2011), proponentes do conjunto de 50 instâncias consideradas e, mais recentemente, por Haddad (2012). O método que obteve o melhor resultado nessas 50 instâncias foi testado para todas as 1.000 instâncias grandes, apresentadas por Vallada e Ruiz (2011), melhorando em 96,6% (966 instâncias) a melhor solução conhecida encontrada por esses últimos autores.Item Algoritmos heurísticos híbridos para o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência.(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Haddad, Matheus Nohra; Souza, Marcone Jamilson FreitasEste trabalho aborda o problema de sequenciamento em máquinas paralelas não- relacionadas com tempos de preparação dependentes da sequência, dó inglês Unre- lated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSPST. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência de lase da máquina utilizada. O objetivo considerado neste problema é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makes pan. OUPMSPST é muito encontrado no âmbito industrial e pertence à classe NP- difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado VP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND)e Path Relinking(PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized AdaptiveS earch Procedure(GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, diferedos outros em três estratégias: a fase PR utiliza a estratégia mix edrelinking ao invés de backward relinking, as vizinhanças que formam o VND são usada sem ordem aleatória a cada chamada e não em ordem previamente de nida; por m,o GIVMP inclui um módulo de busca local feita pelo resolvedor CPLEX12.1 de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista base a dono problemado Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias ,tendo- severi cado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi compara do com outros seis da literatura, sendo dois no primeiro conjunto de problemas- teste e outros quatro no Segundo. No primeiro conjunto veri cou-se a superiorida de absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontra do desvios percentuais relativos médios menores e novas melhores soluções.No segundo conjunto de problemas-teste vericou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se,no entanto,que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados,impedindo uma comparação de robustez dos algoritmos.