Escalonamento Dinâmico de programas MPI-2 utilizando Divisão e Conquista
Resumo
MPI é um padrão para programação de aplicações científicas de alto desempenho e é muito utilizado em ambientes com recursos dedicados, como Clusters. A recente implementação da norma MPI-2 oferece mecanismos que permitem utilizar recursos computacionais cuja disponibilidade altera-se dinamicamente. Este trabalho estuda dois desafios que surgem com a utilização de ambientes dinâmicos: como programar as aplicações para se adaptarem aos recursos e como fazer um bom aproveitamento dos recursos disponíveis. O modelo de programação proposto para este trabalho é o D&C, pois é mais abrangente que o modelo Bag of Tasks, classicamente utilizado nesse tipo de ambiente. Para o bom aproveitamento dos recursos, propõe-se usar algoritmos de escalonamento on-line (Round-Robin e Escalonamento com lista). Por fim, para validar a proposta, são apresentadas aplicações desenvolvidas e resultados de execuções com diferentes algoritmos para escolha dos recursos utilizados.
Referências
R. Buyya. High Performance Cluster Computing: Programming and Applications. Prentice Hall, NJ, USA, 1999.
G. G. H. Cavalheiro, F. Galilée, and J.-L. Roch. Athapascan-1: Parallel Programming with Asynchronous Tasks. In Proceedings of the Yale Multithreaded Programming Workshop, Yale, USA, June 1998.
M. Cera, G. Pezzi, M. Pilla, N. Maillard, and P. Navaux. In Scheduling dynamically spawned processes in mpi-2.
M. C. Cera, G. P. Pezzi, E. N. Mathias, N. Maillard, and P. O. A. Navaux. Improving the dynamic creation of processes in mpi-2, sep 2006a. accepted to publication in 13th European PVMMPI Users Group Meeting, set, 2006.
D. Bailey et al. The NAS parallel benchmarks. Technical Report RNR-91-002, NAS Systems Division, Jan. 1991.
D. Dailey and C. E. Leiserson. Using Cilk to write multiprocessor chess programs. The Journal of the International Computer Chess Association, 2002.
J. Dongarra, P. Luszczek, and A. Petitet. The LINPACK benchmark: past, present and future. Concurrency and Computation: Practice and Experience, 15(9):803–820, 2003.
W. Gropp, E. Lusk, and A. Skjellum. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press, Cambridge, Massachusetts, USA, Oct. 1994.
W. Gropp, E. Lusk, and R. Thakur. Using MPI-2 Advanced Features of the Message-Passing Interface. The MIT Press, Cambridge, Massachusetts, USA, 1999.
J. Jaja. An Introduction to Parallel Algorithms. Addison-Wesley, 1992.
R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, chapter 17, pages 871–941. Elsevier Science Publishers, 1990.
P. Pacheco. Parallel Programming With MPI. Morgan Kaufmann Publishers Inc, 1996.
V. S. Sunderam. PVM: A framework for parallel distributed computing. Concurrency: practice and experience, 2(4):315–339, Dec. 1990.
R. L. R. e. C. S. Thomas H. Cormen, Charles E. Leiserson. Algoritmos: teoria e prática. Ed. Campus, 2002.
R. V. van Nieuwpoort et al. Ibis: an efficient java-based grid programming environment. In Proc. ACM-ISCOPE conference on Java Grande, pages 18–27, New York, NY, USA, 2002. ACM Press.
R. V. van Nieuwpoort, T. Kielmann, and H. E. Bal. Satin: Efficient parallel divide-and-conquer in java. In Proc. EuroPar, pages 690–699, Munich, Germany, Aug. 2000. Springer.
R. V. van Nieuwpoort, J. Maassen, G. Wrzesinska, T. Kielmann, and H. E. Bal. Adaptive load balancing for divideand-conquer grid applications. Journal of Supercomputing, 2006.
