Algoritmos de balanceamento de carga são utilizados em sistemas distribuídos para homogeneizar a ocupação dos recursos computacionais disponíveis. A homogeneidade na ocupação do ambiente permite otimizar a alocação de recursos e, conseqüentemente, aumentar o desempenho das aplicações. Com o advento dos sistemas distribuídos de alta escala, fazem-se necessárias pesquisas para a construção de algoritmos de balanceamento de carga que sejam capazes de gerir com eficiência esses sistemas. Essa eficiência é medida através do número de mensagens geradas no ambiente, do suporte a ambientes heterogêneos, do uso de políticas que consomem poucos recursos do sistema, da estabilidade em alta carga, da escalabilidade do sistema e dos baixos tempos de resposta. Com o objetivo de atender as necessidades dos sistemas distribuídos de alta escala, este doutorado propõe, apresenta e avalia um novo algoritmo de balanceamento de carga denominado TLBA (Tree Load Balancing Algorithm). Esse algoritmo organiza os computadores do sistema em uma topologia lógica na forma de árvore, sobre a qual são executadas operações de balanceamento de carga. Para validar o TLBA foi construído um simulador que, submetido a testes, permitiu comprovar suas contribuições, que incluem: o baixo número de mensagens geradas pelas operações de balanceamento de carga; a estabilidade em altas cargas; os baixos tempos médios de resposta de processos. Para validar os resultados de simulação, foi construído um protótipo do TLBA. Esse protótipo confirmou os resultados de simulação e, conseqüentemente, as contribuições do algoritmo. / Load balancing algorithms are applied in distributed systems to homogenize the occupation of the available computational resources. The homogeneity of the environment occupation allows optimising the resource allocation and consequently, increasing the application performance. With the advent of the large-scale distributed systems, it was necessary to start researching the construction of load balancing algorithms which are able to manage these systems with efficiency. This efficiency is measured through the number of messages generated on the environment; the support to heterogeneous environments and the load balance policies which should spend the minimal resources time; the stability in overloaded situations; the system scalability; and the processes average response times, that should be small. With the aim to achieve the large-scale distributed systems requirements, this Ph.D. proposes, presents and evaluates a new load balancing algorithm named TLBA (Tree Load Balancing Algorithm). This algorithm arranges the computers on a logical network topology with a tree format. The load balancing operations are executed over this tree. To evaluate the TLBA algorithm, a simulator was built that was submitted to tests that confirmed the following characteristics: the small number of messages generated by the load balancing operations; the stability in overloaded situations; the small average processes response times. To validate the simulation results a TLBA prototype was implemented. This prototype confirmed the simulation results and consequently the contributions of the proposed algorithm.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.

Algoritmos de balanceamento de carga são utilizados em sistemas distribuídos para homogeneizar a ocupação dos recursos computacionais disponíveis. A homogeneidade na ocupação do ambiente permite otimizar a alocação de recursos e, conseqüentemente, aumentar o desempenho das aplicações. Com o advento dos sistemas distribuídos de alta escala, fazem-se necessárias pesquisas para a construção de algoritmos de balanceamento de carga que sejam capazes de gerir com eficiência esses sistemas. Essa eficiência é medida através do número de mensagens geradas no ambiente, do suporte a ambientes heterogêneos, do uso de políticas que consomem poucos recursos do sistema, da estabilidade em alta carga, da escalabilidade do sistema e dos baixos tempos de resposta. Com o objetivo de atender as necessidades dos sistemas distribuídos de alta escala, este doutorado propõe, apresenta e avalia um novo algoritmo de balanceamento de carga denominado TLBA (Tree Load Balancing Algorithm). Esse algoritmo organiza os computadores do sistema em uma topologia lógica na forma de árvore, sobre a qual são executadas operações de balanceamento de carga. Para validar o TLBA foi construído um simulador que, submetido a testes, permitiu comprovar suas contribuições, que incluem: o baixo número de mensagens geradas pelas operações de balanceamento de carga; a estabilidade em altas cargas; os baixos tempos médios de resposta de processos. Para validar os resultados de simulação, foi construído um protótipo do TLBA. Esse protótipo confirmou os resultados de simulação e, conseqüentemente, as contribuições do algoritmo. / Load balancing algorithms are applied in distributed systems to homogenize the occupation of the available computational resources. The homogeneity of the environment occupation allows optimising the resource allocation and consequently, increasing the application performance. With the advent of the large-scale distributed systems, it was necessary to start researching the construction of load balancing algorithms which are able to manage these systems with efficiency. This efficiency is measured through the number of messages generated on the environment; the support to heterogeneous environments and the load balance policies which should spend the minimal resources time; the stability in overloaded situations; the system scalability; and the processes average response times, that should be small. With the aim to achieve the large-scale distributed systems requirements, this Ph.D. proposes, presents and evaluates a new load balancing algorithm named TLBA (Tree Load Balancing Algorithm). This algorithm arranges the computers on a logical network topology with a tree format. The load balancing operations are executed over this tree. To evaluate the TLBA algorithm, a simulator was built that was submitted to tests that confirmed the following characteristics: the small number of messages generated by the load balancing operations; the stability in overloaded situations; the small average processes response times. To validate the simulation results a TLBA prototype was implemented. This prototype confirmed the simulation results and consequently the contributions of the proposed algorithm.