Modelo BUCMA: Beneficiador de Usuários Conscientes MultiAlgoritmo em grades computacionais
Resumo
Grades computacionais fornecem recursos computacionais sob demanda com alocações definidas por políticas implementadas em algoritmos de escalonamento. O walltime de uma requisição designa o tempo de provisionamento estimado das tarefas, mas este é aproveitado precariamente. Este trabalho propõe o BUCMA, um modelo multialgoritmo de bonificação/punição de fila ao usuário com base em suas estimativas de walltime. Com estimativas mais precisas de walltime, entende-se que essa métrica possa ser incluída a algoritmos de escalonamento, permitindo otimizações no escalonamento dos recursos. Para validação, implementou-se um algoritmo de escalonamento simples aplicado a um cenário fictício de walltime confiável. Os resultados preliminares mostram que o modelo criado apresentou ganhos de fila e de tempo de espera constantes e de até 98%, e o algoritmo de escalonamento, reduções do makespan de até 14,6%, com pior caso em aproximadamente 9%.
Referências
Anousha, S. and Ahmadi, M. (2013). An improved min-min task scheduling algorithm in grid computing. In GPC 2013, pages 103–113.
Batia, M. K. (2017). Task scheduling in grid computing: A review. In Advances in Computational Sciences and Technology, pages 1707–1714. ISNN, Research India Publications.
Casagrande, L. (2020). batsim-py 1.0.3. https://pypi.org/project/batsim-py/1.0.3.
Casagrande, L., Koslovski, G., Miers, C. C., and Pillon, M. (2020). DeepScheduling: grid computing job scheduler based on deep reinforcement learning. In The 34-th International Conference on Advanced Information Networking and Applications (AINA-2020).
Colvero, T. A., Dantas, M. A. R., and Cunha, D. P. d. (2005). Ambientes de Clusters e Grids computacionais: Características, facilidades e desafios. I Congresso Sul Brasileiro de Computação.
Corrêa, G. and Pillon, M. A. (2020). BUC: Beneficiador de usuários conscientes em grades. 18ª Escola Regional de Redes de Computadores.
Dong, F. and Akl, S. G. A. (2006). Scheduling algorithms for grid computing: State of the art and open problems. In School of Computing, page 55, Kingston, Ontario.
Dubey, K., Kumar, M., and Sharma, S. C. (2018). Modified HEFT algorithm for task scheduling in cloud enviroment. In 6th International Conference on Smart Computing and Communications, volume 125, pages 725–732, Kurukshetra, India. Procedia Computer Science.
Etminani, K. and Naghibzadeh, M. (2007). A min-min max-min selective algorihtm for grid task scheduling. In 2007 3rd IEEE/IFIP International Conference in Central Asia on Internet, pages 1–7.
Goes, L. F. W., Neto, D. O. G., Ferreira, R., and Cirne, W. (2005). Computação em grade: Conceitos, tecnologias, aplicações e tendências. In Escola Regional de Informática de Minas Gerais.
GRID’5000 (2021). Grid5000. https://www.grid5000.fr/w/Hardware.
Hamscher, V., Schwiegelshohn, U., Streit, A., and Yahyapour, R. (2000). Evaluation of job-scheduling strategies for grid computing. In Grid Computing — GRID 2000, volume 1971, pages 191–202.
Jacob, B., Brown, M., Fukui, K., and Trivedi, N. (2005). Introduction to Grid Computing.
IBM. https://www.redbooks.ibm.com/redbooks/pdfs/sg246778.pdf.
Kokilavani, T. and Amalarethinam, D. I. (2011). Load balanced min-min algorithm for static meta-task scheduling in grid computing. In International Journal of Computer Applications, volume 20. DOI:10.5120/2403-3197.
Mu’alem, A. W. and Feitelson, D. G. (2001). ”Utilization, predictability, workloads, In IEEE and user runtime estimates in scheduling the IBM SP2 with backfilling”. Transactions on Parallel and Distributed Systems, volume 12, pages 529–543.
Poquet, M. (2017). Approche par la simulation pourla gestion de ressources. PhD thesis, Université Grenoble Alpes. https://tel.archives-ouvertes.fr/tel-01757245.
Reis, V. Q. d. (2005). Escalonamento em grids computacionais: estudo de caso. Master’s thesis, USP, São Carlos. https://www.teses.usp.br/teses/disponiveis/55/55134/tde18092006-115903/en.php.
Schwiegelshohn, U. and Yahyapour, R. (1998). Analysis of first-come-first-serve parallel job scheduling. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
Sharma, N. and Atri, S. T. S. (2017). A comparative analysis of min-min and max-min algorithms based on the makespan parameter. International Journal of Advanced Research in Computer Science, 8(3).
Singh, A. B., Bhat, S., Raju, R., and D’Souza, R. (2017). A comparative study of various scheduling algorithms in cloud computing. American Journal of Intelligent Systems, 7(3):68–72.
Batia, M. K. (2017). Task scheduling in grid computing: A review. In Advances in Computational Sciences and Technology, pages 1707–1714. ISNN, Research India Publications.
Casagrande, L. (2020). batsim-py 1.0.3. https://pypi.org/project/batsim-py/1.0.3.
Casagrande, L., Koslovski, G., Miers, C. C., and Pillon, M. (2020). DeepScheduling: grid computing job scheduler based on deep reinforcement learning. In The 34-th International Conference on Advanced Information Networking and Applications (AINA-2020).
Colvero, T. A., Dantas, M. A. R., and Cunha, D. P. d. (2005). Ambientes de Clusters e Grids computacionais: Características, facilidades e desafios. I Congresso Sul Brasileiro de Computação.
Corrêa, G. and Pillon, M. A. (2020). BUC: Beneficiador de usuários conscientes em grades. 18ª Escola Regional de Redes de Computadores.
Dong, F. and Akl, S. G. A. (2006). Scheduling algorithms for grid computing: State of the art and open problems. In School of Computing, page 55, Kingston, Ontario.
Dubey, K., Kumar, M., and Sharma, S. C. (2018). Modified HEFT algorithm for task scheduling in cloud enviroment. In 6th International Conference on Smart Computing and Communications, volume 125, pages 725–732, Kurukshetra, India. Procedia Computer Science.
Etminani, K. and Naghibzadeh, M. (2007). A min-min max-min selective algorihtm for grid task scheduling. In 2007 3rd IEEE/IFIP International Conference in Central Asia on Internet, pages 1–7.
Goes, L. F. W., Neto, D. O. G., Ferreira, R., and Cirne, W. (2005). Computação em grade: Conceitos, tecnologias, aplicações e tendências. In Escola Regional de Informática de Minas Gerais.
GRID’5000 (2021). Grid5000. https://www.grid5000.fr/w/Hardware.
Hamscher, V., Schwiegelshohn, U., Streit, A., and Yahyapour, R. (2000). Evaluation of job-scheduling strategies for grid computing. In Grid Computing — GRID 2000, volume 1971, pages 191–202.
Jacob, B., Brown, M., Fukui, K., and Trivedi, N. (2005). Introduction to Grid Computing.
IBM. https://www.redbooks.ibm.com/redbooks/pdfs/sg246778.pdf.
Kokilavani, T. and Amalarethinam, D. I. (2011). Load balanced min-min algorithm for static meta-task scheduling in grid computing. In International Journal of Computer Applications, volume 20. DOI:10.5120/2403-3197.
Mu’alem, A. W. and Feitelson, D. G. (2001). ”Utilization, predictability, workloads, In IEEE and user runtime estimates in scheduling the IBM SP2 with backfilling”. Transactions on Parallel and Distributed Systems, volume 12, pages 529–543.
Poquet, M. (2017). Approche par la simulation pourla gestion de ressources. PhD thesis, Université Grenoble Alpes. https://tel.archives-ouvertes.fr/tel-01757245.
Reis, V. Q. d. (2005). Escalonamento em grids computacionais: estudo de caso. Master’s thesis, USP, São Carlos. https://www.teses.usp.br/teses/disponiveis/55/55134/tde18092006-115903/en.php.
Schwiegelshohn, U. and Yahyapour, R. (1998). Analysis of first-come-first-serve parallel job scheduling. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
Sharma, N. and Atri, S. T. S. (2017). A comparative analysis of min-min and max-min algorithms based on the makespan parameter. International Journal of Advanced Research in Computer Science, 8(3).
Singh, A. B., Bhat, S., Raju, R., and D’Souza, R. (2017). A comparative study of various scheduling algorithms in cloud computing. American Journal of Intelligent Systems, 7(3):68–72.
Publicado
26/10/2021
Como Citar
CORRÊA, Geremias; PILLON, Maurício A.; MIERS, Charles C..
Modelo BUCMA: Beneficiador de Usuários Conscientes MultiAlgoritmo em grades computacionais. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 22. , 2021, Belo Horizonte.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 180-191.
DOI: https://doi.org/10.5753/wscad.2021.18522.
