abstract: Process migration is a heavily studied research area and has a number of applications in distributed systems. Process migration means transferring a process running on one machine to another such that it resumes execution from the point at which it was suspended. The conventional approach to implement process migration is to move the entire state information of the process (including hardware context, virtual memory, files etc.) from one machine to another. Copying all the state information is costly. This thesis proposes and demonstrates a new approach of migrating a process between two cores of Intel Single Chip Cloud (SCC), an experimental 48-core processor by Intel, with each core running a separate instance of the operating system. In this method the amount of process state to be transferred from one core's memory to another is reduced by making use of special registers called Lookup tables (LUTs) present on each core of SCC. Thus this new approach is faster than the conventional method. / Dissertation/Thesis / M.S. Computer Science 2013

Este trabalho apresenta o projeto e a implementação da política de escalonamento com suporte à migração de processos JUMP. A migração de processos é uma ferramenta importante que complementa a alocação inicial realizada pela política de escalonamento em um ambiente paralelo distribuído, permitindo um balanceamento de carga dinâmico e mais refinado, resultando em um melhor desempenho do ambiente e menor tempo de resposta das aplicações paralelas distribuídas. A nova política unifica a alocação inicial e migração de processos em um único algoritmo, de forma a compartilhar decisões para o objetivo comum de prover um melhor desempenho para aplicações de uso intensivo de processamento em clusters heterogêneos. A política é implementada sobre o ambiente de escalonamento flexível e dinâmico AMIGO, adaptado para o suporte à migração de processos. A avaliação de desempenho mostrou que a nova política oferece ganhos expressivos nos tempos de resposta quando comparada às outras duas políticas de escalonamento implementadas no AMIGO, em quase todos os cenários, para diversas aplicações e diversas situações de carga do ambiente / This work presents the project and implementation of the scheduling policy with process migration support JUMP. Process migration is an important tool that complements the initial placement performed by the scheduling policy in a distributed parallel environment, allowing for dynamic and more refined load balancing, resulting in better performance of the environment and shorter response time for distributed parallel applications. The new policy unifies initial placement and process migration in a single algorithm, enabling the sharing of decisions for the common goal of providing a better performance for CPU-bound applications in heterogeneous clusters. The policy is implemented over the dynamical and flexible environment AMIGO, adapted in order to support process migration. Performance evaluation showed that the new policy offers expressive gains in response times when compared to other two scheduling policies implemented in AMIGO in almost all scenarios, for different applications and different environment load situations

A migração de processos é importante em programas MPI por vários motivos, tais como permitir re-escalonamento de processos, balanceamento de cargas e tolerância a falhas. Independentemente do tipo do uso da migração, conhecer o custo imposto pela realização desta operação é um problema pertinente. Quando utiliza-se migração para tentar diminuir o tempo de execução de uma aplicação paralela, este custo passa a ser um ponto crítico. Existem algumas soluções para migração de processos em programas MPI disponíveis atualmente. No entanto, ainda não existe um estudo que quantifique o custo destas migrações. Nesse contexto, este trabalho apresenta um estudo para modelar e dimensionar o custo de migração de processos em programasMPI. Primeiramente, o trabalho identificou, analisou, avaliou e, quando necessário, adaptou as principais soluções disponíveis atualmente para migrar processos MPI. Com base nessas soluções, foram criados modelos de custo que poderão ser utilizado para estimar dinamicamente os custos de migração e auxiliar na tomada de decisão em algoritmos de escalonamento. Osmodelos criados foram utilizados para estimar os custos demigração emaplicações paralelas e o resultado foi comparado comos custos demigração reais. Nesta comparação, os valores previsto ficaram bastante próximos dos valores observados no experimento, demonstrando a qualidade das previsões dos modelos propostos. / Process migration is essential for MPI programs for different reasons, such as processes rescheduling, load balancing and fault tolerance. Knowing well the cost necessary for this operation is a pertinent problem, regardless of the type of migration use. Whenever migration is used for improving the performance of parallel applications, its cost becomes a deciding point. Nowadays, there are some solutions to process migration available for MPI programs. However, there is not a study that can quantify the migration cost and its impact on the execution of MPI programs. In this context, this work presents a study for modeling and dimensioning the process migration cost in MPI programs. First, we identified, analyzed, evaluated and, when needed, adapted the main solutions which are presently available to migrate MPI processes. Based in these solutions, we defined cost models. These models can be used to dynamically estimate the migration costs and to guide scheduling decisions. These models were used to predict the migration cost in parallel applications and the result was compared to observed migration costs. In this comparison, the predicted values were very similar to those observed in the experiment. This work still shows an evaluation about the impact of a migration in the execution of real parallel applications in order to verifying the viability of applying this approach to improve the performance.

A migração de processos é importante em programas MPI por vários motivos, tais como permitir re-escalonamento de processos, balanceamento de cargas e tolerância a falhas. Independentemente do tipo do uso da migração, conhecer o custo imposto pela realização desta operação é um problema pertinente. Quando utiliza-se migração para tentar diminuir o tempo de execução de uma aplicação paralela, este custo passa a ser um ponto crítico. Existem algumas soluções para migração de processos em programas MPI disponíveis atualmente. No entanto, ainda não existe um estudo que quantifique o custo destas migrações. Nesse contexto, este trabalho apresenta um estudo para modelar e dimensionar o custo de migração de processos em programasMPI. Primeiramente, o trabalho identificou, analisou, avaliou e, quando necessário, adaptou as principais soluções disponíveis atualmente para migrar processos MPI. Com base nessas soluções, foram criados modelos de custo que poderão ser utilizado para estimar dinamicamente os custos de migração e auxiliar na tomada de decisão em algoritmos de escalonamento. Osmodelos criados foram utilizados para estimar os custos demigração emaplicações paralelas e o resultado foi comparado comos custos demigração reais. Nesta comparação, os valores previsto ficaram bastante próximos dos valores observados no experimento, demonstrando a qualidade das previsões dos modelos propostos. / Process migration is essential for MPI programs for different reasons, such as processes rescheduling, load balancing and fault tolerance. Knowing well the cost necessary for this operation is a pertinent problem, regardless of the type of migration use. Whenever migration is used for improving the performance of parallel applications, its cost becomes a deciding point. Nowadays, there are some solutions to process migration available for MPI programs. However, there is not a study that can quantify the migration cost and its impact on the execution of MPI programs. In this context, this work presents a study for modeling and dimensioning the process migration cost in MPI programs. First, we identified, analyzed, evaluated and, when needed, adapted the main solutions which are presently available to migrate MPI processes. Based in these solutions, we defined cost models. These models can be used to dynamically estimate the migration costs and to guide scheduling decisions. These models were used to predict the migration cost in parallel applications and the result was compared to observed migration costs. In this comparison, the predicted values were very similar to those observed in the experiment. This work still shows an evaluation about the impact of a migration in the execution of real parallel applications in order to verifying the viability of applying this approach to improve the performance.

A migração de processos é importante em programas MPI por vários motivos, tais como permitir re-escalonamento de processos, balanceamento de cargas e tolerância a falhas. Independentemente do tipo do uso da migração, conhecer o custo imposto pela realização desta operação é um problema pertinente. Quando utiliza-se migração para tentar diminuir o tempo de execução de uma aplicação paralela, este custo passa a ser um ponto crítico. Existem algumas soluções para migração de processos em programas MPI disponíveis atualmente. No entanto, ainda não existe um estudo que quantifique o custo destas migrações. Nesse contexto, este trabalho apresenta um estudo para modelar e dimensionar o custo de migração de processos em programasMPI. Primeiramente, o trabalho identificou, analisou, avaliou e, quando necessário, adaptou as principais soluções disponíveis atualmente para migrar processos MPI. Com base nessas soluções, foram criados modelos de custo que poderão ser utilizado para estimar dinamicamente os custos de migração e auxiliar na tomada de decisão em algoritmos de escalonamento. Osmodelos criados foram utilizados para estimar os custos demigração emaplicações paralelas e o resultado foi comparado comos custos demigração reais. Nesta comparação, os valores previsto ficaram bastante próximos dos valores observados no experimento, demonstrando a qualidade das previsões dos modelos propostos. / Process migration is essential for MPI programs for different reasons, such as processes rescheduling, load balancing and fault tolerance. Knowing well the cost necessary for this operation is a pertinent problem, regardless of the type of migration use. Whenever migration is used for improving the performance of parallel applications, its cost becomes a deciding point. Nowadays, there are some solutions to process migration available for MPI programs. However, there is not a study that can quantify the migration cost and its impact on the execution of MPI programs. In this context, this work presents a study for modeling and dimensioning the process migration cost in MPI programs. First, we identified, analyzed, evaluated and, when needed, adapted the main solutions which are presently available to migrate MPI processes. Based in these solutions, we defined cost models. These models can be used to dynamically estimate the migration costs and to guide scheduling decisions. These models were used to predict the migration cost in parallel applications and the result was compared to observed migration costs. In this comparison, the predicted values were very similar to those observed in the experiment. This work still shows an evaluation about the impact of a migration in the execution of real parallel applications in order to verifying the viability of applying this approach to improve the performance.

Este trabalho apresenta o projeto e a implementação da política de escalonamento com suporte à migração de processos JUMP. A migração de processos é uma ferramenta importante que complementa a alocação inicial realizada pela política de escalonamento em um ambiente paralelo distribuído, permitindo um balanceamento de carga dinâmico e mais refinado, resultando em um melhor desempenho do ambiente e menor tempo de resposta das aplicações paralelas distribuídas. A nova política unifica a alocação inicial e migração de processos em um único algoritmo, de forma a compartilhar decisões para o objetivo comum de prover um melhor desempenho para aplicações de uso intensivo de processamento em clusters heterogêneos. A política é implementada sobre o ambiente de escalonamento flexível e dinâmico AMIGO, adaptado para o suporte à migração de processos. A avaliação de desempenho mostrou que a nova política oferece ganhos expressivos nos tempos de resposta quando comparada às outras duas políticas de escalonamento implementadas no AMIGO, em quase todos os cenários, para diversas aplicações e diversas situações de carga do ambiente / This work presents the project and implementation of the scheduling policy with process migration support JUMP. Process migration is an important tool that complements the initial placement performed by the scheduling policy in a distributed parallel environment, allowing for dynamic and more refined load balancing, resulting in better performance of the environment and shorter response time for distributed parallel applications. The new policy unifies initial placement and process migration in a single algorithm, enabling the sharing of decisions for the common goal of providing a better performance for CPU-bound applications in heterogeneous clusters. The policy is implemented over the dynamical and flexible environment AMIGO, adapted in order to support process migration. Performance evaluation showed that the new policy offers expressive gains in response times when compared to other two scheduling policies implemented in AMIGO in almost all scenarios, for different applications and different environment load situations

The run-time reconfiguration of Field Programmable Gate Arrays (FPGAs) opens new avenues to hardware reuse. Through the use of process migration between hardware and software, an FPGA provides a parallel execution cache. Busy processes can be migrated into hardware-based, parallel processors, and idle processes can be migrated out increasing the utilization of the hardware. The application of hardware/software process migration to the acceleration of Register Transfer Level (RTL) circuit simulation is developed and analyzed. RTL code can exhibit a form of locality of reference such that executing processes tend to be executed again. This property is termed executive temporal locality, and it can be exploited by migration systems to accelerate RTL simulation. In this dissertation, process migration is first formally modeled using Finite State Machines (FSMs). Upon FSMs are built programs, processes, migration realms, and the migration of process state within a realm. From this model, a taxonomy of migration realms is developed. Second, process migration is applied to the RTL simulation of digital circuits. The canonical form of an RTL process is defined, and transformations of HDL code are justified and demonstrated. These transformations allow a simulator to identify basic active units within the simulation and combine them to balance the load across a set of processors. Through the use of input monitors, executive locality of reference is identified and demonstrated on a set of six RTL designs. Finally, the implementation of a migration system is described which utilizes Virtual Machines (VMs) and Real Machines (RMs) in existing FPGAs. Empirical and algorithmic models are developed from the data collected from the implementation to evaluate the effect of optimizations and migration algorithms. / Ph. D.

Este trabalho apresenta a implementação e a utilização da migração de processos SPMD (Single Program Multiple Data), a qual realiza somente a transferência dos dados, que estão sendo manipulados pelo processo, para realizar a migração. Seu principal objetivo foi o estudo do impacto do balanceamento de carga no desempenho de aplicações, desenvolvidas utilizando o modelo de programação SPMD. Depois de realizados testes com aplicações SPMD reais, em sistemas computacionais distribuídos utilizando a migração de processos SPMD, foi possível verificar que ganhos de desempenho podem ser alcançados, tanto na migração de processos quanto no tempo de execução de aplicações paralelas SPMD. / This research presents the implementation and use of the SPMD (Single Program Multiple Data) process migration, which only does the transference of the data that are being used by the process, to perform the process migration. Its main objective was the study of the load balancing impact in the performance of applications developed using the SPMD programming model. After performing the tests with real SPMD applications, in distributed computational systems using the SPMD process migration, it was achieved good performance gains, both in the process migration and in the time execution of applications SPMD parallel applications.

Este trabalho apresenta a implementação e a utilização da migração de processos SPMD (Single Program Multiple Data), a qual realiza somente a transferência dos dados, que estão sendo manipulados pelo processo, para realizar a migração. Seu principal objetivo foi o estudo do impacto do balanceamento de carga no desempenho de aplicações, desenvolvidas utilizando o modelo de programação SPMD. Depois de realizados testes com aplicações SPMD reais, em sistemas computacionais distribuídos utilizando a migração de processos SPMD, foi possível verificar que ganhos de desempenho podem ser alcançados, tanto na migração de processos quanto no tempo de execução de aplicações paralelas SPMD. / This research presents the implementation and use of the SPMD (Single Program Multiple Data) process migration, which only does the transference of the data that are being used by the process, to perform the process migration. Its main objective was the study of the load balancing impact in the performance of applications developed using the SPMD programming model. After performing the tests with real SPMD applications, in distributed computational systems using the SPMD process migration, it was achieved good performance gains, both in the process migration and in the time execution of applications SPMD parallel applications.

No description available.