A Linguagem RS é destinada a programação de núcleos reativos centralizados. Tais núcleos são responsáveis por toda a lógica de um sistema reativo, manipulando os sinais de entrada, realizando as reações e gerando os sinais de saída. Sendo sua idéia inicial tratar apenas processos centralizados, não houve a preocupação com a distribuição. Este trabalho tem como principal objetivo apresentar os aspectos introduzidos de uma nova versão para a Linguagem e para o Compilador RS, que possibilitam a execução de programas distribuídos. Além da possibilidade de execução de sistemas reativos distribuídos, foi acrescentado à Linguagem RS extensões já previstas na sua criação, como sinais inibidores, regras de exclusão mútua e concomitância, a possibilidade de disparo de mais de uma regra em um mesmo instante e a limpeza léxica do código fonte RS. As modificações incorporadas nesta nova versão da linguagem, foram efetivadas através de um novo compilador, chamado de Compilador RS 5.0. O protótipo implementado oferece a geração de três formatos de código: o formato padrão da linguagem RS (os autômatos e as regras correspondentes), códigos na linguagem C para a simulação dos autômatos (tanto para programas distribuídos quanto não-distribuídos) e arquivos no formato portável OC, que é um formato de código objeto padrão para as linguagens reativas. Para a distribuição e implementação da Linguagem RS foi necessária a criação de um novo núcleo de comunicação do MDX, que é responsável pela comunicação dos autômatos RSD. Este núcleo é dividido em três partes. A primeira trata da definição de um modelo formal com as mudanças necessárias para que a linguagem RS consiga trabalhar de forma distribuída, a segunda mostra o projeto do novo núcleo MDX e a terceira apresenta a implementação em C e MDX dos autômatos gerados pelo Compilador RS 5.0. Por fim, exemplos de aplicação desta nova linguagem são apresentados, onde podem ser vistos a importância e o acréscimo proporcionado por este trabalho tanto à linguagem RS quanto à programação de sistemas reativos síncronos. / The RS language is intended to the programming of centralized reactive kernels. Such kernels are responsible for the logic of a reactive system, manipulating the input signals, carrying through the reactions and generating the output signals. Being its initial idea to treat only centered processes, it did not have the concern with the distribution. The main objective of this work is to describe the process of creation of a new version for the Language and Compiler RS, that make possible the execution of distributed programs. Beyond the possibility of execution distributed reactive systems, it was added to RS language foreseen extensions already in its creation, as inhibiting signals, rules of manual exclusion and concurrence, the possibility of detonation of more than a rule in one exactly instant and the lexical cleanness of the RS code source. The modifications incorporated in this new version of the language, had been accomplished through a new compiler, called Compiler RS 5.0. The implemented archetype offers the generation of three formats of code: the standard format of RS language (the corresponding automatons and rules), codes in the language C for the simulation of the automatons and archives in OC portable format, that is a object format code standard for the reactive languages. For the distribution and implementation of Language RS was necessary the creation of a new kernel of communication of the MDX, that is responsible for the communication of RSD automatons. It is divided in three parts. The first one deals with the definition of a formal model that defines the necessary changes so that RS language obtains to work of distributed form, the second shows the design of new MDX kernel and third presents the implementation in C and MDX of the automatons generated for Compiler RS 5.0. Finally, examples of application of this new language are presented, where the importance and the proportionate upgrade for this work to RS language how to the programming of synchronous reactive systems can in such a way be seen.

Este trabalho a dedicado ao estudo da exploração de paralelismo OU na programação em lógica com restrições em ambientes distribuídos. A programação em lógica, cuja linguagem mais significativa 6 Prolog, tem como premissa a utilização da lógica de predicados como linguagem computacional. A programação em lógica com restrições (CLP) é uma extensão da programação em lógica, onde busca-se a eficiência e a possibilidade de executar novas classes de problemas. Variáveis em CLP podem pertencer a domínios específicos como, por exemplo, reais ou booleanos. O principal conceito introduzido é a restrição. Restrição a uma equação que representa uma certa informação sobre uma variável e a sua relação com outras variáveis. o uso de restrições foi proposto para diminuir o espaço de busca na execução dos programas. Apesar de mais eficientes que a programação em lógica clássica, para algumas aplicações reais o desempenho das linguagens CLP ainda é insatisfatório. Por isso, é necessário buscar alternativas novas como a execução em paralelo. A exploração de paralelismo implícito em programas em 1ógica já demonstrou resultados promissores. Vários modelos foram propostos e implementados utilizando as duas principais fontes de paralelismo — E e OU — de forma isolada ou combinada. O objetivo principal desse trabalho é apresentar o modelo pclp(FD) de exploração de paralelismo OU multi-sequêncial para um ambiente com memória distribuída. O modelo pclp(FD) caracteriza-se pela existência de vários trabalhadores, cada um deles possuindo uma maquina abstrata completa. O escalonamento de tarefas a realizado por uma política dinâmica e distribuída. Uma tarefa em pclp(FD) equivale a um ponto de escolha e a um contexto de execução. O contexto de execução a formado por porções da pilha do exportador. Para que o importador tenha acesso ao contexto de execução utiliza-se a cópia incremental, que a uma das varias técnicas possíveis. Cada trabalhador possui a sua própria copia privada das pilhas de execução. A cópia caracteriza-se pelo envio das pilhas de execução do exportador para uma área privada do importador. A cópia incremental é uma técnica mais otimizada que verifica a existência de partes comuns entre os trabalhadores, copiando apenas as panes novas. O algoritmo de cópia incremental proposto no modelo a feito sem nenhuma centralização de informação do estado das pilhas. O projeto e implementação de um prot6tipo para esse modelo, utilizando a linguagem clp(FD), que implementa CLP sobre domínios finitos, permitirá uma analise das vantagens e desvantagens do modelo proposto. Os resultados obtidos com a análise servirão de base para trabalhos futuros, visando aprimorar a implementação e o modelo. / This work is dedicated to the study of the exploration of OR parallelism in Constraint Logic Programming for distributed environment. Logic Programming, which the most meaningful language is Prolog, has as premise the use of the logic of predicates as computational language. Constraint Logic Programming or CLP is an extension of the logic programming, where efficiency and the possibility to execute new kinds of problems are searched. A variable in CLP can belong to specific domains as, for example, Real or Boolean. The main concept introduced is the constraint. Constraint is an equation that represents a certain information over a variable and its relation with others variables. The use of constraints was proposed to decrease search space in the program execution. Although it is more efficient than classic logic programming, for some real applications, the performance of CLP languages still is unsatisfactory. So, it is necessary to search alternatives as parallel execution. The exploration of implicit parallelism in programs in logic has already demonstrated promising results. Several models have been proposed and implemented using the two main sources of parallelism - AND and OR — in an isolated or combined form. The main objective of this work is to present the pclp(FD) model of exploration of multi-sequential OR parallelism for a distributed memory environment. The pclp(FD) model is characterized for the existence of some workers, each one of them possessing a complete abstract machine. Task scheduling is executed by one dynamic and distributed policy. A task in pclp(FD) is equivalent to a choice point and an execution context. Execution context is formed by portions of the stack of the exporter. So that importer has access to the execution context, it uses incremental copy, which is one of the several possible techniques. The copy is characterized for sending execution stacks of the exporter to a private area of the importer, that is, each worker possesses its private copy of the execution stacks. The incremental copy is a more optimized technique that verifies the existence of common parts between workers, copying only the new ones. The incremental copy algorithm proposed in the model executes without centralized information of the state of the stacks. A prototype project and implementation for this model, using the language clp(FD), that implements CLP over finite domains, will allow an analysis of advantages and disadvantages of the considered model. The results gotten with the analysis will serve of base for future works, aiming to improve the implementation and the model.

É notável o avanço da utilização de aplicações multimídia nos diversos setores da atividade humana. Independente da área, seja ela educação ou entretenimento, a possibilidade de agregar recursos dinâmicos como áudio e vídeo aos já largamente utilizados como texto e imagem acarreta em benefícios aos usuários destas aplicações. Além disso, com a popularização da Internet, ha uma crescente demanda pela sua execução em ambientes distribuídos. Este trabalho teve como objetivo desenvolver MUSE, um ambiente gráfico para modelagem de aplicações multimídia interativas. Através de uma interface gráfica avançada e de um novo modelo de autoria de alto nível, e possível a criação de sistemas complexos de forma rápida e intuitiva. 0 modelo de autoria proposto neste trabalho e adotado pelo ambiente prevê a possibilidade de os elementos que constituem a aplicação estarem dispersos em uma rede de computadores, permitindo a definição de limiares aceitáveis de atraso e componentes alternativos. Pela grande expressividade do modelo, no entanto, podem ser geradas especificações com inconsistências lógicas e temporais. Por esta razão, o ambiente prove ainda especificações E-LOTOS - uma extensão temporal de LOTOS - utilizadas para fins de analise e verificação, permitindo a validação dos requisitos temporais das aplicações definidas pelo autor. A formalização das especificações através de uma TDF, além de viabilizar sua validação, prove descrições sem ambigüidades, que podem ser alternativamente utilizadas por autores que sejam familiarizados com a técnica de descrição formal. Este trabalho é parte do projeto DAMD (Design de Aplicações Multimídia Distribuídas) dentro do programa PROTEM fase 2, que tem por objetivo fornecer uma metodologia que cubra o ciclo completo das aplicações multimídia distribuídas e que permita a um autor não especializado em métodos formais desenvolver essas aplicações naturalmente. / It is notable the advance of multimedia applications utilization in several fields of human activity. Independent from the area, whether education or entertainment, the possibility to aggregate dynamic resources like audio and video to the ones already widely used like text and image results in benefits to the users of such applications. Besides, with the popularization of the Internet, there is an increasing demand for their execution in distributed environments. This work presents MUSE, a graphical environment for modeling interactive multimedia applications. Through an advanced graphic interface and a new high-level authoring model, it is possible to create complex systems in a fast and intuitive way. The authoring model proposed in this work and adopted by the tool deals with media objects distributed in a computer network, allowing the definition of acceptable delay thresholds and alternative media objects. Due to the large expressiveness of the model, however, specifications can be generated with logical and temporary inconsistencies. For this reason, the tool also provides E-LOTOS specifications used with the purpose of analyzing and verifying the applications aiming at validating the temporal requirements defined by the author. The formalization of the specifications by means of a TDF, beyond making their validation possible, provides descriptions free of ambiguities, which may be alternatively used by authors familiarized with the formal description technique. This work is part of DAMD (Distributed Multimedia Applications Design) project, sponsored by the Brazilian research council. Its main objectives are to provide a methodology to completely cover the distributed multimedia applications development cycle and to allow authors who are not expert in formal methods to easily develop their applications.

As threads de aplicações paralelas cooperam a fim de cumprir suas tarefas, dessa forma, comunicação é realizada entre elas. A latência de comunicação entre os núcleos em arquiteturas multiprocessadas diferem dependendo da hierarquia de memória e das interconexões. Com o aumento do número de núcleos por chip e número de threads por núcleo, esta diferença entre as latências de comunicação está aumentando. Portanto, é importante mapear as threads de aplicações paralelas levando em conta a comunicação entre elas. Em aplicações paralelas baseadas no paradigma de memória compartilhada, a comunicação é implícita e ocorre através de acessos à variáveis compartilhadas, o que torna difícil a descoberta do padrão de comunicação entre as threads. Mecanismos tradicionais usam simulação para monitorar os acessos à memória realizados pela aplicação, requerendo modificações no código fonte e aumentando drasticamente a sobrecarga. Nesta dissertação de mestrado, são introduzidos dois mecanismos inovadores com uma baixa sobrecarga para se detectar o padrão de comunicação entre threads. O primeiro mecanismo faz uso de informações sobre linhas compartilhadas de caches providas por protocolos de coerência de cache. O segundo mecanismo utiliza a Translation Lookaside Buffer (TLB) para detectar quais páginas de memória cada núcleo está acessando. Ambos os mecanismos dependem totalmente do hardware, o que torna o mapeamento de threads transparente aos programadores e permite que ele seja realizado dinamicamente pelo sistema operacional. Além disto, nenhuma tarefa de alta sobrecarga, como simulação, é requerida. As propostas foram avaliadas com o NAS Parallel Benchmarks (NPB), obtendo representações precisas dos padrões de comunicação. Mapeamentos para as threads foram gerados utilizando os padrões de comunicação descobertos e um algoritmo de mapeamento. O problema do mapeamento é NP-Difícil. Portanto, de forma a se atingir uma complexidade polinomial, o algoritmo empregado é heurístico, baseado no algoritmo de emparelhamento de grafos de Edmonds. Executando as aplicações com o mapeamento resultou em um ganho de desempenho de até 15; 3%. O número de faltas na cache, invalidações em linhas de cache e transações de espionagem foram reduzidos em até 31; 9%, 41% e 65; 4%, respectivamente. / The threads of parallel applications cooperate in order to fulfill their tasks, thereby communication is performed among themselves. The communication latency between the cores in a multiprocessor architecture differs depending on the memory hierarchy and the interconnections. With the increase in the number of cores per chip and the number of threads per core, this difference between the communication latencies is increasing. Therefore, it is important to map the threads of parallel applications taking into account the communication between them. In parallel applications based on the shared memory paradigm, the communication is implicit and occurs through accesses to shared variables, which makes difficult to detect the communication pattern between the threads. Traditional approaches use simulation to monitor the memory accesses performed by the application, requiring modifications to the source code and drastically increasing the overhead. In this master thesis, we introduce two novel light-weight mechanisms to find the communication pattern of threads. The first mechanism makes use of the information about shared cache lines provided by cache coherence protocols. The second mechanism makes use of the Translation Lookaside Buffer (TLB) to detect which memory pages each core is accessing. Both our mechanisms rely entirely on hardware features, which makes the thread mapping transparent to the programmer and allows it to be performed dynamically by the operating system. Moreover, no time consuming task, such as simulation, is required. We evaluated our mechanisms with the NAS Parallel Benchmarks (NPB) and obtained accurate representations of the communication patterns. We generated thread mappings from the detected communication patterns using a mapping algorithm. Mapping is a NP-Hard problem. Therefore, in order to achieve a polynomial complexity, we designed a heuristic method based on the Edmonds graph matching algorithm. Running the applications with these mappings resulted in performance improvements of up to 15.3% compared to the original scheduler of the operating system. The number of cache misses, cache line invalidations and snoop transactions were reduced by up to 31.9%, 41% and 65.4%, respectively.

É notável o avanço da utilização de aplicações multimídia nos diversos setores da atividade humana. Independente da área, seja ela educação ou entretenimento, a possibilidade de agregar recursos dinâmicos como áudio e vídeo aos já largamente utilizados como texto e imagem acarreta em benefícios aos usuários destas aplicações. Além disso, com a popularização da Internet, ha uma crescente demanda pela sua execução em ambientes distribuídos. Este trabalho teve como objetivo desenvolver MUSE, um ambiente gráfico para modelagem de aplicações multimídia interativas. Através de uma interface gráfica avançada e de um novo modelo de autoria de alto nível, e possível a criação de sistemas complexos de forma rápida e intuitiva. 0 modelo de autoria proposto neste trabalho e adotado pelo ambiente prevê a possibilidade de os elementos que constituem a aplicação estarem dispersos em uma rede de computadores, permitindo a definição de limiares aceitáveis de atraso e componentes alternativos. Pela grande expressividade do modelo, no entanto, podem ser geradas especificações com inconsistências lógicas e temporais. Por esta razão, o ambiente prove ainda especificações E-LOTOS - uma extensão temporal de LOTOS - utilizadas para fins de analise e verificação, permitindo a validação dos requisitos temporais das aplicações definidas pelo autor. A formalização das especificações através de uma TDF, além de viabilizar sua validação, prove descrições sem ambigüidades, que podem ser alternativamente utilizadas por autores que sejam familiarizados com a técnica de descrição formal. Este trabalho é parte do projeto DAMD (Design de Aplicações Multimídia Distribuídas) dentro do programa PROTEM fase 2, que tem por objetivo fornecer uma metodologia que cubra o ciclo completo das aplicações multimídia distribuídas e que permita a um autor não especializado em métodos formais desenvolver essas aplicações naturalmente. / It is notable the advance of multimedia applications utilization in several fields of human activity. Independent from the area, whether education or entertainment, the possibility to aggregate dynamic resources like audio and video to the ones already widely used like text and image results in benefits to the users of such applications. Besides, with the popularization of the Internet, there is an increasing demand for their execution in distributed environments. This work presents MUSE, a graphical environment for modeling interactive multimedia applications. Through an advanced graphic interface and a new high-level authoring model, it is possible to create complex systems in a fast and intuitive way. The authoring model proposed in this work and adopted by the tool deals with media objects distributed in a computer network, allowing the definition of acceptable delay thresholds and alternative media objects. Due to the large expressiveness of the model, however, specifications can be generated with logical and temporary inconsistencies. For this reason, the tool also provides E-LOTOS specifications used with the purpose of analyzing and verifying the applications aiming at validating the temporal requirements defined by the author. The formalization of the specifications by means of a TDF, beyond making their validation possible, provides descriptions free of ambiguities, which may be alternatively used by authors familiarized with the formal description technique. This work is part of DAMD (Distributed Multimedia Applications Design) project, sponsored by the Brazilian research council. Its main objectives are to provide a methodology to completely cover the distributed multimedia applications development cycle and to allow authors who are not expert in formal methods to easily develop their applications.

As threads de aplicações paralelas cooperam a fim de cumprir suas tarefas, dessa forma, comunicação é realizada entre elas. A latência de comunicação entre os núcleos em arquiteturas multiprocessadas diferem dependendo da hierarquia de memória e das interconexões. Com o aumento do número de núcleos por chip e número de threads por núcleo, esta diferença entre as latências de comunicação está aumentando. Portanto, é importante mapear as threads de aplicações paralelas levando em conta a comunicação entre elas. Em aplicações paralelas baseadas no paradigma de memória compartilhada, a comunicação é implícita e ocorre através de acessos à variáveis compartilhadas, o que torna difícil a descoberta do padrão de comunicação entre as threads. Mecanismos tradicionais usam simulação para monitorar os acessos à memória realizados pela aplicação, requerendo modificações no código fonte e aumentando drasticamente a sobrecarga. Nesta dissertação de mestrado, são introduzidos dois mecanismos inovadores com uma baixa sobrecarga para se detectar o padrão de comunicação entre threads. O primeiro mecanismo faz uso de informações sobre linhas compartilhadas de caches providas por protocolos de coerência de cache. O segundo mecanismo utiliza a Translation Lookaside Buffer (TLB) para detectar quais páginas de memória cada núcleo está acessando. Ambos os mecanismos dependem totalmente do hardware, o que torna o mapeamento de threads transparente aos programadores e permite que ele seja realizado dinamicamente pelo sistema operacional. Além disto, nenhuma tarefa de alta sobrecarga, como simulação, é requerida. As propostas foram avaliadas com o NAS Parallel Benchmarks (NPB), obtendo representações precisas dos padrões de comunicação. Mapeamentos para as threads foram gerados utilizando os padrões de comunicação descobertos e um algoritmo de mapeamento. O problema do mapeamento é NP-Difícil. Portanto, de forma a se atingir uma complexidade polinomial, o algoritmo empregado é heurístico, baseado no algoritmo de emparelhamento de grafos de Edmonds. Executando as aplicações com o mapeamento resultou em um ganho de desempenho de até 15; 3%. O número de faltas na cache, invalidações em linhas de cache e transações de espionagem foram reduzidos em até 31; 9%, 41% e 65; 4%, respectivamente. / The threads of parallel applications cooperate in order to fulfill their tasks, thereby communication is performed among themselves. The communication latency between the cores in a multiprocessor architecture differs depending on the memory hierarchy and the interconnections. With the increase in the number of cores per chip and the number of threads per core, this difference between the communication latencies is increasing. Therefore, it is important to map the threads of parallel applications taking into account the communication between them. In parallel applications based on the shared memory paradigm, the communication is implicit and occurs through accesses to shared variables, which makes difficult to detect the communication pattern between the threads. Traditional approaches use simulation to monitor the memory accesses performed by the application, requiring modifications to the source code and drastically increasing the overhead. In this master thesis, we introduce two novel light-weight mechanisms to find the communication pattern of threads. The first mechanism makes use of the information about shared cache lines provided by cache coherence protocols. The second mechanism makes use of the Translation Lookaside Buffer (TLB) to detect which memory pages each core is accessing. Both our mechanisms rely entirely on hardware features, which makes the thread mapping transparent to the programmer and allows it to be performed dynamically by the operating system. Moreover, no time consuming task, such as simulation, is required. We evaluated our mechanisms with the NAS Parallel Benchmarks (NPB) and obtained accurate representations of the communication patterns. We generated thread mappings from the detected communication patterns using a mapping algorithm. Mapping is a NP-Hard problem. Therefore, in order to achieve a polynomial complexity, we designed a heuristic method based on the Edmonds graph matching algorithm. Running the applications with these mappings resulted in performance improvements of up to 15.3% compared to the original scheduler of the operating system. The number of cache misses, cache line invalidations and snoop transactions were reduced by up to 31.9%, 41% and 65.4%, respectively.

[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.

Made available in DSpace on 2016-04-29T14:23:52Z (GMT). No. of bitstreams: 1 Diogo Cortiz Silva.pdf: 1671903 bytes, checksum: ee5719b8fbbb5e1d9a7de4b35b463f43 (MD5) Previous issue date: 2009-10-01 / This research debates the excess of worldwide available computational resources with exceeded processing capacity and also how the utilization of the sharing and collaboration concepts influence the integration of those devices to constitute an economic environment with high processing capacity. Currently, it is possible to find a great amount of personal computers, servers and others devices that show high level of idleness, while they could be being used for another purpose, once there are many scientific researches, collaborative projects and digital inclusion programs that are short of resources to reach theirs objectives. The Grid Computing technology was conceived as an alternative to integrate geographically distributed resources pertaining to different domains, enabling a decentralized computational environment. The main objective of this research is to analyze how this technology can generate benefits to the social, environment and economic contexts. In the social approach, Grid Computing stimulates the collaboration and the sharing of computational resources and applications, as well as providing features that are very useful for data transparency between many domains. Those characteristics are also important for the scientific inclusion. The first Case Study approaches the importance of Grid Computing for the collaborative tasks found in the scientific project of the Large Hadron Collider (LHC), which allowed many research institutions and universities around the world to build a shared computational environment of large scale for processing the data generated by LHC. In the environment context, this technology also presents some characteristics to make the computational resources more energy efficient increasing the use of its computational capacities. The second Case Study analyzes the data related to the amount of personal computers connected in the Internet and how to implement Grid Computing based on the Volunteer Computing model to make those computers more productive with no relevant impact in the energy consumption. This research also highlights the synergy between Grid Computing and Cloud Computing, its financial advantages and the generation of new business models based on the commercialization of platform and software as a service in the Internet. The third Case Study analyzes a Cloud Computing model that delivers computational resources (such as a whole server) as a service, enabling a scenario where companies and people could contract a computational environment with a quick provisioning with no need to purchase equipments and to invest in implementation projects. Finally, it is possible to appoint both technologies as relevant trends for the coming years, which can be an influence to generate new software models, platforms and services focused in the Internet / Esta dissertação discute o excesso de recursos computacionais disponíveis mundialmente com capacidade de processamento excedente e também debate como o emprego dos conceitos de compartilhamento e colaboração influenciam a integração desses dispositivos para constituir um ambiente econômico e com alta capacidade de processamento. Atualmente, é possível encontrar uma grande quantidade de computadores pessoais, servidores, entre outros dispositivos, que apresentam elevados níveis de ociosidade. Estes poderiam ser utilizados para outra finalidade, haja vista pesquisas científicas, projetos colaborativos e programas de inclusão digital carentes de recursos para atingirem seus objetivos. A tecnologia de Grid Computing, também chamada de Computação em Grade, foi concebida como uma alternativa para integrar recursos distribuídos geograficamente e pertencentes a diferentes domínios, habilitando um ambiente computacional abrangente e descentralizado. O objetivo desta dissertação é analisar como essa tecnologia, baseada no conceito de colaboração, pode gerar benefícios no contexto social, ambiental e econômico. No âmbito social, Grid Computing estimula o trabalho colaborativo e o compartilhamento de recursos computacionais e aplicacões, além de prover funcionalidades que auxiliam na transparência de dados entre diversos domínios. Essas características também são importantes para a inclusão científica. O primeiro Estudo de Caso aborda a importância de Grid Computing para o projeto científico do Superacelerador de Partículas (LHC). No contexto ambiental, essa tecnologia também apresenta características para tornar os recursos computacionais mais eficientes em relação ao consumo de energia através do aumento do uso de sua capacidade computacional. O segundo Estudo de Caso aborda dados em relação à quantidade de máquinas conectadas à Internet e como uma aplicação de Grid Computing, no modelo de Computação Voluntária, pode tornálas mais produtivas e, consequentemente, mais eficientes no consumo de recursos energéticos. Já no contexto econômico, é de importância destacar a sinergia existente entre Grid Computing e Cloud Computing, as suas vantagens financeiras e a geração de novos modelos de negócios através da comercialização de plataformas e softwares como serviços na Internet, e não mais como produtos. O terceiro Estudo de Caso aborda um modelo de Cloud Computing que disponibiliza recursos computacionais em forma de serviços, permitindo que empresas e pessoas físicas possam contratar um ambiente computacional de rápido provisionamento, sem a necessidade de adquirir equipamentos e investir em projetos de implementação. Por fim, ambas as tecnologias são apontadas como grandes tendências para os próximos anos, as quais influenciarão a geração de novos modelos de softwares, plataformas e serviços voltados à Internet