Um Ambiente para o Desenvolvimento e Avaliação de Algoritmos de Escalonamento para Grades Computacionais
Resumo
O objetivo de uma grade computacional é o de agregar uma coleção de recursos geograficamente distribuídos para oferecer poder computacional para aplicações. Contudo, permanece como desafio a exploração eficiente do desempenho deste ambiente, devido principalmente à natureza distribuída, compartilhada e heterogênea dos recursos. Escalonadores eficientes são fundamentais para que aplicações explorarem a potencialidade das grades. Este trabalho apresenta uma ferramenta para facilitar o desenvolvimento de, e a análise de desempenho oferecida por diferentes políticas de escalonamento de aplicações em ambientes grades.
Referências
C. Boeres e V. E. F. Rebello. On solving the static task scheduling problem for real machines. In Models for Parallel and Distributed Computation: Theory, Algorithmic Techniques and Applications, chapter 3, pages 53-84. Kluwer Academic Publishers, 2002.
C. Boeres e V.E.F. Rebello. Towards optimal task scheduling for realistic machine models: Theory and Practice. The International Journal of High Performance Computing Applications, Vol. 17, No. 2, 2003. Sage Public.
C. Boeres, A. Lima e V.E.F. Rebello. Hybrid Task Scheduling: lntegrating Static and Dynamic Heuristics. In Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing (SBACPAD' 2003), São Paulo, Brazil, November 2003. IEEE Computer Society Press.
C. Boeres e V.E.F. Rebello. EasyGrid: Towards a framework for the automatic grid enabling of legacy MPI applications. Concurrency and Computation: Practice and Experience, 16 (5): 425-432, 2004. John Wiley and Sons. [BorlWeb] Borland. http://www.borland.com.br/
H. Casanova, SimGrid: A Toolkit for the Simulation of Application Scheduling. In Proceedings of First IEEE/ACM International Symposium on Cluster Computing and the Grid, May 2001.
D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, e T. von Eicken. LogP: Towards a realistic model of parallel computation. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, USA, May 1993.
I. Foster e C. Kesselman. Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputer Applications, 11(2): 115-128, 1997.
I. Foster e.C. Kesselman (editors). The GRID: Blueprint for a New Computing Jnfrastructure. Morgan Kaufmann, 1999.
M. R. Garey e D. S. Johnson. Computers and lntractability. W. H. Freeman and Co., 1979
The GridRio Computational Grid. http://easygrid.ic.uff.br/grid/GridRio.html
J. Hwang, Y. Chow, F. Anger e B. Lee, Scheduling precendence graphs in systems with interprocessor communications times. SIAM Joumal of Computing, 18(2): 1-8, 1989. Foz do Iguaçu, 27 a 29 de Outubro de 2004
T. Kalinowski, I. Kort, e D. Trystram, List scheduling of general task graphs under LogP. Parallel Computing, 26(9): 1109-1128, 2000.
T. Kielmann, H. Bal, S. Gorlatch, K. Verstoep, e R. Hofman. Network performance-aware collective communication for clustered wide area systems. Parallel Computing, 27(11):1431-1456, 2001.
Y-K Kwok e I. Ahmad. Dynamic Critical-Path scheduling: an effective technique for allocating tasks graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 7(5):506-521. May 1996.
Y. K. Kwok e I. Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. Joumal of Parallel and Distributed Computing, 59(3):381-422, Dec. 1999.
Y-K Kwok e I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4), Dec. 1999.
M. Maheswaran and H. J. Siegel. A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems". In The Proceedings of the 7th Heterogeneous Computing Workshop (HCW98), pages 57-69, Orlando, Florida, March 1998. IEEE Comp. Soc. Press
H.A. Mendes, HLogP: Um modelo de escalonamento para a execução de aplicações MPI em grades computacionais, Dissertação de Mestrado, Instituto de Computação, Universidade Fede ral Fluminense, 2004.
Message Passing Forum. MPI: a Message Passing Interface. Technical report, University of Tennessee, 1995.
C.H. Papadimitriou, and M. Yannakakis, Towards and architecture-independent analysis of parallel algorithms. SIAMJ Computer, v. 19, p. 322-328, 1990.
V.E.F. Rebello e C. Boeres. Projeto EasyGrid: Um framework para a habilitação automática de aplicações MPI em Grids Computacionais (e a Iniciativa GridRio). Nos Anais do I Workshop em Grade Computacional e Aplicações. Programa de Verão do LNCC, Petrópolis, RJ. Brazil, Janeiro 2003.
J.A. Silva, A.A. Fonseca, B.A. Vianna, C. Boeres e V.E.F. Rebello, A Grade Computacional GridRio e o Projeto EasyGnd. Nos Anais do 11 Workshop em Grade Computacional e Aplicações, Programa de Verão 2004 do LNCC, Petrópolis, RJ, Brazil, Fevereiro, 2004.
H. Topcuoglu, S. Hariri, and M. Wu, Performance effective and low-complexity task cheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems 13,(3): 260-274, March 2002.
J.D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10:384-393, 1975.
C. Boeres e V.E.F. Rebello. Towards optimal task scheduling for realistic machine models: Theory and Practice. The International Journal of High Performance Computing Applications, Vol. 17, No. 2, 2003. Sage Public.
C. Boeres, A. Lima e V.E.F. Rebello. Hybrid Task Scheduling: lntegrating Static and Dynamic Heuristics. In Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing (SBACPAD' 2003), São Paulo, Brazil, November 2003. IEEE Computer Society Press.
C. Boeres e V.E.F. Rebello. EasyGrid: Towards a framework for the automatic grid enabling of legacy MPI applications. Concurrency and Computation: Practice and Experience, 16 (5): 425-432, 2004. John Wiley and Sons. [BorlWeb] Borland. http://www.borland.com.br/
H. Casanova, SimGrid: A Toolkit for the Simulation of Application Scheduling. In Proceedings of First IEEE/ACM International Symposium on Cluster Computing and the Grid, May 2001.
D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, e T. von Eicken. LogP: Towards a realistic model of parallel computation. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, USA, May 1993.
I. Foster e C. Kesselman. Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputer Applications, 11(2): 115-128, 1997.
I. Foster e.C. Kesselman (editors). The GRID: Blueprint for a New Computing Jnfrastructure. Morgan Kaufmann, 1999.
M. R. Garey e D. S. Johnson. Computers and lntractability. W. H. Freeman and Co., 1979
The GridRio Computational Grid. http://easygrid.ic.uff.br/grid/GridRio.html
J. Hwang, Y. Chow, F. Anger e B. Lee, Scheduling precendence graphs in systems with interprocessor communications times. SIAM Joumal of Computing, 18(2): 1-8, 1989. Foz do Iguaçu, 27 a 29 de Outubro de 2004
T. Kalinowski, I. Kort, e D. Trystram, List scheduling of general task graphs under LogP. Parallel Computing, 26(9): 1109-1128, 2000.
T. Kielmann, H. Bal, S. Gorlatch, K. Verstoep, e R. Hofman. Network performance-aware collective communication for clustered wide area systems. Parallel Computing, 27(11):1431-1456, 2001.
Y-K Kwok e I. Ahmad. Dynamic Critical-Path scheduling: an effective technique for allocating tasks graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 7(5):506-521. May 1996.
Y. K. Kwok e I. Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. Joumal of Parallel and Distributed Computing, 59(3):381-422, Dec. 1999.
Y-K Kwok e I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4), Dec. 1999.
M. Maheswaran and H. J. Siegel. A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems". In The Proceedings of the 7th Heterogeneous Computing Workshop (HCW98), pages 57-69, Orlando, Florida, March 1998. IEEE Comp. Soc. Press
H.A. Mendes, HLogP: Um modelo de escalonamento para a execução de aplicações MPI em grades computacionais, Dissertação de Mestrado, Instituto de Computação, Universidade Fede ral Fluminense, 2004.
Message Passing Forum. MPI: a Message Passing Interface. Technical report, University of Tennessee, 1995.
C.H. Papadimitriou, and M. Yannakakis, Towards and architecture-independent analysis of parallel algorithms. SIAMJ Computer, v. 19, p. 322-328, 1990.
V.E.F. Rebello e C. Boeres. Projeto EasyGrid: Um framework para a habilitação automática de aplicações MPI em Grids Computacionais (e a Iniciativa GridRio). Nos Anais do I Workshop em Grade Computacional e Aplicações. Programa de Verão do LNCC, Petrópolis, RJ. Brazil, Janeiro 2003.
J.A. Silva, A.A. Fonseca, B.A. Vianna, C. Boeres e V.E.F. Rebello, A Grade Computacional GridRio e o Projeto EasyGnd. Nos Anais do 11 Workshop em Grade Computacional e Aplicações, Programa de Verão 2004 do LNCC, Petrópolis, RJ, Brazil, Fevereiro, 2004.
H. Topcuoglu, S. Hariri, and M. Wu, Performance effective and low-complexity task cheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems 13,(3): 260-274, March 2002.
J.D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10:384-393, 1975.
Publicado
27/10/2004
Como Citar
FONSECA, A. A.; VIANNA, B. A.; MOURA, N. T.; MENEZES, L. T.; MENDES, H. A.; BOERES, C.; REBELLO, V. E. F..
Um Ambiente para o Desenvolvimento e Avaliação de Algoritmos de Escalonamento para Grades Computacionais. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 5. , 2004, Foz do Iguaçu.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 19-26.
DOI: https://doi.org/10.5753/wscad.2004.18996.
