[pt] O processamento de consulta paralelo tradicional utilize- se de nós computacionais para reduzir o tempo de processamento de consultas. Com o surgimento das grades computacionais, milhares de nós podem ser utilizados, desafiando as atuais técnicas de processamento de consulta a oferecerem um suporte massivo ao paralelismo em um ambiente onde as condições variam todo a instante. Em adição, as aplicações científicas executadas neste ambiente oferecem novas características de processamento de dados que devem ser integradas em um sistema desenvolvido para este ambiente. Neste trabalho apresentamos o sistema de processamento de consulta paralelo do CoDIMS-G, e seu novo operador Orbit que foi desenvolvido para suportar a avaliação de consultas iterativas. Neste modelo de execução as tuplas são constantemente avaliadas por um fragmento paralelo do plano de execução. O trabalho inclui o desenvolvimento do sistema de processamento de consulta e um novo algoritmo de escalonamento que, considera as variações de rede e o throughput de cada nó, permitindo ao sistema se adaptar constantemente as variações no ambiente. / [en] Traditional parallel query processing uses multiple computing nodes to reduce query response time. Within a Grid computing context, the availability of thousands of nodes challenge current parallel query processing techniques to support massive parallelism in a constantly varying environment conditions. In addition, scientific applications running on Grids offer new data processing characteristics that shall be integrated in such a framework. In this work we present the CoDIMS-G parallel query processing system with a full-fledged new query execution operator named Orbit. Orbit is designed for evaluating massive iterative based data processing. Tuples in Orbit iterate over a parallelized fragment of the query execution plan. This work includes the development of the query processing system and a new scheduling algorithm that considers variation on network and the throughput of each node. Such algorithm permits the system to adapt constantly to the changes in the environment.

[pt] Neste trabalho de dissertação são propostos algoritmos adaptativos que exploram a esparsidade em redes distribuídas de sensores para estimação de parâmetros e estimação espectral. São desenvolvidos algoritmos gradiente conjugado (CG) distribuído para os protocolos consenso e difusão em versão convencional e modificada (MCG). Esses algoritmos são desenvolvidos com exploração de esparsidade usando as funções penalidades l1 e log-sum. Os métodos propostos apresentam um melhor desempenho en termos de velocidade de convergência e desvio médio quadratico (MSD) que as já conhecidas variantes distribuídas do algoritmo least mean square (LMS) e muito próximo ao desempenho do algoritmo recursive least square (RLS). Além disso, propõe-se um algoritmo distribuído de optimização alternada de variáveis discretas e contínuas (DAMDC) baseado no LMS. O algoritmo DAMDC-LMS apresenta um desempenho muito próximo ao algoritmo oráculo e tem maior velocidade de convergência que os algoritmos estudados com exploração de esparsidade. Os resultados numéricos mostram que o algoritmo DAMDC-LMS pode ser aplicado em vários cenários. / [en] This dissertation proposes distributed adaptive algorithms exploiting sparsity for parameter and spectrum estimation over sensor networks. Conventional and modified conjugate gradient (CG and MCG) algorithms using consensus and diffusion strategies are presented. Sparsity-aware versions of CG an MCG algorithms using l1 and log-sum penalty functions are developed. The proposed sparsity-aware and non-sparse CG and MCG methods outperform the equivalent variants of the least-mean square (LMS) algorithms in terms of convergence rate and mean square deviation (MSD) at steady state, and have a close performance to the recursive least square (RLS) algorithm. The diffusion CG strategies have shown the best performance, specifically the adapt then combine (ATC) version. Furthermore a distributed alternating mixed discretecontinuous (DAMDC) algorithm to approach the oracle algorithm based on the diffusion strategy for parameter and spectrum estimation over sensor networks is proposed. An LMS type algorithm with the DAMDC proposed technique obtains the oracle matrix in an adaptive way and compare it with the existing sparsity-aware as well as the classical algorithms. The proposed algorithm has an improved performance in terms of MSD. Numerical results show that the DAMDC-LMS algorithm is reliable and can be applied in several scenarios.

[pt] O problema de escalonamento de tarefas divisíveis consiste em determinar como uma carga a ser processada deve ser dividida entre processadores e em que ordem cada fração de carga será enviada a cada processador. Considera-se o escalonamento em redes estrela com computadores e enlaces heterogêneos. Nesta dissertação são propostas formulações originais deste problema como modelos de programação linear inteira mista, assim como um novo algoritmo de complexidade O(n) para a solução ótima de um caso especial. Além disso, também são propostas duas novas heurísticas para o problema, que permitem a elaboração de bons escalonamentos para instâncias de grande porte em um reduzido tempo de processamento. / [en] The problem of divisible job scheduling consists of determining how to divide the data to be processed among processors and in which order each fraction should be sent to them. In this dissertation, we consider the divisible load scheduling problem in star networks with heterogeneous computers and links. Original mixed integer linear programming formulations of this problem are proposed, as well as a new algorithm with complexity O(n) to find the optimal solution for a special case. We also propose two fast heuristics that achieve good results for instances representing large scale computing systems.

[pt] O objetivo genérico desta tese foi o desenvolvimento de uma arquitetura computacional distribuída para a interpretação automática, baseada em objetos, de grandes volumes de dados de imagem de sensoriamento remoto, com foco na distribuição de dados e processamento em um ambiente de computação em nuvem. Dois objetivos específicos foram perseguidos: (i) o desenvolvimento de uma nova arquitetura distribuída para análise de imagens que é capaz de lidar com vetores e imagens ao mesmo tempo; e (ii) a modelagem e implementação de uma plataforma distribuída para a interpretação de grandes volumes de dados de sensoriamento remoto. Para validar a nova arquitetura, foram realizados experimentos com dois modelos de classificação – um de cobertura da terra e outro de uso do solo – sobre uma imagem QuickBird de uma área do município de São Paulo. Os modelos de classificação, propostos por Novack (Novack09), foram recriados usando as estruturas de representação do conhecimento da nova plataforma. Nos experimentos executados, a plataforma foi capaz de processar todo o modelo de classificação de cobertura da terra para uma imagem de 32.000x32.000 pixels (aproximadamente 3,81 GB), com aproximadamente 8 milhões de objetos de imagem (aproximadamente 23,2 GB), em apenas 1 hora, utilizando 32 máquinas em um serviço de nuvem comercial. Resultados igualmente interessantes foram obtidos para o modelo de classificação de uso do solo. Outra possibilidade de paralelismo oferecida pelas estruturas de representação de conhecimento da plataforma também foi avaliada. / [en] The general objective of this thesis was the development of a distributed computational architecture for the automatic, object-based interpretation of large volumes of remote sensing image data, focusing on data and processing distribution in a cloud computing environment. Two specific objectives were pursued: (i) the development of a novel distributed architecture for image analysis that is able to deal with vectors and rasters at the same time; and (ii) the design and implementation of an open-source, distributed platform for the interpretation of very large volumes of remote sensing data. In order to validate the new architecture, experiments were carried out using two classification models – land cover and land use – on a QuickBird image of an area of the São Paulo municipality. The classification models, proposed by Novack (Novack09), were recreated using the knowledge representation structures available in the new platform. In the executed experiments, the platform was able to process the whole land cover classification model on a 32,000x32,000-pixel image (approximately 3.81 GB), with approximately 8 million image objects (approximately 23.2 GB), in just one hour, using 32 machines in a commercial cloud computing service. Equally interesting results were obtained for the land use classification model. Another possibility of parallelism provided by the platform s knowledge representation structures was also evaluated.

[pt] A Segmentação de imagens representa uma etapa fundamental na análise de imagens e geralmente envolve um alto custo computacional, especialmente ao lidar com grandes volumes de dados. Devido ao significativo aumento nas resoluções espaciais, espectrais e temporais das imagens de sensoriamento remoto nos últimos anos, as soluções sequenciais e paralelas atualmente empregadas não conseguem alcançar os níveis de desempenho e escalabilidade esperados. Este trabalho propõe um método de segmentação de imagens distribuída capaz de lidar, de forma escalável e eficiente, com imagens grandes de altíssima resolução. A solução proposta é baseada no modelo MapReduce, que oferece uma estrutura altamente escalável e confiável para armazenar e processar dados muito grandes em ambientes de computação em clusters e, em particular, também para nuvens privadas e comerciais. O método proposto é extensível a qualquer algoritmo de crescimento de regiões podendo também ser adaptado para outros modelos. A solução foi implementada e validada usando a plataforma Hadoop. Os resultados experimentais comprovam a viabilidade de realizar a segmentação distribuída sobre o modelo MapReduce por intermédio da computação na nuvem. / [en] Image segmentation is a critical step in image analysis, and generally involves a high computational cost, especially when dealing with large volumes of data. Given the significant increase in the spatial, spectral and temporal resolutions of remote sensing imagery in the last years, current sequential and parallel solutions fail to deliver the expected performance and scalability. This work proposes a distributed image segmentation method, capable of handling very large high-resolution images in an efficient and scalable way. The proposed solution is based on the MapReduce model, which offers a highly scalable and reliable framework for storing and processing massive data in cluster environments and in private and public computing clouds. The proposed method is extendable to any region-growing algorithm and can be adapted to other models. The solution was implemented and validated using the Hadoop platform. Experimental results attest the viability of performing distributed segmentation over the MapReduce model through cloud computing.

[pt] Este trabalho investiga o problema de otimização de alternativas para o desenvolvimento de campos petrolíferos. Uma alternativa de desenvolvimento refere-se à forma como um campo petrolífero, conhecido e delimitado, é colocado em produção, isto é, diz respeito à determinação do número, localização e agendamento dos poços de produção e injeção. Otimização de alternativas consiste em encontrar as configurações de produção que, a longo prazo, forneçam o maior valor presente líquido (VPL), obtido a partir do custo de investimento inicial, do preço do petróleo, da produção de óleo e gás, dos custos de operação, das alíquotas de impostos e dos royalties pagos durante o tempo de produção. A produção de óleo é obtida usando-se um simulador de reservatório. O simulador recebe a informação da alternativa a ser simulada e retorna a curva de produção de óleo e gás no tempo de produção especificado. Cada execução do simulador pode demorar desde alguns segundos até várias horas, dependendo da complexidade do reservatório modelado. Este trabalho propõe, implementa e avalia um sistema inteligente de otimização que emprega: algoritmos genéticos (AGs) para a busca de uma alternativa de desenvolvimento ótima; uso de ambiente de computação paralela para a simulação de reservatório e cálculo do VPL das alternativas; um módulo de inferência baseado em modelos inteligentes para aproximar a função de produção de óleo; e um módulo de caracterização baseado em mapas de qualidade para obter informações do campo petrolífero a serem aproveitadas durante a otimização. Este trabalho consistiu de 4 etapas: uma revisão da literatura sobre desenvolvimento de campos petrolíferos, simulação de reservatórios e caracterização de campos petrolíferos; um estudo das técnicas de inteligência computacional para otimização e aproximação de funções; desenvolvimento do modelo proposto de otimização de alternativas; e o estudo de casos. O modelo proposto foi avaliado com configurações de reservatório homogêneo e heterogêneo obtendo resultados da otimização, do uso da caracterização, da aproximação pelo módulo de inferência e do uso do ambiente paralelo. Os resultados obtidos mostram que, o modelo proposto, permite alcançar respostas com altos VPL sem utilizar conhecimento prévio, e também a partir de informações extraídas da caracterização ou fornecidas pelo próprio especialista como sementes iniciais na otimização. A principal contribuição deste trabalho é a concepção e implementação de um sistema baseado em técnicas inteligentes para otimizar alternativas de desenvolvimento com uma redução do tempo computacional para um processo iterativo, obtida tanto pelo aproveitamento do poder computacional de um ambiente de computação paralela, como pelo uso de aproximações das curvas de produção. Este sistema inteligente oferece uma ferramenta de suporte à decisão que automatiza a busca de alternativas de desenvolvimento e aproveita informações vindas do conhecimento do engenheiro de reservatório. / [en] This work investigates the problem of optimization of alternatives for petroleum fields` development. A development alternative refers to the way a well-known and delimited petroleum field is placed in production. This process involves the determination of the number, localization and scheduling of producer and injector wells. Thus, the optimization of alternatives consists of finding the production configurations that, in the long term, provide the maximum net present value (NPV); this is obtained from the investment cost, oil price, oil & gas production, operation costs and taxes and royalties paid during the production time. The oil and gas production is obtained from a reservoir simulator. The simulator receives information from the alternative to be simulated, and returns an oil & gas production to specified production time. Each simulation can take from a few seconds to several hours, depending on complexity of the reservoir being modeled. This work proposes, implements and evaluates an intelligent optimization system that comprises: genetic algorithms (GAs) to search an optimal development alternative; using of parallel computing environment to reservoir simulation and NPV computing; an inference module, basis in intelligent models, to approximate the oil production function; and a oilfield characterization module, basis in quality maps, to obtain information about the oilfield to use during optimization process. This work consisted of four stages: a literature review about petroleum field development and reservoir simulation; a study about computational intelligence techniques applied in optimization and functions approximation; the development of alternatives optimization proposal model; and the case studies. The proposal model was evaluated using homogeneous and heterogeneous reservoir configurations, obtaining results of optimization, by using characterization, the inference module and the parallel environment. The obtained results indicate that the proposed model provides alternatives with high NPV without previous knowledge and also from information provided by characterization or information inserted by the expert as initial seeds into optimization. The main contribution of this work is the conception and the implementation of a system basis in intelligent techniques to optimize development alternatives offering a reduction time to an iterative process, obtained from exploit of computational effort of a parallel computing environment or by using of production curves approximations. This intelligent system offers a decision-support tool that allows automating the search process of development alternatives and exploiting information from knowledge of reservoir engineers.