Um ambiente de programação é uma ferramenta de software resultante da associa ção de um modelo de programação a um sistema de execução. O objetivo de um ambiente de programação é simpli car o desenvolvimento e a execução de aplicações em uma determinada infra-estrutura computacional. Uma infra-estrutura de Computa ção em Grade apresenta características peculiares que tornam pouco e cientes ambientes de programação existentes para infra-estruturas mais tradicionais, como máquinas maciçamente paralelas ou clusters de computadores. Este trabalho apresenta o WSPE, um ambiente de programação peer-to-peer para Computação em Grade. O WSPE oferece suporte para aplicações grid-unaware que seguem o modelo de programação de tarefas paralelas. A interface de programação WSPE é de nida através de anotações da linguagem Java. O sistema de execu- ção segue um modelo peer-to-peer totalmente descentralizado com o propósito de obter robustez e escalabilidade. Embora um sistema de execução necessite abordar diversos aspectos para se tornar completo, a concepção do sistema de execução WSPE aborda aspectos de desempenho, portabilidade, escalabilidade e adaptabilidade. Para tanto foram desenvolvidos ou adaptados mecanismos para as funções de escalonamento, de construção da rede de sobreposição e de suporte ao paralelismo adaptativo. O mecanismo de escalonamento empregado pelo sistema de execução WSPE é baseado na idéia de roubo de trabalho e utiliza uma nova estratégia que resulta em uma e ciência até cinco vezes superior quando comparada com uma estrat égia mais tradicional. Experimentos realizados com um protótipo do WSPE e também por simulação demonstram a viabilidade do ambiente de programação proposto. / A programming environment is a software tool resulting from the association of a programming model to a runtime system. The goal of a programming environment is to simplify application development and execution on a given computational infrastructure. A Grid Computing infrastructure presents peculiar characteristics that make less e cient existing programming environments designed for more traditional infrastructures, such as massively parallel machines or clusters of computers. This work presents WSPE, a peer-to-peer programming environment for Grid Computing. WSPE provides support for grid-unaware applications following the task parallelism programming model. WSPE programming interface is de ned using annotations from the Java language. The runtime system follows a fully decentralized peer-to-peer model. Although several aspects must be considered in order for a runtime system to become complete, WSPE runtime system's conception considers only performance, portability, scalability and adaptability. For this purpose, mechanisms have been developed or adapted to handle scheduling, overlay network building and adaptive parallelism support functions. The scheduling mechanism employed by WSPE's runtime system is based on the idea of work stealing and uses a new strategy resulting on four times higher e ciency when compared to a more traditional strategy. Conducted experiments with WSPE's prototype and also using a simulation tool demonstrate the proposed programming environment feasibility.

Nos últimos anos, uma das alternativas adotadas para aumentar o desempenho de sistemas de processamento de alto desempenho têm sido o uso de arquiteturas híbridas. Essas arquiteturas são constituídas de processadores multicore e coprocessadores especializados, como GPUs. Esses coprocessadores atuam como aceleradores em alguns tipos de operações. Por outro lado, as ferramentas e modelos de programação paralela atuais não são adequados para cenários híbridos, produzindo aplicações pouco portáveis. O paralelismo de tarefas considerado um paradigma de programação genérico e de alto nível pode ser adotado neste cenário. Porém, exige o uso de algoritmos de escalonamento dinâmicos, como o algoritmo de roubo de tarefas. Neste contexto, este trabalho apresenta um middleware (WORMS) que oferece suporte ao paralelismo de tarefas com escalonamento por roubo de tarefas em sistemas híbridos multi-CPU e multi-GPU. Esse middleware permite que as tarefas tenham implementação tanto para execução em CPUs quanto em GPUs, decidindo em tempo de execução qual das implementações será executada de acordo com os recursos de hardware disponíveis. Os resultados obtidos com o WORMS mostram ser possível superar, em algumas aplicações, tanto o desempenho de ferramentas de referência para execução em CPU quanto de ferramentas para execução em GPUs. / In the last years, one of alternatives adopted to increase performance in high performance computing systems have been the use of hybrid architectures. These architectures consist of multicore processors and specialized coprocessors, like GPUs. Coprocessors act as accelerators in some types of operations. On the other hand, current parallel programming models and tools are not suitable for hybrid scenarios, generating less portable applications. Task parallelism, considered a generic and high level programming paradigm, can be used in this scenario. However, it requires the use of dynamic scheduling algorithms, such as work stealing. In this context, this work presents a middleware (WORMS) that supports task parallelism with work stealing scheduling in multi-CPU and multi-GPU systems. This middleware allows task implementations for both CPU and GPU, deciding at runtime which implementation will run according to the available hardware resources. The performance results obtained with WORMS showed that is possible to outperform both CPU and GPU reference tools in some applications.

No description available.

Um ambiente de programação é uma ferramenta de software resultante da associa ção de um modelo de programação a um sistema de execução. O objetivo de um ambiente de programação é simpli car o desenvolvimento e a execução de aplicações em uma determinada infra-estrutura computacional. Uma infra-estrutura de Computa ção em Grade apresenta características peculiares que tornam pouco e cientes ambientes de programação existentes para infra-estruturas mais tradicionais, como máquinas maciçamente paralelas ou clusters de computadores. Este trabalho apresenta o WSPE, um ambiente de programação peer-to-peer para Computação em Grade. O WSPE oferece suporte para aplicações grid-unaware que seguem o modelo de programação de tarefas paralelas. A interface de programação WSPE é de nida através de anotações da linguagem Java. O sistema de execu- ção segue um modelo peer-to-peer totalmente descentralizado com o propósito de obter robustez e escalabilidade. Embora um sistema de execução necessite abordar diversos aspectos para se tornar completo, a concepção do sistema de execução WSPE aborda aspectos de desempenho, portabilidade, escalabilidade e adaptabilidade. Para tanto foram desenvolvidos ou adaptados mecanismos para as funções de escalonamento, de construção da rede de sobreposição e de suporte ao paralelismo adaptativo. O mecanismo de escalonamento empregado pelo sistema de execução WSPE é baseado na idéia de roubo de trabalho e utiliza uma nova estratégia que resulta em uma e ciência até cinco vezes superior quando comparada com uma estrat égia mais tradicional. Experimentos realizados com um protótipo do WSPE e também por simulação demonstram a viabilidade do ambiente de programação proposto. / A programming environment is a software tool resulting from the association of a programming model to a runtime system. The goal of a programming environment is to simplify application development and execution on a given computational infrastructure. A Grid Computing infrastructure presents peculiar characteristics that make less e cient existing programming environments designed for more traditional infrastructures, such as massively parallel machines or clusters of computers. This work presents WSPE, a peer-to-peer programming environment for Grid Computing. WSPE provides support for grid-unaware applications following the task parallelism programming model. WSPE programming interface is de ned using annotations from the Java language. The runtime system follows a fully decentralized peer-to-peer model. Although several aspects must be considered in order for a runtime system to become complete, WSPE runtime system's conception considers only performance, portability, scalability and adaptability. For this purpose, mechanisms have been developed or adapted to handle scheduling, overlay network building and adaptive parallelism support functions. The scheduling mechanism employed by WSPE's runtime system is based on the idea of work stealing and uses a new strategy resulting on four times higher e ciency when compared to a more traditional strategy. Conducted experiments with WSPE's prototype and also using a simulation tool demonstrate the proposed programming environment feasibility.

Nos últimos anos, uma das alternativas adotadas para aumentar o desempenho de sistemas de processamento de alto desempenho têm sido o uso de arquiteturas híbridas. Essas arquiteturas são constituídas de processadores multicore e coprocessadores especializados, como GPUs. Esses coprocessadores atuam como aceleradores em alguns tipos de operações. Por outro lado, as ferramentas e modelos de programação paralela atuais não são adequados para cenários híbridos, produzindo aplicações pouco portáveis. O paralelismo de tarefas considerado um paradigma de programação genérico e de alto nível pode ser adotado neste cenário. Porém, exige o uso de algoritmos de escalonamento dinâmicos, como o algoritmo de roubo de tarefas. Neste contexto, este trabalho apresenta um middleware (WORMS) que oferece suporte ao paralelismo de tarefas com escalonamento por roubo de tarefas em sistemas híbridos multi-CPU e multi-GPU. Esse middleware permite que as tarefas tenham implementação tanto para execução em CPUs quanto em GPUs, decidindo em tempo de execução qual das implementações será executada de acordo com os recursos de hardware disponíveis. Os resultados obtidos com o WORMS mostram ser possível superar, em algumas aplicações, tanto o desempenho de ferramentas de referência para execução em CPU quanto de ferramentas para execução em GPUs. / In the last years, one of alternatives adopted to increase performance in high performance computing systems have been the use of hybrid architectures. These architectures consist of multicore processors and specialized coprocessors, like GPUs. Coprocessors act as accelerators in some types of operations. On the other hand, current parallel programming models and tools are not suitable for hybrid scenarios, generating less portable applications. Task parallelism, considered a generic and high level programming paradigm, can be used in this scenario. However, it requires the use of dynamic scheduling algorithms, such as work stealing. In this context, this work presents a middleware (WORMS) that supports task parallelism with work stealing scheduling in multi-CPU and multi-GPU systems. This middleware allows task implementations for both CPU and GPU, deciding at runtime which implementation will run according to the available hardware resources. The performance results obtained with WORMS showed that is possible to outperform both CPU and GPU reference tools in some applications.

Um ambiente de programação é uma ferramenta de software resultante da associa ção de um modelo de programação a um sistema de execução. O objetivo de um ambiente de programação é simpli car o desenvolvimento e a execução de aplicações em uma determinada infra-estrutura computacional. Uma infra-estrutura de Computa ção em Grade apresenta características peculiares que tornam pouco e cientes ambientes de programação existentes para infra-estruturas mais tradicionais, como máquinas maciçamente paralelas ou clusters de computadores. Este trabalho apresenta o WSPE, um ambiente de programação peer-to-peer para Computação em Grade. O WSPE oferece suporte para aplicações grid-unaware que seguem o modelo de programação de tarefas paralelas. A interface de programação WSPE é de nida através de anotações da linguagem Java. O sistema de execu- ção segue um modelo peer-to-peer totalmente descentralizado com o propósito de obter robustez e escalabilidade. Embora um sistema de execução necessite abordar diversos aspectos para se tornar completo, a concepção do sistema de execução WSPE aborda aspectos de desempenho, portabilidade, escalabilidade e adaptabilidade. Para tanto foram desenvolvidos ou adaptados mecanismos para as funções de escalonamento, de construção da rede de sobreposição e de suporte ao paralelismo adaptativo. O mecanismo de escalonamento empregado pelo sistema de execução WSPE é baseado na idéia de roubo de trabalho e utiliza uma nova estratégia que resulta em uma e ciência até cinco vezes superior quando comparada com uma estrat égia mais tradicional. Experimentos realizados com um protótipo do WSPE e também por simulação demonstram a viabilidade do ambiente de programação proposto. / A programming environment is a software tool resulting from the association of a programming model to a runtime system. The goal of a programming environment is to simplify application development and execution on a given computational infrastructure. A Grid Computing infrastructure presents peculiar characteristics that make less e cient existing programming environments designed for more traditional infrastructures, such as massively parallel machines or clusters of computers. This work presents WSPE, a peer-to-peer programming environment for Grid Computing. WSPE provides support for grid-unaware applications following the task parallelism programming model. WSPE programming interface is de ned using annotations from the Java language. The runtime system follows a fully decentralized peer-to-peer model. Although several aspects must be considered in order for a runtime system to become complete, WSPE runtime system's conception considers only performance, portability, scalability and adaptability. For this purpose, mechanisms have been developed or adapted to handle scheduling, overlay network building and adaptive parallelism support functions. The scheduling mechanism employed by WSPE's runtime system is based on the idea of work stealing and uses a new strategy resulting on four times higher e ciency when compared to a more traditional strategy. Conducted experiments with WSPE's prototype and also using a simulation tool demonstrate the proposed programming environment feasibility.

This thesis studies the area of virtualization. The focus is on the sub-area live migration, a technique that allows a seamless migration of a virtual machine from one physical machine to another physical machine. Virtualization is an attractive technique, utilized in large computer systems, for example data centers. By using live migration, data center administrators can migrate virtual machines, seamlessly, without the users of the virtual machines taking notice about the migrations. Manually initiated migrations can become cumbersome, with an ever-increasing number of physical machines. The number of physical and virtual machines is not the only problem, deciding when to migrate and where to migrate are other problems that needs to be solved. Manually initiated migrations can also be inaccurate and untimely. Two different strategies for automated live migration have been developed in this thesis. The Push and the Pull strategies. The Push strategy tries to get rid of virtual machines and the Pull strategy tries to steal virtual machines. Both of these strategies, their design and implementation, are presented in the thesis. The strategies utilizes Shannon's Information Entropy to measure the balance in the system. The strategies further utilizes a cost model to predict the time a migration would require. This is used together with the Information Entropy to decide which virtual machine to migrate if and when a hotspot occurs. The implementation was done with the help of OMNeT++, an open-source simulation tool. The strategies are evaluated with the help of a set of simulations. These simulations include a variety of scenarios with different workloads. Our results shows that the developed strategies can re-balance a system of computers, after a large amount of virtual machines has been added or removed, in only 4-5 minutes. The results further shows that our strategies are able to keep the system balanced when the system load is at medium. This while virtual machines are continuously added or removed from the system. The contribution this thesis brings to the field is a model for how automated live migration of virtual machines can be done to improve the performance of a computer system, for example a data center.

This report investigates the rural inter-communal conflict as a threat to community livelihood in Jonglei State, one of the ten states in South Sudan. Jonglei State has a long history of unrest, which has also affected other parts of the country. Cattle raiding and conflict have manifested in Jonglei State and the surrounding communities for many years. Many people have lost their lives, and livestock losses have been abundant. It is vital that local government understands and contextualises these challenges so that appropriate interventions may be developed. This study proposes to provide a brief historical background on the evolution of inter-communal conflict in Jonglei. There have been recent changes in the security situation and increased access to weapons. Advanced weaponry has also led to a rise in insecurity and increases in the number and scale of cattle raids. Political tensions and political instability have also emerged. The political situation is unstable and political factions are in constant disagreement. Furthermore, there are limited economic opportunities there is also limited access to natural resources such as water and grazing land for cattle. Climate conditions and migration patterns are also discussed and explained. The cross sectional descriptive survey was used in this study. Various recommendations flowing from the results of the study are proposed in the final chapter. If adopted, these recommendations could enable the Government of South Sudan and the residents of Jonglei to overcome inter-communal conflict.

No description available.

Nous présentons deux contributions dans le domaine de la programmation parallèle. La première est théorique : nous introduisons l’analyse SIPS, une approche nouvelle pour dénombrer le nombre d’opérations de synchronisation durant l’exécution d’un algorithme parallèle ordonnancé par vol de travail. Basée sur le concept d’horloges logiques, elle nous permet : d’une part de donner de nouvelles majorations de coût en moyenne; d’autre part de concevoir des programmes parallèles plus efficaces par adaptation dynamique de la granularité. La seconde contribution est pragmatique : nous présentons une parallélisation générique d’algorithmes pour la génération déterministe de nombres pseudo-aléatoires, indépendamment du nombre de processus concurrents lors de l’exécution. Alternative à l’utilisation d’un générateur pseudo-aléatoire séquentiel par processus, nous introduisons une API générique, appelée Par-R qui est conçue et analysée grâce à SIPS. Sa caractéristique principale est d’exploiter un générateur séquentiel qui peut “sauter” directement d’un nombre à un autre situé à une distance arbitraire dans la séquence pseudo-aléatoire. Grâce à l’analyse SIPS, nous montrons qu’en moyenne, lors d’une exécution par vol de travail d’un programme très parallèle (dont la profondeur ou chemin critique est très petite devant le travail ou nombre d’opérations), ces opérations de saut sont rares. Par-R est comparé au générateur pseudo-aléatoire DotMix écrit pour Cilk Plus, une extension de C/C++ pour la programmation parallèle par vol de travail. Le surcout théorique de Par-R se compare favorablement au surcoput de DotMix, ce qui apparait aussi expériemntalement. De plus, étant générique, Par-R est indépendant du générateur séquentiel sous-jacent. / Nós apresentamos duas contribuições para a área de programação paralela. A primeira contribuição é teórica: nós introduzimos a análise SIPS, uma nova abordagem para a estimar o número de sincronizações realizadas durante a execução de um algoritmo paralelo. SIPS generaliza o conceito de relógios lógicos para contar o número de sincronizações realizadas por um algoritmo paralelo e é capaz de calcular limites do pior caso mesmo na presença de execuções paralelas não-determinísticas, as quais não são geralmente cobertas por análises no estado-da-arte. Nossa análise nos permite estimar novos limites de pior caso para computações escalonadas pelo popular algoritmo de roubo de tarefas e também projetar programas paralelos e adaptáveis que são mais eficientes. A segunda contribuição é pragmática: nós apresentamos uma estratégia de paralelização eficiente para a geração de números pseudoaleatórios. Como uma alternativa para implementações fixas de componentes de geração aleatória nós introduzimos uma API chamada Par-R, projetada e analisada utilizando-se SIPS. Sua principal idea é o uso da capacidade de um gerador sequencial R de realizar um “pulo” eficiente dentro do fluxo de números gerados; nós os associamos a operações realizadas pelo escalonador por roubo de tarefas, o qual nossa análise baseada em SIPS demonstra ocorrer raramente em média. Par-R é comparado com o gerador paralelo de números pseudoaleatórios DotMix, escrito para a plataforma de multithreading dinâmico Cilk Plus. A latência de Par-R tem comparação favorável à latência do DotMix, o que é confirmado experimentalmente, mas não requer o uso subjacente fixado de um dado gerador aleatório. / We present two contributions to the field of parallel programming. The first contribution is theoretical: we introduce SIPS analysis, a novel approach to estimate the number of synchronizations performed during the execution of a parallel algorithm. Based on the concept of logical clocks, it allows us: on one hand, to deliver new bounds for the number of synchronizations, in expectation; on the other hand, to design more efficient parallel programs by dynamic adaptation of the granularity. The second contribution is pragmatic: we present an efficient parallelization strategy for pseudorandom number generation, independent of the number of concurrent processes participating in a computation. As an alternative to the use of one sequential generator per process, we introduce a generic API called Par-R, which is designed and analyzed using SIPS. Its main characteristic is the use of a sequential generator that can perform a “jump-ahead” directly from one number to another on an arbitrary distance within the pseudorandom sequence. Thanks to SIPS, we show that, in expectation, within an execution scheduled by work stealing of a “very parallel” program (whose depth or critical path is subtle when compared to the work or number of operations), these operations are rare. Par-R is compared with the parallel pseudorandom number generator DotMix, written for the Cilk Plus dynamic multithreading platform. The theoretical overhead of Par-R compares favorably to DotMix’s overhead, what is confirmed experimentally, while not requiring a fixed generator underneath.