Um Escalonador de Tarefas Dependentes Robusto às Incertezas nas Descrições das Aplicações em Grades
Resumo
O escalonamento de tarefas em grades é realizado considerando-se o estado corrente dos recursos da grade e a descrição dos requisitos das aplicações. Requisitos informados incorretamente podem levar à alocações que apresentam desempenhos piores do que os previstos, tornando necessária a implementação de escalonadores que sejam robustos frente à incertezas. Neste artigo, apresenta-se o escalonador PLITD-FUZZY, um escalonador de tarefas que utiliza técnicas de otimização fuzzy para produzir escalonamentos robustos frente às incertezas na descrição das aplicações. Experimentos de simulação comprovam a eficácia do PLITD-FUZZY nos casos em que há incerteza na descrição da utilização da rede pelas aplicações.
Referências
Batista, D. M., da Fonseca, N. L. S., Granelli, F., and Kliazovich, D. (2007). Uma Metodologia para o Auto-Ajuste de Aplicações em Grades. In Anais do XXVII Congresso da Sociedade Brasileira de Computação – VI WPerformance, pages 475–494.
Batista, D. M., da Fonseca, N. L. S., and Miyazawa, F. K. (2006). Escalonadores de Tarefas em Grades. In Anais do XXVI Congresso da Sociedade Brasileira de Computação – V Wperformance, pages 73–92.
Blythe, J., Jain, S., Deelman, E., Gil, Y., Vahi, K., Mandal, A., and Kennedy, K. (2005). Task Scheduling Strategies for Workflow-based Applications in Grids. In IEEE International Symposium on Cluster Computing and Grids (CCGRID’05), volume 2, pages 759–767.
Bölöni, L. and Marinescu, D. C. (2002). Robust Scheduling of Metaprograms. Journal of Scheduling, 5:395–412.
Carole, F., Garibaldi, J. M., and Ouelhadj, D. (2007). Fuzzy Grid Scheduling Using Tabu Search. In Proceedings of IEEE International Fuzzy Systems Conference, pages 1–6.
Casanova, H., Zagorodnov, D., Berman, F., and Legrand, A. (2000). Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. In HCW ’00: Proceedings of the 9th Heterogeneous Computing Workshop, page 349, Washington, DC, USA. IEEE Computer Society.
Chiang, S.-H., Arpaci-Dusseau, A., and Vernon, M. K. (2002). The Impact of More Accurate Requested Runtimes on Production Job Scheduling Performance. In 8th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2002), pages 103–127. Springer-Verlag Berlin Heidelberg.
Chiang, S.-H., Mansharamani, R. K., and Vernon, M. K. (1994). Use of Application Characteristics and Limited Preemption for Run-to-Completion Parallel Processor Scheduling Policies. In SIGMETRICS ’94: Proceedings of the 1994 ACM SIGMETRICS Conference on measurement and Modeling of Computer Systems, pages 33–44, New York, NY, USA. ACM Press.
Cirne, W.; Berman, F. (2001). A Comprehensive Model of the Supercomputer Workload. In IEEE International Workshop on Workload Characterization (WWC-4), pages 140–148.
da Silva, F. A. B. and Scherson, I. D. (2000). Improving Parallel Job Scheduling Using Runtime Measurements. In IPDPS ’00/JSSPP ’00: Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 18–38, London, UK. Springer-Verlag.
Dash Optimization. The Xpress-Optimizer. Disponível em [link]. Último acesso em 1 fev 2008.
Doar, M. and Leslie, I. M. (1993). How Bad is Naive Multicast Routing? In Proc. IEEE INFOCOM’93, pages 82–89.
Foster, I. (2002). What is the Grid? A Three Point Checklist. GRIDToday, 1(6).
Foster, I. and Kesselman, C. (1999). Computational Grids. In The Grid: Blueprint for a New Computing Infrastructure, chapter 2. Morgan-Kaufman.
Lee, C. B., Schwartzman, Y., Hardy, J., and Snavely, A. (2004). Are User Runtime Estimates Inherently Inaccurate? In 10th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2004) , pages 253–263. Springer-Verlag Berlin Heidelberg.
NASA. Applications of Montage. Disponível em [link]. Último acesso em 8 mai 2008.
Oikonomakos, M., Christodoulopoulos, K., and Varvarigos, E. M. (2007). Profiling Computation Jobs in Grid Systems. In Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2007), pages 197–204.
Papadimitriou, C. H. and Steiglitz, K. (1998). Combinatorial Optimization – Algorithms and Complexity, pages 363–366. Dover Publications.
Prodan, R. and Fahringer, T. (2005). Dynamic Scheduling of Scientific Workflow Application on the Grid: a Case Study. In SAC’05: Proceedings of the 2005 ACM symposium on Applied computing, pages 687–694, New York, NY, USA. ACM Press.
Real, R., Yamin, A., da Silva, L., Frainer, G., Augustin, I., Barbosa, J., and Geyer, C. (2003). Resource Scheduling on Grid: Handling Uncertainty. In Proceedings of the Fourth International Workshop on Grid Computing, pages 205–207.
Sakellariou, R. and Zhao, H. (2004). A Low-cost Rescheduling Policy for Efficient Mapping of Workflows on Grid Systems. Scientific Programming, 12:253 – 262.
Skillicorn, D. B. (2002). Motivating Computational Grids. In 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID’02), pages 401–406.
Sun, X. and Wu, M. (2005). GHS: A Performance System of Grid Computing. In 19th IEEE International Parallel and Distributed Processing Symposium. [link]. Accessed at 21/05/2006.
Vadhiyar, S. S. and Dongarra, J. J. (2003). A Performance Oriented Migration Framework for the Grid. In 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID’03), pages 130–137.
Zhao, H. and Sakellariou, R. (2006). Scheduling Multiple DAGs onto Heterogeneous Systems. In Proceedings of the 20h International Parallel and Distributed Processing Symposium (IPDPS 2006), pages 130–143.
Batista, D. M., da Fonseca, N. L. S., and Miyazawa, F. K. (2006). Escalonadores de Tarefas em Grades. In Anais do XXVI Congresso da Sociedade Brasileira de Computação – V Wperformance, pages 73–92.
Blythe, J., Jain, S., Deelman, E., Gil, Y., Vahi, K., Mandal, A., and Kennedy, K. (2005). Task Scheduling Strategies for Workflow-based Applications in Grids. In IEEE International Symposium on Cluster Computing and Grids (CCGRID’05), volume 2, pages 759–767.
Bölöni, L. and Marinescu, D. C. (2002). Robust Scheduling of Metaprograms. Journal of Scheduling, 5:395–412.
Carole, F., Garibaldi, J. M., and Ouelhadj, D. (2007). Fuzzy Grid Scheduling Using Tabu Search. In Proceedings of IEEE International Fuzzy Systems Conference, pages 1–6.
Casanova, H., Zagorodnov, D., Berman, F., and Legrand, A. (2000). Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. In HCW ’00: Proceedings of the 9th Heterogeneous Computing Workshop, page 349, Washington, DC, USA. IEEE Computer Society.
Chiang, S.-H., Arpaci-Dusseau, A., and Vernon, M. K. (2002). The Impact of More Accurate Requested Runtimes on Production Job Scheduling Performance. In 8th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2002), pages 103–127. Springer-Verlag Berlin Heidelberg.
Chiang, S.-H., Mansharamani, R. K., and Vernon, M. K. (1994). Use of Application Characteristics and Limited Preemption for Run-to-Completion Parallel Processor Scheduling Policies. In SIGMETRICS ’94: Proceedings of the 1994 ACM SIGMETRICS Conference on measurement and Modeling of Computer Systems, pages 33–44, New York, NY, USA. ACM Press.
Cirne, W.; Berman, F. (2001). A Comprehensive Model of the Supercomputer Workload. In IEEE International Workshop on Workload Characterization (WWC-4), pages 140–148.
da Silva, F. A. B. and Scherson, I. D. (2000). Improving Parallel Job Scheduling Using Runtime Measurements. In IPDPS ’00/JSSPP ’00: Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 18–38, London, UK. Springer-Verlag.
Dash Optimization. The Xpress-Optimizer. Disponível em [link]. Último acesso em 1 fev 2008.
Doar, M. and Leslie, I. M. (1993). How Bad is Naive Multicast Routing? In Proc. IEEE INFOCOM’93, pages 82–89.
Foster, I. (2002). What is the Grid? A Three Point Checklist. GRIDToday, 1(6).
Foster, I. and Kesselman, C. (1999). Computational Grids. In The Grid: Blueprint for a New Computing Infrastructure, chapter 2. Morgan-Kaufman.
Lee, C. B., Schwartzman, Y., Hardy, J., and Snavely, A. (2004). Are User Runtime Estimates Inherently Inaccurate? In 10th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2004) , pages 253–263. Springer-Verlag Berlin Heidelberg.
NASA. Applications of Montage. Disponível em [link]. Último acesso em 8 mai 2008.
Oikonomakos, M., Christodoulopoulos, K., and Varvarigos, E. M. (2007). Profiling Computation Jobs in Grid Systems. In Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGRID 2007), pages 197–204.
Papadimitriou, C. H. and Steiglitz, K. (1998). Combinatorial Optimization – Algorithms and Complexity, pages 363–366. Dover Publications.
Prodan, R. and Fahringer, T. (2005). Dynamic Scheduling of Scientific Workflow Application on the Grid: a Case Study. In SAC’05: Proceedings of the 2005 ACM symposium on Applied computing, pages 687–694, New York, NY, USA. ACM Press.
Real, R., Yamin, A., da Silva, L., Frainer, G., Augustin, I., Barbosa, J., and Geyer, C. (2003). Resource Scheduling on Grid: Handling Uncertainty. In Proceedings of the Fourth International Workshop on Grid Computing, pages 205–207.
Sakellariou, R. and Zhao, H. (2004). A Low-cost Rescheduling Policy for Efficient Mapping of Workflows on Grid Systems. Scientific Programming, 12:253 – 262.
Skillicorn, D. B. (2002). Motivating Computational Grids. In 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID’02), pages 401–406.
Sun, X. and Wu, M. (2005). GHS: A Performance System of Grid Computing. In 19th IEEE International Parallel and Distributed Processing Symposium. [link]. Accessed at 21/05/2006.
Vadhiyar, S. S. and Dongarra, J. J. (2003). A Performance Oriented Migration Framework for the Grid. In 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID’03), pages 130–137.
Zhao, H. and Sakellariou, R. (2006). Scheduling Multiple DAGs onto Heterogeneous Systems. In Proceedings of the 20h International Parallel and Distributed Processing Symposium (IPDPS 2006), pages 130–143.
Publicado
12/07/2008
Como Citar
BATISTA, Daniel Macêdo; DRUMMOND, André Costa; FONSECA, Nelson Luis Saldanha da.
Um Escalonador de Tarefas Dependentes Robusto às Incertezas nas Descrições das Aplicações em Grades. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 7. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 161-179.
ISSN 2595-6167.
