Process Migration: Controlling Application and Resource Dynamics by Combining Computation, Communication and Memory Metrics
Resumo
In this paper we present MigBSP, a rescheduling model that acts on Bulk Synchronous Parallel applications. It combines the metrics Computation, Communication and Memory to make migration decisions on Computation Grids. MigBSP also offers efficient adaptations to reduce its own overhead. Additionally, MigBSP is infrastructure and application independent and tries to handle dynamicity on both levels. MigBSP’s results show performance gains of up to 16% on dynamic environments while maintaining a small overhead when migrations do not take place.
Referências
O. Bonorden. Load balancing in the bulk-synchronousparallel setting using process migrations. In 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), pages 1–9. IEEE, 2007.
O. Bonorden, J. Gehweiler, and F. M. auf der Heide. Load balancing strategies in a web computing environment. In Int. Conf. on Parallel Processing and Applied Mathematics (PPAM), pages 839–846, Poland, 2005.
H. Casanova, A. Legrand, and M. Quinson. 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, 2008. IEEE Computer Society.
R. da Rosa Righi, L. L. Pilla, A. Carissimi, P. Navaux, and H.-U. Heiss. Migbsp: A novel migration model for bulksynchronous parallel processes rescheduling. High Performance Computing and Communications, 10th IEEE International Conference on, 0:585–590, 2009.
R. E. De Grande and A. Boukerche. Dynamic balancing of communication and computation load for hla-based simulations on large-scale distributed systems. J. Parallel Distrib. Comput., 71:40–52, January 2011.
C. Du, X.-H. Sun, and M. Wu. Dynamic scheduling with process migration. In CCGRID ’07: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, pages 92–99, 2007. IEEE.
N.-T. Fong, C.-Z. Xu, and L. Y. Wang. Optimal periodic remapping of dynamic bulk synchronous computations. J. Parallel Distrib. Comput., 63:1036–1049, November 2003.
C. Huang, G. Zheng, L. Kale, and S. Kumar. Performance evaluation of adaptive mpi. In PPoPP ’06: Proc. of the eleventh ACMSIGPLAN symposium on Principles and practice of parallel programming, pages 12–21, 2006. ACM Press.
M. Y.-H. Low, W. Liu, and B. Schmidt. 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, 2007.
D. S. Nikolopoulos and C. D. Polychronopoulos. Adaptive scheduling under memory constraints on non-dedicated computational farms. Future Gener. Comput. Syst., 19:505– 519, May 2003.
J.M. Orduna, V. Arnau, A. Ruiz, R. Valero, and J. Duato. On the design of communication-aware task scheduling strategies for heterogeneous systems. In ICPP ’00: Int. Conf. on Parallel Processing, page 391, 2000. IEEE.
J. A. Pascual, J. Navaridas, and J. Miguel-Alonso. Job scheduling strategies for parallel processing. chapter Effects of Topology-Aware Allocation Policies on Scheduling Performance, pages 138–156. Springer-Verlag, Berlin, 2009.
H. Sanjay and S. Vadhiyar. Strategies for rescheduling tightly-coupled parallel applications in multi-cluster grids. Journal of Grid Computing, pages 1–25, 2010. 10.1007/s10723-010-9170-z.
R. Sudarsan and C. Ribbens. Reshape: A framework for dynamic resizing and scheduling of homogeneous applications in a parallel environment. In Parallel Processing, 2007. ICPP 2007. Int. Conference on, page 44, sept. 2007.
S. S. Vadhiyar and J. J. Dongarra. Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257, 2005.
O. Bonorden, J. Gehweiler, and F. M. auf der Heide. Load balancing strategies in a web computing environment. In Int. Conf. on Parallel Processing and Applied Mathematics (PPAM), pages 839–846, Poland, 2005.
H. Casanova, A. Legrand, and M. Quinson. 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, 2008. IEEE Computer Society.
R. da Rosa Righi, L. L. Pilla, A. Carissimi, P. Navaux, and H.-U. Heiss. Migbsp: A novel migration model for bulksynchronous parallel processes rescheduling. High Performance Computing and Communications, 10th IEEE International Conference on, 0:585–590, 2009.
R. E. De Grande and A. Boukerche. Dynamic balancing of communication and computation load for hla-based simulations on large-scale distributed systems. J. Parallel Distrib. Comput., 71:40–52, January 2011.
C. Du, X.-H. Sun, and M. Wu. Dynamic scheduling with process migration. In CCGRID ’07: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, pages 92–99, 2007. IEEE.
N.-T. Fong, C.-Z. Xu, and L. Y. Wang. Optimal periodic remapping of dynamic bulk synchronous computations. J. Parallel Distrib. Comput., 63:1036–1049, November 2003.
C. Huang, G. Zheng, L. Kale, and S. Kumar. Performance evaluation of adaptive mpi. In PPoPP ’06: Proc. of the eleventh ACMSIGPLAN symposium on Principles and practice of parallel programming, pages 12–21, 2006. ACM Press.
M. Y.-H. Low, W. Liu, and B. Schmidt. 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, 2007.
D. S. Nikolopoulos and C. D. Polychronopoulos. Adaptive scheduling under memory constraints on non-dedicated computational farms. Future Gener. Comput. Syst., 19:505– 519, May 2003.
J.M. Orduna, V. Arnau, A. Ruiz, R. Valero, and J. Duato. On the design of communication-aware task scheduling strategies for heterogeneous systems. In ICPP ’00: Int. Conf. on Parallel Processing, page 391, 2000. IEEE.
J. A. Pascual, J. Navaridas, and J. Miguel-Alonso. Job scheduling strategies for parallel processing. chapter Effects of Topology-Aware Allocation Policies on Scheduling Performance, pages 138–156. Springer-Verlag, Berlin, 2009.
H. Sanjay and S. Vadhiyar. Strategies for rescheduling tightly-coupled parallel applications in multi-cluster grids. Journal of Grid Computing, pages 1–25, 2010. 10.1007/s10723-010-9170-z.
R. Sudarsan and C. Ribbens. Reshape: A framework for dynamic resizing and scheduling of homogeneous applications in a parallel environment. In Parallel Processing, 2007. ICPP 2007. Int. Conference on, page 44, sept. 2007.
S. S. Vadhiyar and J. J. Dongarra. Self adaptivity in grid computing: Research articles. Concurr. Comput. : Pract. Exper., 17(2-4):235–257, 2005.
Publicado
26/10/2011
Como Citar
GRAEBIN, Lucas; RIGHI, Rodrigo da Rosa; NAVAUX, Philippe Olivier Alexandre.
Process Migration: Controlling Application and Resource Dynamics by Combining Computation, Communication and Memory Metrics. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 12. , 2011, Vitória.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 105-112.
DOI: https://doi.org/10.5753/wscad.2011.17274.
