Avaliação de Estratégias de Balanceamento de Carga do Tipo Mestre-Escravo para Aplicações SPMD em Clusters e Grids Computacionais
Autores
|
6190 |
135,2822,160
|
|
|
6191 |
135,2822,160
|
|
|
6194 |
135,2822,160
|
Informações:
Publicações do PESC
O desempenho de aplicações paralelas do tipo SPMD (Single Prograin Multiple Data) é fortemente afetado pelos fatores dinâmicos de desequilíbrio de carga. O uso de um algoritmo de balanceamento de carga adequado é essencial para superar os efeitos destes fatores. O principal objetivo deste trabalho é avaliar o desempenho de algumas estratégias de balanceamento de carga baseadas principalmente na abordagem Mestre-escravo. Foram implementados algoritmos estáticos e dinâmicos baseados ou adaptados a partir de estratégias de escalonamento bastante utilizadas na literatura. Os dois algoritmos estáticos implementados utilizam diferentes métricas para distribuir tarefas para o processadores. O primeiro deles simplesmente distribui as tarefas de forma igualitária entre os processadores. O seguindo utiliza a ferramenta Network Weather Service (NWS) para recuperar informações mais precisas sobre as características de uma dada máquina e sobre a rede, efetuando assim uma distribuição mais eficiente. As estratégias dinâmicas utilizam o modelo mestre-escravo e foram dividas em três grupos principais: (1) nas estratégias deste grupo o mestre distribui aos seus escravos blocos de tarefas de tamanho fixo, (2) neste grupo, foram implementadas seis estratégias diferentes, onde foi utilizada uma abordagem de redução de bloco durante a execução da aplicação, (3) a estratégia mestre escravo hierárquica, que utiliza uma topologia de processadores. O desempenho dos algoritmos foi analisado a partir da execução de duas aplicações reais com diferentes características e em diferentes ambientes de execução. Os resultados obtidos mostram a importância de se escolher a estratégia adequada para uma determinada condição.
The perforinailce of SMPD (Siilgle Prograin Multiple Data) applications is strongly affected by load iinbalaiice. The use of a suitable load balancing algorithm is essential to overcoine the effects of the iinbalance factors. The maiii objective of this worlc is to evaluate the performaiice of some load balancing strategies based on static aiid inaster-slave models. Static aiid dyilainic algorithins were implemeiited and adapted on well-lcnown scheduling strategies used in the literature. The two static algorithms implemented use two different metrics to distribute worlc. The first one simply distributes the taslts equally between machines. The second one uses the Networlc Weather Service (NWS) to talte more precise iiiforinatioii about the characteristics of a given machine and about the networlc. The dynamic strategies use the inastei-slave model and are divided in three main gronps: (1) the algorithm distributes worlc by using a fixed worlc block size, (2) in this group, six different algorithms were implemeiited reduciiig the worlc bloclc size during the execution iii order to have better performaiice by reducing the grain size of the worlc along the executioii tiine, (3) the algorithin distributes worlc iil an hieraschical fashion. The impact of the algorithins was ailalyzed by runiling two real applicatioiis with different parallel patterns o11 two different distributed environments. The results show the iinportance of using proper load balancing strategies for specific eiiviroiiment coiiditioiis.