Auto-Balanceamento de Carga em Programas Paralelos

• José Nagib Cotrim Árabe UFMG
• Cristina Duarte Murta UFMG

DOI: https://doi.org/10.5753/sbac-pad.1996.19824

Resumo

Este artigo aborda o problema do balanceamento interno de carga de programas paralelos em redes de workstations homogêneas e heterogêneas. O conceito de programas paralelos auto-balanceáveis é discutido. Um estudo detalhado do balanceamento de carga de programas Dome [1] é apresentado. Os principais objetivos são quantificar os ganhos obtidos com o balanceamento da carga e identificar os obstáculos mais importantes para a obtenção de ganhos adicionais. Ambientes homogêneos e heterogêneos, estáveis e instáveis foram analisados. Os resultados indicam que a obtenção de ganhos relevantes com o balanceamento de carga está vinculada a uma escolha cuidadosa do número de operações paralelas que devem ser executadas antes da próxima etapa de balanceamento de carga e que este número deve ser dinamicamente determinado por algum algoritmo adaptativo em função da heterogeneidade e da estabilidade do ambiente.

Referências

Árabe, J.N.C., Beguelin, A., Lowekamp, B., Seligman, E., Starkey, M. and Stephan, P., "Dome: Parallel Programming in a Distributed Computing Environment", Proceedings of the 10th International Parallel Processing Symposium, Honolulu, Hawaii, April 15-19, 1996, pp. 218-224.

Casavant, T.L. and Kuhl, J.G., "Effects of Response and Stability on Scheduling in Distributed Computing Systems", IEEE Transactions on Software Engineering, Vol. SE-14, No. 11, November 1988, pp. 1578-1588.

Eager, D.L., Lazowska, E.D. and Zahorjan, J., "Adaptive Load Sharing in Homogeneous Distributed Systems", IEEE Transactions on Software Engineering, Vol. SE-12, No. 5, May 1986, pp. 662-675.

Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R. and Sunderam, V., PVM: Parallel Virtual Machine A Users' Guide and Tutorial for Networked Parallel Computing, MIT Press, 1994.

Hennessy, J. L. and Patterson, D. A., Computer Architecture: A Quantitative Approach, Second Edition, Morgan Kaufmann Publishers, Inc., 1996.

Livny, M. and Melman, M., "Load Balancing in Homogeneous Broadcast Distributed Systems", Proceedings of the ACM Comput. Network Performance Symposium., 1982, pp. 47-55.

Murta, Cristina D. and Árabe, J. Nagib C., "Estudo do Balanceamento de Carga no Ambiente Dome", Relatório Técnico 013/96, Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Brasil.

Shivaratri, N.G., Krueger, P. and Singhal, M., "Load Distributing for Locally Distributed Systems", IEEE Computer, Vol. 25, No. 12, December 1992, pp. 33-44.