Computação em nuvem é um novo paradigma, onde recursos computacionais são disponibilizados como serviços. Neste cenário, o usuário não tem a necessidade de adquirir infraestrutura, ele pode alugar os recursos de um provedor e usá-los durante um certo período de tempo. Além disso, o usuário pode facilmente alocar e desalocar quantos recursos ele desejar, num ambiente totalmente elástico. O usuário só é cobrado pelo efetivo uso que for feito dos recursos alocados, isso significa que ele somente pagará pelo que for utilizado. Por outro lado, usuários de processamento de alto desempenho (PAD) tem a necessidade de utilizar grande poder computacional como uma ferramenta de trabalho. Para se ter acesso a estes recursos, são necessários investimentos financeiros adequados para aquisição de sistemas para PAD. Mas, neste caso, duas situações podem incorrer em problemas. O usuário necessita ter acesso aos recursos financeiros totais para adquirir e manter um sistema para PAD, e esses recusros são limitados. O propósito dessa dissertação é avaliar se o paradigma de computação em nuvem é um ambiente viável para PAD, verificando se este modelo de computação tem a capaciodade de prover acesso a ambientes que podem ser utilizados para a execução de aplicações de alto desempenho, e também, se o custo benefício apresentado é melhor do que o de sistemas tradicionais. Para isso, todo o modelo de computação em nuvem foi avaliado para se identificar quais partes dele tem o potencial para ser usado para PAD. Os componentes identificados foram avaliados utilizando-se proeminentes provedores de computação em nuvem. Foram analisadas as capacidades de criação de ambientes de PAD, e tais ambientes tiveram seu desempenho analisado através da utilização de técnicas tradicionais. Para a avaliação do custo benefício, foi criado e aplicado um modelo de custo. Os resultados mostraram que todos os provedores analisados possuem a capacidade de criação de ambientes de PAD. Em termos de desempenho, houveram alguns casos em que os provedores de computação em nuvem foram melhores do que um sistema tradicional. Na perspectiva de custo, a nuvem apresenta uma alternativa bastante interessante devido ao seu modelo de cobrança de acordo com o uso. Como conclusão dessa dissertação, foi mostrado que a computação em nuvem pode ser utilizada como uma alternativa real para ambientes de PAD. / Cloud computing is a new paradigm, where computational resources are offered as services. In this context, the user does not need to buy infrastructure, the resources can be rented from a provider and used for a period of time. Furthermore the user can easily allocate as many resources as needed, and deallocate them as well, in a totally elastic environment. The resources need to be paid only for the effective usage time. On the other hand, High-Performance Computing (HPC) requires a large amount of computational power. To acquire systems capable for HPC, large financial investments are necessary. Apart from the initial investment, the user must pay the maintenance costs, and has only limited computational resources. To overcome these issues, this thesis aims to evaluate the cloud computing paradigm as a candidate environment for HPC. We analyze the efforts and challenges for porting and deploy HPC applications to the cloud. We evaluate if this computing model can provide sufficient capacities for running HPC applications, and compare its cost efficiency to traditional HPC systems, such as clusters. The cloud computing paradigm was analyzed to identify which models have the potential to be used for HPC purposes. The identified models were then evaluated using major cloud providers, Microsoft Windows Azure, Amazon EC2 and Rackspace and compare them to a traditional HPC system. We analyzed the capabilities to create HPC environments, and evaluated their performance. For the evaluation of the cost efficiency, we developed an economic model. The results show that all the evaluated providers have the capability to create HPC environments. In terms of performance, there are some cases where cloud providers present a better performance than the traditional system. From the cost perspective, the cloud presents an interesting alternative due to the pay-per-use model. Summarizing the results, this dissertation shows that cloud computing can be used as a realistic alternative for HPC environments.

Weather forecasting models are computationally intensive applications and traditionally they are executed in parallel machines. However, some issues prevent these models from fully exploiting the available computing power. One of such issues is load imbalance, i.e., the uneven distribution of load across the processors of the parallel machine. Since weather models are typically synchronous applications, that is, all tasks synchronize at every time-step, the execution time is determined by the slowest task. The causes of such imbalance are either static (e.g. topography) or dynamic (e.g. shortwave radiation, moving thunderstorms). Various techniques, often embedded in the application’s source code, have been used to address both sources. However, these techniques are inflexible and hard to use in legacy codes. In this thesis, we explore the concept of processor virtualization for dynamically balancing the load in weather models. This means that the domain is over-decomposed in more tasks than the available processors. Assuming that many tasks can be safely executed in a single processor, each processor is put in charge of a set of tasks. In addition, the system can migrate some of them from overloaded processors to underloaded ones when it detects load imbalance. This approach has the advantage of decoupling the application from the load balancing strategy. Our objective is to show that processor virtualization can be applied to weather models as long as an appropriate strategy for migrations is used. Our proposal takes into account the communication pattern of the application in addition to the load of each processor. In this text, we present the techniques used to minimize the amount of change needed in order to apply processor virtualization to a real-world application. Furthermore, we analyze the effects caused by the frequency at which the load balancer is invoked and a threshold that activates rebalancing. We propose an automatic strategy to find an optimal threshold to trigger load balancing. These strategies are centralized and work well for moderately large machines. For larger machines, we present a fully distributed algorithm and analyze its performance. As a study case, we demonstrate the effectiveness of our approach for dynamically balancing the load in Brams, a mesoscale weather forecasting model based on MPI parallelization. We choose this model because it presents a considerable load imbalance caused by localized thunderstorms. In addition, we analyze how other effects of processor virtualization can improve performance.

Weather forecasting models are computationally intensive applications and traditionally they are executed in parallel machines. However, some issues prevent these models from fully exploiting the available computing power. One of such issues is load imbalance, i.e., the uneven distribution of load across the processors of the parallel machine. Since weather models are typically synchronous applications, that is, all tasks synchronize at every time-step, the execution time is determined by the slowest task. The causes of such imbalance are either static (e.g. topography) or dynamic (e.g. shortwave radiation, moving thunderstorms). Various techniques, often embedded in the application’s source code, have been used to address both sources. However, these techniques are inflexible and hard to use in legacy codes. In this thesis, we explore the concept of processor virtualization for dynamically balancing the load in weather models. This means that the domain is over-decomposed in more tasks than the available processors. Assuming that many tasks can be safely executed in a single processor, each processor is put in charge of a set of tasks. In addition, the system can migrate some of them from overloaded processors to underloaded ones when it detects load imbalance. This approach has the advantage of decoupling the application from the load balancing strategy. Our objective is to show that processor virtualization can be applied to weather models as long as an appropriate strategy for migrations is used. Our proposal takes into account the communication pattern of the application in addition to the load of each processor. In this text, we present the techniques used to minimize the amount of change needed in order to apply processor virtualization to a real-world application. Furthermore, we analyze the effects caused by the frequency at which the load balancer is invoked and a threshold that activates rebalancing. We propose an automatic strategy to find an optimal threshold to trigger load balancing. These strategies are centralized and work well for moderately large machines. For larger machines, we present a fully distributed algorithm and analyze its performance. As a study case, we demonstrate the effectiveness of our approach for dynamically balancing the load in Brams, a mesoscale weather forecasting model based on MPI parallelization. We choose this model because it presents a considerable load imbalance caused by localized thunderstorms. In addition, we analyze how other effects of processor virtualization can improve performance.

Computação em nuvem é um novo paradigma, onde recursos computacionais são disponibilizados como serviços. Neste cenário, o usuário não tem a necessidade de adquirir infraestrutura, ele pode alugar os recursos de um provedor e usá-los durante um certo período de tempo. Além disso, o usuário pode facilmente alocar e desalocar quantos recursos ele desejar, num ambiente totalmente elástico. O usuário só é cobrado pelo efetivo uso que for feito dos recursos alocados, isso significa que ele somente pagará pelo que for utilizado. Por outro lado, usuários de processamento de alto desempenho (PAD) tem a necessidade de utilizar grande poder computacional como uma ferramenta de trabalho. Para se ter acesso a estes recursos, são necessários investimentos financeiros adequados para aquisição de sistemas para PAD. Mas, neste caso, duas situações podem incorrer em problemas. O usuário necessita ter acesso aos recursos financeiros totais para adquirir e manter um sistema para PAD, e esses recusros são limitados. O propósito dessa dissertação é avaliar se o paradigma de computação em nuvem é um ambiente viável para PAD, verificando se este modelo de computação tem a capaciodade de prover acesso a ambientes que podem ser utilizados para a execução de aplicações de alto desempenho, e também, se o custo benefício apresentado é melhor do que o de sistemas tradicionais. Para isso, todo o modelo de computação em nuvem foi avaliado para se identificar quais partes dele tem o potencial para ser usado para PAD. Os componentes identificados foram avaliados utilizando-se proeminentes provedores de computação em nuvem. Foram analisadas as capacidades de criação de ambientes de PAD, e tais ambientes tiveram seu desempenho analisado através da utilização de técnicas tradicionais. Para a avaliação do custo benefício, foi criado e aplicado um modelo de custo. Os resultados mostraram que todos os provedores analisados possuem a capacidade de criação de ambientes de PAD. Em termos de desempenho, houveram alguns casos em que os provedores de computação em nuvem foram melhores do que um sistema tradicional. Na perspectiva de custo, a nuvem apresenta uma alternativa bastante interessante devido ao seu modelo de cobrança de acordo com o uso. Como conclusão dessa dissertação, foi mostrado que a computação em nuvem pode ser utilizada como uma alternativa real para ambientes de PAD. / Cloud computing is a new paradigm, where computational resources are offered as services. In this context, the user does not need to buy infrastructure, the resources can be rented from a provider and used for a period of time. Furthermore the user can easily allocate as many resources as needed, and deallocate them as well, in a totally elastic environment. The resources need to be paid only for the effective usage time. On the other hand, High-Performance Computing (HPC) requires a large amount of computational power. To acquire systems capable for HPC, large financial investments are necessary. Apart from the initial investment, the user must pay the maintenance costs, and has only limited computational resources. To overcome these issues, this thesis aims to evaluate the cloud computing paradigm as a candidate environment for HPC. We analyze the efforts and challenges for porting and deploy HPC applications to the cloud. We evaluate if this computing model can provide sufficient capacities for running HPC applications, and compare its cost efficiency to traditional HPC systems, such as clusters. The cloud computing paradigm was analyzed to identify which models have the potential to be used for HPC purposes. The identified models were then evaluated using major cloud providers, Microsoft Windows Azure, Amazon EC2 and Rackspace and compare them to a traditional HPC system. We analyzed the capabilities to create HPC environments, and evaluated their performance. For the evaluation of the cost efficiency, we developed an economic model. The results show that all the evaluated providers have the capability to create HPC environments. In terms of performance, there are some cases where cloud providers present a better performance than the traditional system. From the cost perspective, the cloud presents an interesting alternative due to the pay-per-use model. Summarizing the results, this dissertation shows that cloud computing can be used as a realistic alternative for HPC environments.

A Dinâmica de Fluidos Computacional é uma importante área de pesquisa no contexto da Computação Científica. Através da modelagem e simulação das propriedades de líquidos e gases é possível obter resultados numéricos para diferentes estruturas e fenômenos físicos cotidianos e de grande importância econômica. A evolução dos sistemas computacionais possibilitou a essa área o surgimento de novas técnicas e abordagens de simulação. Uma das técnicas computacionais atualmente empregadas é o Método de Lattice Boltzmann, um método numérico iterativo para a modelagem e simulação mesoscópica da dinâmica de fluxos de fluidos. Diferentes tipos de sistemas físicos podem ser tratados através dessa técnica, como é o caso de fluxos em meios porosos ou de substâncias imiscíveis. No entanto, por causa da dimensão dos sistemas físicos, é necessário adotar estratégias que permitam a obtenção de resultados precisos ou em tempos computacionais aceitáveis. Assim, paralelizar as operações é a solução mais indicada para aumentar o desempenho do método. Uma maneira eficiente de paralelizar um método numérico é fazer uso de técnicas de distribuição de dados refinadas, como é o caso do particionamento em blocos. Tais abordagens de paralelização foram adotadas neste trabalho em implementações bi- e tridimensionais do Método de Lattice Boltzmann, com o intuito de avaliar o ganho de desempenho oferecido através dessa técnica. Além disso, foram definidos os fatores que influenciam as melhores configurações de particionamento. Os resultados obtidos demonstraram que o particionamento em blocos prove um aumento considerável do desempenho das aplicações paralelas, especialmente para a versão tridimensional do método. Para algumas configurações dos estudos de caso os tempos de execução diminuíram em até 30% em relação aos tempos obtidos com o particionamento unidimensional. Já as melhores configurações para a distribuição dos dados em blocos foram aquelas em que a disposição dos dados manteve-se mais quadrada ou cúbica em relação a cada uma das dimensões coordenadas. / Computational Fluid Dynamics is an important research area in the Scientific Computing context. Through the modeling and simulation of liquids and gases properties it is possible to get numerical results for different physical structures and daily phenomena that have great economic importance. The evolution of the computational systems made it possible to develop new techniques and approaches of simulation in this area. One of these techniques currently used is the Lattice Boltzmann Method. This method is an iterative numerical strategy for modeling and simulating mesoscopic dynamics of fluid flows. Different types of physical systems can be simulated through this technique, like immiscible substances and flows in porous media. However, since the dimension of the physical systems is usually large, it is necessary to adopt strategies that allow to get accurate results or results in an acceptable computational time. Thus, the parallelization of the operations is the best alternative to increase the performance of the method. An efficient way to parallelize a numerical method is to make use of refined data distribution techniques, like data partitioning in blocks. Such parallelization approach had been adopted in this work for bi- and three-dimensional implementations of the Lattice Boltzmann Method. The objective of the work was to evaluate the performance enhancement offered through the parallelization. Moreover, another objective is to define the elements that influence the best partitioning configurations. The results shown that data partitioning in blocks provide a considerable performance increase for parallel implementations, especially for the three-dimensional version of the method. For some configurations adopted in the case studies, the execution time was reduced of up to 30% in relation to the one-dimensional partitioning strategy. The best configurations for data distribution in blocks were that where the data disposal are more square or cubical shaped in relation to each one of the coordinate dimensions

O aumento crescente no número de processadores das arquiteturas paralelas que estão no topo dos rankings de desempenho, apesar de permitir uma maior capacidade de processamento, também traz consigo um aumento na taxa de falhas diretamente proporcional ao número de processadores. Atualmente, as técnicas de tolerância a falhas com recuperação retroativa são as mais empregadas em aplicações MPI, principalmente a técnica de checkpoint coordenado. No entanto, previsões afirmam que essa última técnica será inadequada para as arquiteturas emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho da comunicação MPI sobre Publish/Subscriber no qual se baseia o log de mensagens. O trabalho compreende: um estudo das técnicas de tolerância a falhas mais empregadas em ambientes de alto desempenho e a motivação para a escolha dessa variante de log de mensagens; a proposta de log de mensagens; uma implementação de comunicação Open MPI sobre OpenAMQ e sua respectiva avaliação de desempenho com comunicação tradicional TCP/IP e com o log de mensagens pessimista local da distribuição do Open MPI. Os benchmarks utilizados foram o NetPIPE, o NAS Parallel Benchmarks e a aplicação Virginia Hydrodynamics (VH-1). / The growing number of processors in parallel architectures at the top of performance rankings allows a higher processing capacity. However, it also brings an increase in the fault rate which is directly proportional to the number of processors. Nowadays, coordinated checkpoint is the most widely used rollback technique for system recovery in the occurrence of faults in MPI applications. Nevertheless, projections point that this technique will be inappropriate for the emerging architectures. On the other hand, message logging seems to be more appropriate to this new scenario. This work consists in a proposal of pessimistic message logging (remote based) with non-coordinated checkpoint and the performance evaluation of an MPI communication mechanism that works over Publish/Subscriber channels in which the proposed message logging is based. The work is organized as following: an study of fault tolerant techniques used in HPC and the motivation for choosing this variant of message logging; a message logging proposal; an implementation of Open MPI communication over OpenAMQ; performance evaluation and comparision with the tradicional TCP/IP communication and a pessimistic message logging (sender based) from Open MPI distribution. The benchmark set is composed of NetPIPE, NAS Parallel Benchmarks and Virginia Hydrodynamics (VH-1).

Atualmente, o computador pessoal (PC) moderno poder ser considerado como um cluster heterogênedo de um nodo, o qual processa simultâneamente inúmeras tarefas provenientes das aplicações. O PC pode ser composto por Unidades de Processamento (PUs) assimétricas, como a Unidade Central de Processamento (CPU), composta de múltiplos núcleos, a Unidade de Processamento Gráfico (GPU), composta por inúmeros núcleos e que tem sido um dos principais co-processadores que contribuiram para a computação de alto desempenho em PCs, entre outras. Neste sentido, uma plataforma de execução heterogênea é formada em um PC para efetuar cálculos intensivos em um grande número de dados. Na perspectiva desta tese, a distribuição da carga de trabalho de uma aplicação nas PUs é um fator importante para melhorar o desempenho das aplicações e explorar tal heterogeneidade. Esta questão apresenta desafios uma vez que o custo de execução de uma tarefa de alto nível em uma PU é não-determinístico e pode ser afetado por uma série de parâmetros não conhecidos a priori, como o tamanho do domínio do problema e a precisão da solução, entre outros. Nesse escopo, esta pesquisa de doutorado apresenta um sistema sensível ao contexto e de adaptação em tempo de execução com base em um compromisso entre a redução do tempo de execução das aplicações - devido a um escalonamento dinâmico adequado de tarefas de alto nível - e o custo de computação do próprio escalonamento aplicados em uma plataforma composta de CPU e GPU. Esta abordagem combina um modelo para um primeiro escalonamento baseado em perfis de desempenho adquiridos em préprocessamento com um modelo online, o qual mantém o controle do tempo de execução real de novas tarefas e escalona dinâmicamente e de modo eficaz novas instâncias das tarefas de alto nível em uma plataforma de execução composta de CPU e de GPU. Para isso, é proposto um conjunto de heurísticas para escalonar tarefas em uma CPU e uma GPU e uma estratégia genérica e eficiente de escalonamento que considera várias unidades de processamento. A abordagem proposta é aplicada em um estudo de caso utilizando uma plataforma de execução composta por CPU e GPU para computação de métodos iterativos focados na solução de Sistemas de Equações Lineares que se utilizam de um cálculo de stencil especialmente concebido para explorar as características das GPUs modernas. A solução utiliza o número de incógnitas como o principal parâmetro para a decisão de escalonamento. Ao escalonar tarefas para a CPU e para a GPU, um ganho de 21,77% em desempenho é obtido em comparação com o escalonamento estático de todas as tarefas para a GPU (o qual é utilizado por modelos de programação atuais, como OpenCL e CUDA para Nvidia) com um erro de escalonamento de apenas 0,25% em relação à combinação exaustiva. / A modern personal computer can be now considered as a one-node heterogeneous cluster that simultaneously processes several applications’ tasks. It can be composed by asymmetric Processing Units (PUs), like the multi-core Central Processing Unit (CPU), the many-core Graphics Processing Units (GPUs) - which have become one of the main co-processors that contributed towards high performance computing - and other PUs. This way, a powerful heterogeneous execution platform is built on a desktop for data intensive calculations. In the perspective of this thesis, to improve the performance of applications and explore such heterogeneity, a workload distribution over the PUs plays a key role in such systems. This issue presents challenges since the execution cost of a task at a PU is non-deterministic and can be affected by a number of parameters not known a priori, like the problem size domain and the precision of the solution, among others. Within this scope, this doctoral research introduces a context-aware runtime and performance tuning system based on a compromise between reducing the execution time of the applications - due to appropriate dynamic scheduling of high-level tasks - and the cost of computing such scheduling applied on a platform composed of CPU and GPUs. This approach combines a model for a first scheduling based on an off-line task performance profile benchmark with a runtime model that keeps track of the tasks’ real execution time and efficiently schedules new instances of the high-level tasks dynamically over the CPU/GPU execution platform. For that, it is proposed a set of heuristics to schedule tasks over one CPU and one GPU and a generic and efficient scheduling strategy that considers several processing units. The proposed approach is applied in a case study using a CPU-GPU execution platform for computing iterative solvers for Systems of Linear Equations using a stencil code specially designed to explore the characteristics of modern GPUs. The solution uses the number of unknowns as the main parameter for assignment decision. By scheduling tasks to the CPU and to the GPU, it is achieved a performance gain of 21.77% in comparison to the static assignment of all tasks to the GPU (which is done by current programming models, such as OpenCL and CUDA for Nvidia) with a scheduling error of only 0.25% compared to exhaustive search.

Previsões meteorológicas para longos períodos de tempo estão se tornando cada vez mais importantes. A preocupação mundial com as consequências da mudança do clima tem estimulado pesquisas para determinar o seu comportamento nas próximas décadas. Ao mesmo tempo, os passos necessários para definir uma melhor modelagem e simulação do clima e/ou tempo estão longe da precisão desejada. Aumentar o refinamento da superfície terrestre e, consequentemente, aumentar o número de pontos discretos (utilizados para a representação da atmosfera) na modelagem climática e precisão das soluções computadas é uma meta que está em conflito com o desempenho das aplicações numéricas. Aplicações que envolvem a interação de longos períodos de tempo e incluem um grande número de operações possuem um tempo de execução inviável para as arquiteturas de computadores tradicionais. Para superar esta situação, um modelo climatológico pode adotar diferentes níveis de refinamento da superfície terrestre, utilizando mais pontos discretos somente em regiões onde uma maior precisão é requerida. Este é o caso de Ocean-Land-AtmosphereModel, que permite o refinamento estático de uma determinada região no início da execução do código. No entanto, um refinamento dinâmico possibilitaria uma melhor compreensão das condições climáticas específicas de qualquer região da superfície terrestre que se tivesse interesse, sem a necessidade de reiniciar a execução da aplicação. Com o surgimento das arquiteturas multi-core e a adoção de GPUs para a computação de propósito geral, existem diferentes níveis de paralelismo. Hoje há paralelismo interno ao processador, entre processadores e entre computadores. Com o objetivo de extrair ao máximo a performance dos computadores atuais, é necessário utilizar todos os níveis de paralelismo disponíveis durante o desenvolvimento de aplicações concorrentes. No entanto, nenhuma interface de programação paralela explora simultaneamente bem os diferentes níveis de paralelismo existentes. Baseado neste contexto, esta tese investiga como explorar diferentes níveis de paralelismo em modelos climatológicos usando interfaces clássicas de programação paralela de forma combinada e como é possível prover refinamento de malhas em tempo de execução para estes modelos. Os resultados obtidos a partir de implementações realizadas mostraram que é possível reduzir o tempo de execução de uma simulação atmosférica utilizando diferentes níveis de paralelismo, através do uso combinado de interfaces de programação paralela. Além disso, foi possível prover maior desempenho na execução de aplicações climatológicas que utilizam refinamento de malhas em tempo de execução. Com isso, uma malha de maior resolução para a representação da atmosfera terrestre pode ser adotada e, consequentemente, as previsões numéricas serão mais precisas. / Weather forecasts for long periods of time has emerged as increasingly important. The global concern with the consequences of climate changes has stimulated researches to determine the climate in coming decades. At the same time the steps needed to better defining the modeling and the simulation of climate/weather is far of the desired accuracy. Upscaling the land surface and consequently to increase the number of points used in climate modeling and the precision of the computed solutions is a goal that conflicts with the performance of numerical applications. Applications that include the interaction of long periods of time and involve a large number of operations become the expectation for results infeasible in traditional computers. To overcome this situation, a climatic model can take different levels of refinement of the Earth’s surface, using more discretized elements only in regions where more precision are required. This is the case of Ocean-Land- Atmosphere Model, which allows the static refinement of a particular region of the Earth in the early execution of the code. However, a dynamic mesh refinement could allow to better understand specific climatic conditions that appear at execution time of any region of the Earth’s surface, without restarting execution. With the introduction of multi-core processors and GPU boards, computers architectures have many parallel layers. Today, there are parallelism inside the processor, among processors and among computers. In order to use the best performance of the computers it is necessary to consider all parallel levels to distribute a concurrent application. However, nothing parallel programming interface abstracts all these different parallel levels. Based in this context, this thesis investigates how to explore different levels of parallelism in climatological models using mixed interfaces of parallel programming and how these models can provide mesh refinement at execution time. The performance results show that is possible to reduce the execution time of atmospheric simulations using different levels of parallelism, through the combined use of parallel programming interfaces. Higher performance for the execution of atmospheric applications that use online mesh refinement was also provided. Therefore, more mesh resolution to describe the Earth’s atmosphere can be adopted, and consequently the numerical forecasts are more accurate.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.