Avaliação de Desempenho de Algoritmos de Balanceamento de Carga de Aplicações SPMD na Presença de Carga Externa
Resumo
O desempenho de programas paralelos é frequentemente afetado por diferentes fatores dinâmicos de desequilíbrio de carga. Um fator de desequilíbrio muito comum, presente nos ambientes paralelos não dedicados, é a existência de outros processos concorrendo com a aplicação paralela pelos recursos computacionais. A heterogeneidade e variação desta carga externa impede que seja feita uma distribuição prévia e equilibrada das tarefas da aplicação paralela. O uso de uma estratégia de balanceamento de carga adequada é fundamemal para a redução dos efeitos causados por este fator de desequilíbrio. Neste trabalho, serão avaliadas oito estratégias de balanceamento de carga utilizadas em duas aplicações paralelas SPMD distintas, quando executadas na presença de carga externa. As aplicações SPMD implementadas calculam: (a) a multiplicação de matrizes quadradas e (b) a dispersão térmica em meios porosos. Neste trabalho, propõe-se também um índice de desbalanceamento de carga para aplicações SPMD.
Referências
M.A. Franklin e V. Govindan, "A General Matrix Iterative Model for Dynamic Load Balancing", Parallel Computing 22 (1996), 969-989.
M. Furuichi, K. Taki e N. Ichiyoshi, "A Multi-Level Load Balancing Scheme for Or-Parallel Exhaustive Search Programs on the Multi-Psi", Proceedings of the Second ACM SIGPLAN Symposium on Principies and Practice of Parallel Programming, 1990, 50-59.
S. Lifschitz, A. Plastino e C.C. Ribeiro, "Exploring Load Balancing in Parallel Processing of Recursive Queries", Proceedings of the III Euro-Par Conference, Lecture Notes in Computer Science 1300, 1997, 1125-1129.
T. G. Mattson, "Scientific Computation", Parallel and Distributed Computing Handbook (A.Y. Zomaya, editor), 981 - 1002, McGraw-Hill, 1996.
C. Moyne, S. Didierjean, H.P.A. Souto e O.T. da Silveira Filho, "Thermal Dispersion in Porous Media: One-Equation Model", International Journal of Heat and Mass Transfer 43, 2000, 3853-3867.
A. Plastino, Balanceamento de Carga de Aplicações Paralelas SPMD, Tese de Doutorado, Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, 2000.
A. Plastino, C.C. Ribeiro e N. Rodriguez, "A Tool for SPMD Application Development with Support for Load Balancing", Proceedings ofthe Intemational Conference ParCo'99, 639-646, Imperial College Press, 2000.
A. Plastino, C.C. Ribeiro e N. Rodriguez, "A Framework for SPMD Applications with Load Balancing", Proceedings of tlte 12th Symposium on Computer Architecture and High Peiformance Computing (SBAC-PAD'2000), 245-252, São Pedro, 2000.
M.J. Quinn, Parallel Computing: Theory and Practice, Series in Computer Science, McGraw-Hill, 1994. 15
O.T. da Silveira Filho, Dispersão Térmica em Meios Porosos Periódicos. Um Estudo Numérico., Tese de Doutorado, Instituto Politécnico, Universidade Estadual do Rio de Janeiro, 2001.
V. Thomé, D. Vianna, R. Costa, A. Plastino e O.T. da Silveira Filho, "Exploring Load Balancing in a Scientific SPMD Parallel Application", Proceedings of the 4th International Workshop on High Performance Scientific and Engineering Computing with Applications (HPSECA'2002) realizado em conjunto com 31st lmernational Conference on Parallel Processing (ICPP'2002), a ser publicado.
M.A. Willebeek-LeMair e A.P. Reeves, "Strategies for Dynamic Load Balancing on Highly Parallel Computers", IEEE Transactions on Parallel and Distributed Systems 4 (1993), 979-993.
M.J. Zaki, W. Li e S. Parthasarathy, "Customized Dynamic Load Balancing for a Network of Workstations", Journal of Parallel and Distributed Computing 43 (1997), 156-162.
