Avaliação do Re-escalonamento Adaptativo de Processos BSP
Resumo
A migração de processos apresenta-se como um mecanismo para o balanceamento de carga durante a execução de aplicações, principalmente em ambientes heterogêneos e dinâmicos. Neste contexto, foi desenvolvido um modelo chamado MigBSP que controla o re-escalonamento de processos em aplicações BSP (Bulk Synchronous Parallel). Tais aplicações são divididas em superetapas, cada qual contendo fases de computação e comunicação, seguidas de uma barreira de sincronização. Tendo em vista que a barreira espera pelo processo mais lento, o modelo objetiva o ajuste da alocação dos processos para reduzir o tempo das superetapas. Considerando esse escopo, as principais contribuições do modelo são: (I) combinação de múltiplas métricas para medir o potencial de migração de cada processo; (II) consideração de padrões para analisar a regularidade dos processos; e (III) adaptatividade no re-escalonamento de acordo com o estado do sistema. Este artigo apresenta resultados experimentais do modelo sobre uma aplicação BSP regular e outra irregular.Referências
Aggarwal, G., Motwani, R., and Zhu, A. (2003). The load rebalancing problem. In SPAA ’03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 258–265, New York, NY, USA. ACM Press.
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 21th International Parallel and Distributed Processing Symposium (IPDPS 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 Computer Society.
Casavant, T. L. and Kuhl, J. G. (1988). A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans. Softw. Eng., 14(2):141–154.
Chen, C. and Tong, W. (2004). The application of the bsp model on datagrid. In SCC ’04: Proceedings of the 2004 IEEE International Conference on Services Computing, pages 471–474, Washington, DC, USA. IEEE Computer Society.
Du, C., Sun, X.-H., and Wu, M. (2007). Dynamic scheduling with process migration. In CCGRID ’07: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, pages 92–99, Washington, DC, USA. IEEE Computer Society.
Frachtenberg, E. and Schwiegelshohn, U. (2008). New Challenges of Parallel Job Scheduling. Job Scheduling Strategies for Parallel Processing, (4942):1–23.
García, E. W. and Morales-Luna, G. (2008). Simulation for bulk synchronous parallel superstep task assignment in desktop grids characterised by gaussian parameter distributions. Multiagent and Grid Systems, 4(2):141–166.
Goldchleger, A., Kon, F., Goldman, A., Finger, M., and Bezerra, G. C. (2004). Integrade object-oriented grid middleware leveraging the idle computing power of desktop machines: Research articles. Concurr. Comput. : Pract. Exper., 16(5):449–459.
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, New York, NY, USA. ACM Press.
Kondo, D., Casanova, H., Wing, E., and Berman, F. (2002). Models and scheduling mechanisms for global computing applications. In IPDPS ’02: Proceedings of the 16th International Symposium on Parallel and Distributed Processing, page 79.2, Washington, DC, USA. IEEE Computer Society.
Kovacs, J. and Kacsuk, P. (2004). A migration framework for executing parallel programs in the grid. In European Across Grids Conference, volume 3165 of Lecture Notes in Computer Science, pages 80–89. Springer.
Low, M. Y.-H., Liu, W., and Schmidt, B. (2007). A parallel bsp algorithm for irregular dynamic programming. In Advanced Parallel Processing Technologies, 7th International Symposium, volume 4847 of Lecture Notes in Computer Science, pages 151–160. Springer.
Righi, R. d. R., Pilla, L. a. L., Carissimi, A., and Navaux, P. O. (2008). Controlling processes reassignment in bsp applications. In Computer Architecture and High Performance Computing, 2008. SBAC-PAD ’08. 20th International Symposium on, pages 37–44.
Schepke, Claudio; Maillard, N. (2007). Performance improvement of the parallel lattice boltzmann method through blocked data distributions. In 19th International Symposium on Computer Architecture and High Performance Computing, 2007. SBAC-PAD 2007, pages 71–78.
Skillicorn, D. B., Hill, J. M. D., and McColl, W. F. (1997). Questions and Answers about BSP. Scientific Programming, 6(3):249–274.
Tanenbaum, A. (2003). Computer Networks. Prentice Hall PTR, Upper Saddle River, New Jersey, 4th edition.
Vadhiyar, S. S. and Dongarra, J. J. (2005). Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257.
Valiant, L. G. (1990). A bridging model for parallel computation. Commun. ACM, 33(8):103–111.
Wieczorek, M., Podlipnig, S., Prodan, R., and Fahringer, T. (2008). Bi-criteria scheduling of scientific workflows for the grid. International Symposium on Cluster Computing and the Grid (CCGrid), pages 9–16.
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 21th International Parallel and Distributed Processing Symposium (IPDPS 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 Computer Society.
Casavant, T. L. and Kuhl, J. G. (1988). A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans. Softw. Eng., 14(2):141–154.
Chen, C. and Tong, W. (2004). The application of the bsp model on datagrid. In SCC ’04: Proceedings of the 2004 IEEE International Conference on Services Computing, pages 471–474, Washington, DC, USA. IEEE Computer Society.
Du, C., Sun, X.-H., and Wu, M. (2007). Dynamic scheduling with process migration. In CCGRID ’07: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, pages 92–99, Washington, DC, USA. IEEE Computer Society.
Frachtenberg, E. and Schwiegelshohn, U. (2008). New Challenges of Parallel Job Scheduling. Job Scheduling Strategies for Parallel Processing, (4942):1–23.
García, E. W. and Morales-Luna, G. (2008). Simulation for bulk synchronous parallel superstep task assignment in desktop grids characterised by gaussian parameter distributions. Multiagent and Grid Systems, 4(2):141–166.
Goldchleger, A., Kon, F., Goldman, A., Finger, M., and Bezerra, G. C. (2004). Integrade object-oriented grid middleware leveraging the idle computing power of desktop machines: Research articles. Concurr. Comput. : Pract. Exper., 16(5):449–459.
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, New York, NY, USA. ACM Press.
Kondo, D., Casanova, H., Wing, E., and Berman, F. (2002). Models and scheduling mechanisms for global computing applications. In IPDPS ’02: Proceedings of the 16th International Symposium on Parallel and Distributed Processing, page 79.2, Washington, DC, USA. IEEE Computer Society.
Kovacs, J. and Kacsuk, P. (2004). A migration framework for executing parallel programs in the grid. In European Across Grids Conference, volume 3165 of Lecture Notes in Computer Science, pages 80–89. Springer.
Low, M. Y.-H., Liu, W., and Schmidt, B. (2007). A parallel bsp algorithm for irregular dynamic programming. In Advanced Parallel Processing Technologies, 7th International Symposium, volume 4847 of Lecture Notes in Computer Science, pages 151–160. Springer.
Righi, R. d. R., Pilla, L. a. L., Carissimi, A., and Navaux, P. O. (2008). Controlling processes reassignment in bsp applications. In Computer Architecture and High Performance Computing, 2008. SBAC-PAD ’08. 20th International Symposium on, pages 37–44.
Schepke, Claudio; Maillard, N. (2007). Performance improvement of the parallel lattice boltzmann method through blocked data distributions. In 19th International Symposium on Computer Architecture and High Performance Computing, 2007. SBAC-PAD 2007, pages 71–78.
Skillicorn, D. B., Hill, J. M. D., and McColl, W. F. (1997). Questions and Answers about BSP. Scientific Programming, 6(3):249–274.
Tanenbaum, A. (2003). Computer Networks. Prentice Hall PTR, Upper Saddle River, New Jersey, 4th edition.
Vadhiyar, S. S. and Dongarra, J. J. (2005). Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257.
Valiant, L. G. (1990). A bridging model for parallel computation. Commun. ACM, 33(8):103–111.
Wieczorek, M., Podlipnig, S., Prodan, R., and Fahringer, T. (2008). Bi-criteria scheduling of scientific workflows for the grid. International Symposium on Cluster Computing and the Grid (CCGrid), pages 9–16.
Publicado
20/07/2009
Como Citar
PILLA, Laércio Lima; RIGHI, Rodrigo; CARISSIMI, Alexandre; NAVAUX, Philippe; HEISS, Hans-Ulrich.
Avaliação do Re-escalonamento Adaptativo de Processos BSP. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 8. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 2129-2144.
ISSN 2595-6167.
