Modelo BUCMA: Beneficiador de Usuários Conscientes MultiAlgoritmo em grades computacionais

• Geremias Corrêa UDESC
• Maurício A. Pillon UDESC
• Charles C. Miers UDESC

DOI: https://doi.org/10.5753/wscad.2021.18522

Abstract

Computational grids provide on-demand computing resources based on policy-defined allocations implemented in scheduling algorithms. The walltime of a request designates the estimated provisioning time of the tasks, but it is crudely used. We propose BUCMA, a user bonification/punishment multi-algorithm model based on our walltime estimation. In the long term, the objective is to improve the accuracy of submissions, aiming the development of scheduling algorithms which can rely on the walltime value, allowing optimizations in resource scheduling. A simple algorithm is created to verify the model's applicability, in a hipotetic reliable walltime scenario, aiming at performance enhancement. Our model presented constant gains on queue and waiting time, up to 98% in both. Moreover, the algorithm based on the model presented reductions of makespan up to 14,6%, with the worst case in approximately 9%.

References

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.