Auto-Organização na Seleção de Candidatos a Migração em Aplicações Bulk Synchronous Parallel
Resumo
Reescalonamento de processos pode ser uma técnica pertinente para atingir melhor desempenho, principalmente quando cargas irregulares e ambientes com múltiplos clusters são considerados. A decisão de mover processos para novos recursos é NP-Difícil, e heurísticas são usadas com o intuito de atingir bons resultados em um tempo aceitável. Nesse sentido, esse artigo apresenta AutoMig – uma nova heurística para aplicações BSP (Bulk Synchronous Parallel) que auto-organiza a seleção dos candidatos a migração para diferentes clusters. Seu diferencial é uma função de predição (pf) que considera dados de computação e comunicação dos processos, bem como os custos de migração. pf é aplicada sobre uma lista de escalonamentos e AutoMig decide qual é o mais adequado deles para atingir um desempenho melhor que o oferecido pelo mapeamento corrente. Os resultados mostram ganhos de até 32% nos testes de uma aplicação CPU-Bound em um ambiente simulado com múltiplos clusters.
Referências
Baritompa, W., Bulger, D. W., and Wood, G. R. (2007). Generating functions and the performance of backtracking adaptive search. J. of Global Optimization, 37:159–175.
Bhandarkar, M. A., Brunner, R., and Kale, L. V. (2000). Run-time support for adaptive load balancing. In IPDPS ’00: Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, pages 1152–1159, London, UK. Springer-Verlag.
Bonorden, O. (2007). Load balancing in the bulk-synchronous-parallel setting using process migrations. In Int. Parallel and Distrib. Processing Symp., 2007,pages 1–9.IEEE.
Bonorden, O., Gehweiler, J., and auf der Heide, F. M. (2005). Load balancing strategies in a web computing environment. In Proceeedings of International Conference on Parallel Processing and Applied Mathematics (PPAM), pages 839–846, Poznan, Poland.
Casanova, H., Legrand, A., and Quinson, M. (2008). Simgrid: A generic framework for large-scale distributed experiments. In Tenth International Conference on Computer Modeling and Simulation (uksim), pages 126–131, Los Alamitos, CA, USA. IEEE.
Chen, L., Wang, C.-L., and Lau, F. (2008). Process reassignment with reduced migration cost in grid load rebalancing. Parallel and Distrib. Processing, 2008, pages 1–13,IEEE.
da Rosa Righi, R., Pilla, L. L., Carissimi, A., Navaux, P. A., and Heiss, H.-U. (2010). Observing the impact of multiple metrics and runtime adaptations on bsp process rescheduling. Parallel Processing Letters, 20(2):123–144.
da Silva e Silva, F. J., Kon, F., Goldman, A., Finger, M., de Camargo, R. Y., Filho, F. C., and Costa, F. M. (2010). Application execution management on the integrade opportunistic grid middleware. J. Parallel Distrib. Comput., 70(5):573–583.
De Grande, R. E. and Boukerche, A. (2011). Dynamic balancing of communication and computation load for hla-based simulations on large-scale distributed systems. J. Parallel Distrib. Comput., 71:40–52.
Ding, D., Luo, S., and Gao, Z. (2009). A dual heuristic scheduling strategy based on task partition in grid environments. In Int. Joint Conference on Computational Sciences and Optimization, pages 63–67, IEEE.
Duselis, J., Cauich, E., Wang, R., and Scherson, I. (2009). Resource selection and allocation for dynamic adaptive computing in heterogeneous clusters. In Cluster Computing and Workshops, 2009. CLUSTER ’09. IEEE International Conference on, pages 1 –9.
El Kabbany, G., Wanas, N., Hegazi, N., and Shaheen, S. (2011). A dynamic load balancing framework for real-time applications in message passing systems. International Journal of Parallel Programming, 39:143–182. DOI: 10.1007/s10766-010-0134-5.
Guo, Y., Chen, X., Deng, M., Wang, Z., Lv, W., Xu, C., and Wang, T. (2009). The fractal compression coding in mobile video monitoring system. In WRI International Conference on Comm. and Mobile Computing, pages 492–495, IEEE.
Hendrickson, B. (2009). Computational science: Emerging opportunities and challenges. Journal of Physics: Conference Series, 180(1):012013.
Huang, C., Zheng, G., Kale, L., and Kumar, S. (2006). Performance evaluation of adaptive mpi. In PPoPP ’06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 12–21, ACM Press.
Kwok, Y.-K. and Cheung, L.-S. (2004). A new fuzzy-decision based load balancing system for distributed object computing. J. Parallel Distrib. Comput., 64(2):238–253.
Moreno-Vozmediano, R. and Alonso-Conde, A. B. (2005). Influence of grid economic factors on scheduling and migration. In High Perf. Comp. for Computational Science, volume 3402 of Lecture Notes in Comp. Science, pages 274–287. Springer.
Nascimento, A. P., Sena, A. C., Boeres, C., and Rebello, V. E. F. (2007). Distributed and dynamic self-scheduling of parallel mpi grid applications: Research articles. Concurr. Comput. : Pract. Exper., 19(14):1955–1974.
Pascual, J. A., Navaridas, J., and Miguel-Alonso, J. (2009). Job scheduling strategies for parallel processing. chapter Effects of Topology-Aware Allocation Policies on Scheduling Performance, pages 138–156. Springer-Verlag, Berlin, Heidelberg.
Qin, X., Jiang, H., Manzanares, A., Ruan, X., and Yin, S. (2010). Communication-aware load balancing for parallel applic. on clusters. IEEE Trans. Comput., 59(1):42–52.
Sanjay, H. A. and Vadhiyar, S. S. (2009). A strategy for scheduling tightly coupled parallel applications on clusters. Concurr. Comput. : Pract. Exper., 21(18):2491–2517.
Silva, R. E., Pezzi, G., Maillard, N., and Diverio, T. (2005). Automatic data-flow graph generation of mpi programs. In SBAC-PAD ’05: Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing, pages 93–100, Washington, DC, USA. IEEE Computer Society.
Tanenbaum, A. (2003). Computer Networks. Prentice Hall, New Jersey, 4th ed.
Vadhiyar, S. S. and Dongarra, J. J. (2005). Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257.
Xhafa, F. and Abraham, A. (2010). Computational models and heuristic methods for grid scheduling problems. Future Gener. Comput. Syst., 26(4):608–621.
Xing, C. (2008). An adaptive domain pool scheme for fractal image compression. Education Technology and Training and Geoscience and Remote Sensing, 2:719–722.
Yang, C.-T. and Chou, K.-Y. (2009). An adaptive job allocation strategy for heterogeneous multiple clusters. In Int. Conf. on Computer and Information Technology - Volume 02, pages 209–214, IEEE.
Zaki, M. J., Li, W., and Parthasarathy, S. (1997). Customized dynamic load balancing for a network of workstations. J. Parallel Distrib. Comput., 43(2):156–162.
Bhandarkar, M. A., Brunner, R., and Kale, L. V. (2000). Run-time support for adaptive load balancing. In IPDPS ’00: Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, pages 1152–1159, London, UK. Springer-Verlag.
Bonorden, O. (2007). Load balancing in the bulk-synchronous-parallel setting using process migrations. In Int. Parallel and Distrib. Processing Symp., 2007,pages 1–9.IEEE.
Bonorden, O., Gehweiler, J., and auf der Heide, F. M. (2005). Load balancing strategies in a web computing environment. In Proceeedings of International Conference on Parallel Processing and Applied Mathematics (PPAM), pages 839–846, Poznan, Poland.
Casanova, H., Legrand, A., and Quinson, M. (2008). Simgrid: A generic framework for large-scale distributed experiments. In Tenth International Conference on Computer Modeling and Simulation (uksim), pages 126–131, Los Alamitos, CA, USA. IEEE.
Chen, L., Wang, C.-L., and Lau, F. (2008). Process reassignment with reduced migration cost in grid load rebalancing. Parallel and Distrib. Processing, 2008, pages 1–13,IEEE.
da Rosa Righi, R., Pilla, L. L., Carissimi, A., Navaux, P. A., and Heiss, H.-U. (2010). Observing the impact of multiple metrics and runtime adaptations on bsp process rescheduling. Parallel Processing Letters, 20(2):123–144.
da Silva e Silva, F. J., Kon, F., Goldman, A., Finger, M., de Camargo, R. Y., Filho, F. C., and Costa, F. M. (2010). Application execution management on the integrade opportunistic grid middleware. J. Parallel Distrib. Comput., 70(5):573–583.
De Grande, R. E. and Boukerche, A. (2011). Dynamic balancing of communication and computation load for hla-based simulations on large-scale distributed systems. J. Parallel Distrib. Comput., 71:40–52.
Ding, D., Luo, S., and Gao, Z. (2009). A dual heuristic scheduling strategy based on task partition in grid environments. In Int. Joint Conference on Computational Sciences and Optimization, pages 63–67, IEEE.
Duselis, J., Cauich, E., Wang, R., and Scherson, I. (2009). Resource selection and allocation for dynamic adaptive computing in heterogeneous clusters. In Cluster Computing and Workshops, 2009. CLUSTER ’09. IEEE International Conference on, pages 1 –9.
El Kabbany, G., Wanas, N., Hegazi, N., and Shaheen, S. (2011). A dynamic load balancing framework for real-time applications in message passing systems. International Journal of Parallel Programming, 39:143–182. DOI: 10.1007/s10766-010-0134-5.
Guo, Y., Chen, X., Deng, M., Wang, Z., Lv, W., Xu, C., and Wang, T. (2009). The fractal compression coding in mobile video monitoring system. In WRI International Conference on Comm. and Mobile Computing, pages 492–495, IEEE.
Hendrickson, B. (2009). Computational science: Emerging opportunities and challenges. Journal of Physics: Conference Series, 180(1):012013.
Huang, C., Zheng, G., Kale, L., and Kumar, S. (2006). Performance evaluation of adaptive mpi. In PPoPP ’06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 12–21, ACM Press.
Kwok, Y.-K. and Cheung, L.-S. (2004). A new fuzzy-decision based load balancing system for distributed object computing. J. Parallel Distrib. Comput., 64(2):238–253.
Moreno-Vozmediano, R. and Alonso-Conde, A. B. (2005). Influence of grid economic factors on scheduling and migration. In High Perf. Comp. for Computational Science, volume 3402 of Lecture Notes in Comp. Science, pages 274–287. Springer.
Nascimento, A. P., Sena, A. C., Boeres, C., and Rebello, V. E. F. (2007). Distributed and dynamic self-scheduling of parallel mpi grid applications: Research articles. Concurr. Comput. : Pract. Exper., 19(14):1955–1974.
Pascual, J. A., Navaridas, J., and Miguel-Alonso, J. (2009). Job scheduling strategies for parallel processing. chapter Effects of Topology-Aware Allocation Policies on Scheduling Performance, pages 138–156. Springer-Verlag, Berlin, Heidelberg.
Qin, X., Jiang, H., Manzanares, A., Ruan, X., and Yin, S. (2010). Communication-aware load balancing for parallel applic. on clusters. IEEE Trans. Comput., 59(1):42–52.
Sanjay, H. A. and Vadhiyar, S. S. (2009). A strategy for scheduling tightly coupled parallel applications on clusters. Concurr. Comput. : Pract. Exper., 21(18):2491–2517.
Silva, R. E., Pezzi, G., Maillard, N., and Diverio, T. (2005). Automatic data-flow graph generation of mpi programs. In SBAC-PAD ’05: Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing, pages 93–100, Washington, DC, USA. IEEE Computer Society.
Tanenbaum, A. (2003). Computer Networks. Prentice Hall, New Jersey, 4th ed.
Vadhiyar, S. S. and Dongarra, J. J. (2005). Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257.
Xhafa, F. and Abraham, A. (2010). Computational models and heuristic methods for grid scheduling problems. Future Gener. Comput. Syst., 26(4):608–621.
Xing, C. (2008). An adaptive domain pool scheme for fractal image compression. Education Technology and Training and Geoscience and Remote Sensing, 2:719–722.
Yang, C.-T. and Chou, K.-Y. (2009). An adaptive job allocation strategy for heterogeneous multiple clusters. In Int. Conf. on Computer and Information Technology - Volume 02, pages 209–214, IEEE.
Zaki, M. J., Li, W., and Parthasarathy, S. (1997). Customized dynamic load balancing for a network of workstations. J. Parallel Distrib. Comput., 43(2):156–162.
Publicado
19/07/2011
Como Citar
GRAEBIN, Lucas; ARAÚJO, Diogo Pinheiro de; RIGHI, Rodrigo da Rosa.
Auto-Organização na Seleção de Candidatos a Migração em Aplicações Bulk Synchronous Parallel. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 10. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 2061-2074.
ISSN 2595-6167.
