Algoritmos de Escalonamento Gangue com Estratégias de Migracão em um Ambiente MCMCA
DOI:
https://doi.org/10.22456/2175-2745.79994Keywords:
Sistemas distribuídos, Jobs paralelos, Técnicas de migração, Escalonamento de gangueAbstract
Ao longo da última década, o rápido avanço das tecnologias de rede, hardware e middleware, bem como a sofisticação dos recursos de software contribuíram para o surgimento de novos modelos computacionais. Consequentemente, houve uma capacidade crescente para o uso eficiente e efetivo de recursos distribuídos visando integrá-los, de modo a fornecer um ambiente amplamente distribuído, cuja capacidade computacional podendo ser utilizada para resolver problemas complexos. Os dois aspectos mais desafiadores dos sistemas distribuídos, são o gerenciamento de recursos e o escalonamento de tarefas. Este trabalho contribui para minimizar tais problemáticas: (i) através do uso de técnicas de migração; (ii) a implementação de um ambiente de simulação multicore multicluster com mecanismo de balanceamento de carga, a fim de analisar o sistema em diversos contextos; (iii) implementação e análise dos escalonadores de gangues através de métricas com intuito de medir o desempenho em diferentes situações. Assim, os resultados mostraram um melhor uso dos recursos, implicando na redução de custos operacionaisDownloads
References
SALEHI, M. A. et al. Stochastic-based robust dynamic resource allocation for independent tasks in a heterogeneous computing system. J Parallel Distrib Comput., v. 97, n. 1, p. 96–111, 2016.
KANG, W.; KIM, J. Effective scheduling of grid resources using failure prediction. Comput Inf., v. 35, n. 1, p. 369–390, 2016.
ZAKARYA, M.; GILLAM, L. Energy efficient computing,clusters,gridsandclouds:Ataxonomyand survey. SUSCOM, v. 14, n. 1, p. 13–33, 2017.
LUO, H. et al. A review of job scheduling for grid computing. Application Res of Comput., v. 22, n. 5, p. 16–9, 2005.
COOK, S. A. The complexity of theorem-proving procedures. In: HARRISON, M. A.; BANERJI, R. B.; ULLMAN, J. D. (Ed.). Proceedings of the Third Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM, 1971. (STOC, v. 1).
ULLMAN, J. D. Np-complete scheduling problems. J. Comput. Syst. Sci, v. 10, n. 3, p. 384–393, 1975.
TOPCUOGLU, H.; HARIRI, S.; WU, M. Performance- effective and low complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distributed Systems, v. 13, n. 3, p. 260–274, 2002.
CASAVANT, T. L.; KUHL, J. G. A taxonomy of scheduling in general-purpose distributed computingsystems. IEEE Trans. Softw. Eng., v. 14, n. 2, p. 141–154, 1988.
WIECZOREK, M.; HOHEISEL, A.; PRODAN, R. Towards a general model of the multi-criteria workflow scheduling on the grid. Future Gener. Comput. Syst., v. 25, n. 3, p. 237–256, 2009.
SMANCHAT, S.; VIRIYAPANT, K. Taxonomies of workflow scheduling problem and techniques in the cloud. Future Gener. Comput. Syst., v. 52, n. 3, p. 1–12, 2015.
LOPES,R.V.;MENASCE ,D.Ataxonomyofjob scheduling on distributed computing systems. IEEE Trans. Parallel Distrib. Syst., v. 27, n. 12, p. 3412–3428, 2016.
XHAFA, F.; ABRAHAMB, A. Computational models and heuristic methods for grid scheduling problems. Future Gener Comput Syst., v. 26, n. 4, p. 608–621, 2010.
MA, T. et al. Grid task scheduling: Algorithm review. IETE Technical, v. 28, n. 2, p. 158–167, 2011.
CHATURVEDI, A. K.; SAHU, R. New heuristic for scheduling of independent tasks in computational grid. J Grid Distr Comput., v. 4, n. 3, p. 25–36, 2011.
MISHRA, M. K. et al. A survey on scheduling heuristics in grid computing environment. IJMECS, v. 6, n. 10, p. 57–83, 2014.
WANG, J.; ABU-GHAZALEH, N.; PONOMAREV, D. Controlled contention: Balancing contention and reservation in multicore application scheduling. In: IEEE. 2015 IEEE International Parallel and Distributed Processing Symposium. Hyderabad, India: IEEE, 2015. v. 1, n. 1, p. 946–955.
FEITELSON, D. G. Resampling with feedback – a new paradigm of using workload data. In: Proceedings of the 22nd International Conference on Euro-Par 2016: Parallel Processing - Volume 9833. New York, NY, USA: Springer-Verlag New York, Inc., 2016. v. 9833.
GO ́MEZ-MART ́IN,C.;VEGA-RODR ́IGUEZ,M.A.; GONZA ́LEZ-SA ́NCHEZ,J.-L.Fattenedbackfilling:An improved strategy for job scheduling in parallel systems. Journal of Parallel and Distributed Computing, v. 97, n. 1, p. 69–77, 2016.
OUSTERHOUT, J. K. et al. Scheduling techniques for concurrent systems. v. 82, n. 1, p. 22–30, 1982.
LANGER, T.; OSINSKI, L.; MOTTOK, J. A survey of parallel hard-real time scheduling on task models and scheduling approaches. ARCS 2017, v. 1, n. 1, p. 1–8, 2017.
FEITELSON, D. G.; RUDOLPH, L.; SCHWIE- GELSHOHN, U. Parallel job scheduling - a status report. In: FEITELSON, D. G.; RUDOLPH, L.; SCHWIEGELSHOHN, U. (Ed.). Job Scheduling Strategies for Parallel Processing - 10th International Workshop, JSSPP 20. Berlin, Germany: Springer, 2004. (LNCS, 1).
WANG, X. et al. Multi-cluster load balancing based on process migration. In: XU, M. et al. (Ed.). Proceedings of the 7th International Conference on Advanced Parallel Processing Technologies. Berlin, Heidelberg: Springer-Verlag, 2007. v. 1.
KARATZA, H. D. Performance of gang scheduling strategies in a parallel system. Simul Model Pract Theory, v. 17, n. 2, p. 430–441, 2009.
PAPAZACHOS, Z.; KARATZA, H. D. Performance evaluation of bag of gangs scheduling in a heterogeneous distributed system. J. Syst. Softw., v. 83, n. 8, p. 1346–1354, 2010.
PAPAZACHOS, Z. C.; KARATZA, H. D. Gang scheduling in multi-core clusters implementing migrations. Future Gener. Comput. Syst., v. 27, n. 8, p. 1153–1165, 2011.
MOSCHAKIS, I. A.; KARATZA, H. D. Evaluation of gang scheduling performance and cost in a cloud computing system. J. Supercomput., Kluwer Academic Publishers, v. 59, n. 2, p. 975–992, 2012.
HAO, Y.; WANG, L.; ZHENG, M. An adaptive algorithm for scheduling parallel jobs in meteorological cloud. Know.-Based Syst., v. 98, n. 3, p. 226–240, 2016.
TOMAS, L.; CAMINERO, B.; CARRION, C. Improving grid resource usage: Metrics for measuring fragmentation. In: CCGRID ’12. 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computings. Washington, DC, USA: IEEE Computer Society, 2012. v. 1, n. 1.
GRUDENIC, I.; BOGUNOVIC, N. Analysis of scheduling algorithms for computer clusters. MIPRO 2008, v. 1, n. 1, p. 1–6, 2008.
MANICKAM, V.; ARAVIND, A. A fair and efficient gang scheduling algorithm for multicore processors. In: Wireless Networks and Computational Intelligence. Berlin, Germany: Springer, 2012. (CCIS, 1), p. 467–476.
LIU, X. et al. Scheduling parallel jobs using migration and consolidation in the cloud. Math Probl Eng, v. 2012, n. 1, p. 1, 2012.
PAPAZACHOS, Z. C.; KARATZA, H. D. Gang scheduling in a two-cluster system implementing migrations and periodic feedback. Simul-T Soc Mod Sim, v. 87, n. 12, p. 1021–1031, 2011.
PINTO, F. A. P. et al. Analysis of scheduling algorithms with migration strategies in distributed systems. ICNS 2014, v. 1, n. 1, p. 1–6, 2014.
PINTO, F. A. P. et al. Algorithms scheduling with migration strategies for reducing fragmentation in distributed systems. IEEE LATIN AMERICA TRANSACTIONS, v. 13, n. 3, p. 762–768, 2015.
BUYYA, R.; ABRAMSON, D.; NIMROD, J. G. An architecture for a resource management and scheduling system in a global computational grid. HPCASIA ’05, v. 1, n. 1, p. 283, 2000.
ABDELGADIR, A. T.; PATHAN, A.-S. K.; AHMED, M. On the performance of mpi-openmp on a 12 nodes multi-core cluster. In: XIANG, Y. et al. (Ed.). Proceedings of the 11th International Conference on Algorithms and Architectures for Parallel Processing. Berlin, Heidelberg: Springer-Verlag, 2011. (ICA3PP’11, v. 2), p. 225–234.
HAMID, R. J. W. N.; WILLS, G. B. An architecture for measuring network performance in multi-core multi-cluster architecture (MCMCA). IJCTE, v. 7, n. 1, p. 57–61, 2015.
MAHESWARAN, M. et al. Dynamic matching
and scheduling of a class of independent tasks onto heterogeneous computing systems. In: Proceedings of the Eighth Heterogeneous Computing Workshop. Washington, DC, USA: IEEE Computer Society, 1999. (HCW ’99, 1).
MARSAN, M. A.; BALBO, G.; CONTE, G. Performance Models of Multiprocessor Systems. 1. ed. Cambridge, MA, USA: MIT Press, 1987. v. 1.
GARG, S. K. et al. Double auction-inspired meta-scheduling of parallel applications on global grids. J. Parallel Distrib. Comput., v. 73, n. 4, p. 450–464, 2013.
HOCKNEY, R. The communication challenge for mpp: Intel paragon and meiko cs-2. HPCN, v. 20, n. 3, p. 931–936, 1994.
FUJIWARA, K.; CASANOVA, H. Speed and accuracy of network simulation in the simgrid framework. In: GLYNN, P. (Ed.). Proceedings of the 2Nd International Conference on Performance Evaluation Methodologies and Tools. Brussels, Belgium: ICST, 2007. v. 1, n. 12.
CASANOVA, H. et al. Versatile, scalable, and accurate simulation of distributed applications and platforms. J Parallel Distrib Comput., v. 74, n. 10, p. 2899–2917, 2014.
FEITELSON, D. G. Workload Modeling for Computer Systems Performance Evaluation. 1. ed. New York, NY, USA: Cambridge University Press, 2015. v. 1.
FEITELSON, D. G. Job Scheduling in Multiprogrammed Parallel Systems. Yorktow, USA, 1997.
FEITELSON, D. The Standard Workload Format. 2017. Dispon ́ıvel em: ⟨http://www.cs.huji.ac.il/labs/parallel/ workload/swf.html⟩.
BRAUN, T. et al. A comparison of eleven static heuristics for mapping a class of independenttasks onto heterogeneous distributed computing systems. J. Parallel Distributed Computer, v. 61, n. 6, p. 870–837, 2001.
LIN, H.-C.; RAGHAVENDRA, C. S. An analysis of the join the shortest queue (jsq) policy. ICDCS ’03, v. 1, n. 1, p. 362–366, 1992.
KARATZA, H. D. A simulation-based performance analysis of gang scheduling in a distributed system. In: IEEE, Simulation Symposium, 1999. Proceedings. 32nd Annual. Washington, DC, USA: IEEE Computer Society, 1999. v. 1, n. 1.
VASUPONGAYYA, S.; PRASITSUPPAROTE, A. Extending goal-oriented parallel computer job scheduling policies to heterogeneous systems. J Supercomput., v. 65, n. 3, p. 1223–1241, 2013.
FEITELSON, D. A Survey of Scheduling in Multiprogrammed Parallel Systems. New York, USA: IBM T.J. Watson Research Center, 1994. v. 1. 127 p.
GONZALEZ, J. C. Coordinated Scheduling and Dynamic Performance Analysis in Multiprocessors Systems. Tese (Doutorado) — Universitat Politecnica de Catalunya, Barcelona, Espanha, 2002.
FEITELSON, D. G. Packing schemes for gang scheduling. JSSPP, v. 1162, n. 1, p. 89–110, 1996.
ZHOU, B. B. et al. An efficient resource allocation scheme for gang scheduling. JSSPP, v. 1911, n. 1, p. 74–86, 2000.
SEDGEWICK, R.; WAYNE, K. Algorithms. 4. ed. Boston, USA: Addison-Wesley Professional, 2017. v. 1.
ZHANG, Y.; FRANKE, H.; MOREIRA. The impact of migration on parallel job scheduling for distributed systems. In: BODE, A.; LUDWIG, T.; WISMu ̈LLER, W. K. andRoland (Ed.). Proceedings from the 6th International Euro-Par Conference on Parallel Processing. Berlin, Heidelberg: Springer-Verlag, 2000. (Lecture Notes in Computer Science, v. 1990).
LEUNG, V. J.; SABIN, G.; SADAYAPPAN, P. Parallel job scheduling policies to improve fairness: A case study. ICPP Workshops - IEEE, v. 1, n. 1, p. 346–353, 2010.
TANG, W. et al. Reducing fragmentation on torus-connected supercomputers. In: 2011 IEEE International Parallel Distributed Processing Symposium. Washington, USA: IEEE Computer Society, 2011. v. 1.
TANG, W. et al. Adaptive metric-aware job scheduling for production supercomputers. In: FENG, W. chun;PARASHAR, M. (Ed.). Parallel Processing Workshops (ICPPW), 2012 41st International Conference on. Pittsburgh, USA: IEEE, 2012. v. 1.
BURKIMSHER, A.; BATE, I.; INDRUSIAK, L. S. A
survey of scheduling metrics and an improved ordering policy for list schedulers operating on workloads with dependencies and a wide variation in execution times. Future Gener Comput Syst., v. 29, n. 8, p. 2009–2025, 2012
