nach oben

The Journal of Supercomputing

Erschienen in:

06.07.2020

Task scheduling, resource provisioning, and load balancing on scientific workflows using parallel SARSA reinforcement learning agents and genetic algorithm

verfasst von: Ali Asghari, Mohammad Karim Sohrabi, Farzin Yaghmaee

Erschienen in: The Journal of Supercomputing | Ausgabe 3/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Cloud computing is one of the most popular distributed environments, in which, multiple powerful and heterogeneous resources are used by different user applications. Task scheduling and resource provisioning are two important challenges of cloud environment, called cloud resource management. Resource management is a major problem especially for scientific workflows due to their heavy calculations and dependency between their operations. Several algorithms and methods have been developed to manage cloud resources. In this paper, the combination of state-action-reward-state-action learning and genetic algorithm is used to manage cloud resources. At the first step, the intelligent agents schedule the tasks during the learning process by exploring the workflow. Then, in the resource provisioning step, each resource is assigned to an agent, and its utilization is attempted to be maximized in the learning process of its corresponding agent. This is conducted by selecting the most appropriate set of the tasks that maximizes the utilization of the resource. Genetic algorithm is utilized for convergence of the agents of the proposed method, and to achieve global optimization. The fitness function that has been exploited by this genetic algorithm seeks to achieve more efficient resource utilization and better load balancing by observing the deadlines of the tasks. The experimental results show that the proposed algorithm reduces makespan, enhances resource utilization, and improves load balancing, compared to MOHEFT and MCP, the well-known workflow scheduling algorithms of the literature.

Vorheriger Artikel First experiences of teaching quantum computing

Nächster Artikel Multi-spectral remote sensing land-cover classification based on deep learning methods

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Gradwell P, Padget J (2005) Markets vs auctions: approaches to distributed combinatorial resource scheduling. Multiagent Grid Syst 1(4):251–262MATH

Galstyan A, Czajkowski K, Lerman K (2005) Resource allocation in the grid with learning agents. J Grid Comput 3(1–2):91–100

Yeo CS, Buyya R, Pourreza H, Eskicioglu R, Graham P, Sommers F (2006) Cluster computing: high-performance, high-availability, and high-throughput processing on a network of computers. In: Zomaya AY (ed) Handbook of nature-inspired and innovative computing. Springer, Boston, MA, pp 521–551

Armbrust M, Fox A, Griffith R, Joseph AD, Katz R, Konwinski A, Lee G et al (2010) A view of cloud computing. Commun ACM 53(4):50–58

Hameed A, Khoshkbarforoushha A, Ranjan R, Jayaraman PP, Kolodziej J, Balaji P, Zeadally S et al (2016) A survey and taxonomy on energy efficient resource allocation techniques for cloud computing systems. Computing 98(7):751–774MathSciNet

Weingärtner R, Bräscher GB, Westphall CB (2015) Cloud resource management: a survey on forecasting and profiling models. J Netw Comput Appl 47:99–106

Kahanwal D, Singh DTP (2013) The distributed computing paradigms: P2P, grid, cluster, cloud, and jungle. arXiv:1311.3070

Gonzalez NM, de Brito Carvalho TCM, Miers CC (2017) Cloud resource management: towards efficient execution of large-scale scientific applications and workflows on complex infrastructures. J Cloud Comput 6(1):13

Jennings B, Stadler R (2015) Resource management in clouds: survey and research challenges. J Netw Syst Manag 23(3):567–619

10.

Arunarani AR, Manjula D, Sugumaran V (2019) Task scheduling techniques in cloud computing: a literature survey. Future Gen Comput Syst 91:407–415

11.

Kalra M, Singh S (2015) A review of metaheuristic scheduling techniques in cloud computing. Egypt Inform J 16(3):275–295

12.

Rodriguez MA, Buyya R (2018) Scheduling dynamic workloads in multi-tenant scientific workflow as a service platforms. Future Gen Comput Syst 79:739–750

13.

Barker A, Van Hemert J (2007) Scientific workflow: a survey and research directions. In: International Conference on Parallel Processing and Applied Mathematics. Springer, Berlin, Heidelberg, pp 746–753

14.

de Carvalho Silva J, de Oliveira Dantas AB, de Carvalho Junior FH (2019) A scientific workflow management system for orchestration of parallel components in a cloud of large-scale parallel processing services. Sci Comput Program 173:95–127

15.

Malawski M, Juve G, Deelman E, Nabrzyski J (2015) Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds. Future Gen Comput Syst 48:1–18

16.

Zhang Q, Cheng L, Boutaba R (2010) Cloud computing: state-of-the-art and research challenges. J Internet Serv Appl 1(1):7–18

17.

Barto AG, Mahadevan S (2003) Recent advances in hierarchical reinforcement learning. Discrete Event Dyn Syst 13(1–2):41–77MathSciNetMATH

18.

Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York

19.

Asghari A, Sohrabi MK, Yaghmaee F (2020) Online scheduling of dependent tasks of cloud’s workflows to enhance resource utilization and reduce the makespan using multiple reinforcement learning-based agents. Soft Comput. https://doi.org/10.1007/s00500-020-04931-7CrossRef

20.

Asghari A, Sohrabi MK, Yaghmaee F (2020) A cloud resource management framework for multiple online scientific workflows using cooperative reinforcement learning agents. Comput Netw. https://doi.org/10.1016/j.comnet.2020.107340CrossRef

21.

Xu C-Z, Rao J, Xiangping B (2012) URL: a unified reinforcement learning approach for autonomic cloud management. J Parallel Distrib Comput 72(2):95–105

22.

Duggan M, Duggan J, Howley E, Barrett E (2017) A reinforcement learning approach for the scheduling of live migration from under utilised hosts. Memet Comput 9(4):283–293

23.

Shi B, Zhu H, Yuan H, Shi R, Wang J (2018) Pricing cloud resource based on reinforcement learning in the competing environment. In: International Conference on Cloud Computing. Springer, Cham, pp 158–171

24.

Benifa JVB, Dejey D (2019) RLPAS: reinforcement learning-based proactive auto-scaler for resource provisioning in cloud environment. Mob Netw Appl 24:1348–1363

25.

Orhean AI, Pop F, Raicu I (2018) New scheduling approach using reinforcement learning for heterogeneous distributed systems. J Parallel Distrib Comput 117:292–302

26.

Liu N, Li Z, Xu J, Xu Z, Lin S, Qiu Q, Tang J, Wang Y (2017) A hierarchical framework of cloud resource allocation and power management using deep reinforcement learning. In: 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). IEEE, pp 372–382

27.

Zhang Yu, Yao J, Guan H (2018) Intelligent cloud resource management with deep reinforcement learning. IEEE Cloud Comput 4(6):60–69

28.

Balla HAM, Sheng CG, Weipeng J (2018) Reliability enhancement in cloud computing via optimized job scheduling implementing reinforcement learning algorithm and queuing theory. In: 2018 1st International Conference on Data Intelligence and Security (ICDIS). IEEE, pp 127–130

29.

Peng Z, Cui D, Zuo J, Li Q, Xu B, Lin W (2015) Random task scheduling scheme based on reinforcement learning in cloud computing. Cluster Comput 18(4):1595–1607

30.

Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287MathSciNetMATH

31.

Kwok YK, Ahmad I (1998) Benchmarking the task graph scheduling algorithms. In: Proceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing. IEEE, pp 531–537

32.

Keshanchi B, Souri A, Navimipour NJ (2017) An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. J Syst Softw 124:1–21

33.

Liu C-Y, Zou C-M, Wu P (2014) A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing. In: 2014 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES). IEEE, pp 68–72

34.

Wu S-y, Zhang P, Li F, Gu F, Pan Y (2016) A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems. J Cent South Univ 23(2):421–429

35.

Akbari M, Rashidi H, Alizadeh SH (2017) An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Eng Appl Artif Intell 61:35–46

36.

Wang B, Li J (2016) Load balancing task scheduling based on multi-population genetic algorithm in cloud computing. In: 2016 35th Chinese Control Conference (CCC). IEEE, pp 5261–5266

37.

Beegom ASA, Rajasree MS (2015) Genetic algorithm framework for bi-objective task scheduling in cloud computing systems. In: International Conference on Distributed Computing and Internet Technology. Springer, Cham, pp 356–359

38.

Ahmad SG, Liew CS, Munir EU, Ang TF, Khan SU (2016) A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems. J Parallel Distrib Comput 87:80–90

39.

Page AJ, Keane TM, Naughton TJ (2010) Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J Parallel Distrib Comput 70(7):758–766MATH

40.

Singh S, Chana I (2016) A survey on resource scheduling in cloud computing: issues and challenges. J Grid Comput 14(2):217–264

41.

Manvi SS, Shyam GK (2014) Resource management for Infrastructure as a service (IaaS) in cloud computing: a survey. J Netw Comput Appl 41:424–440

42.

Wu F, Wu Q, Tan Y (2015) Workflow scheduling in cloud: a survey. J Supercomput 71(9):3373–3418

43.

Antonopoulos N, Gillam L (2010) Cloud computing. Springer, LondonMATH

44.

Sutton RS, Barto AG (1998) Reinforcement learning: an introduction. MIT Press, CambridgeMATH

45.

Michalski RS, Carbonell JG, Mitchell TM (eds) (2013) Machine learning: an artificial intelligence approach. Springer, Berlin

46.

Puterman ML (2014) Markov decision processes: discrete stochastic dynamic programming. Wiley, New YorkMATH

47.

Barto AG, Bradtke SJ, Singh SP (1995) Learning to act using real-time dynamic programming. Artif Intell 72(1–2):81–138

48.

Watkins CJCH (1989) Learning from delayed rewards. Ph.D. Diss., King’s College, Cambridge

49.

Rummery GA (1995) Problem solving with reinforcement learning. Ph.D. Diss., University of Cambridge

50.

Rummery GA, Niranjan M (1994) On-line Q-learning using connectionist systems, vol 37. University of Cambridge, Cambridge

51.

John GH (1994) When the best move isn’t optimal: Q-learning with exploration. In: AAAI, p 1464

52.

Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, Cambridge

53.

Konak A, Coit DW, Smith AE (2006) Multi-objective optimization using genetic algorithms: a tutorial. Reliab Eng Syst Saf 91(9):992–1007

54.

Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, OxfordMATH

55.

Sastry K, Goldberg D, Kendall G (2005) Genetic algorithms. In: Burke EK, Kendall G (eds) Search methodologies. Springer, Boston, MA, pp 97–125

56.

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, ReadingMATH

57.

Ghomi EJ, Rahmani AM, Qader NN (2017) Load-balancing algorithms in cloud computing: a survey. J Netw Comput Appl 88:50–71

58.

Xu M, Tian W, Buyya R (2017) A survey on load balancing algorithms for virtual machines placement in cloud computing. Concurr Comput Pract Exp 29(12):e4123

59.

Corazza M, Sangalli A (2015) Q-learning and SARSA: a comparison between two intelligent stochastic control approaches for financial trading. University Ca’Foscari of Venice, Dept. of Economics Research Paper Series No 15

60.

Beale HD, Demuth HB, Hagan MT (1996) Neural network design. PWS, Boston

61.

Myerson RB (2013) Game theory. Harvard University Press, CambridgeMATH

62.

Chang D-H, Son JH, Kim MH (2002) Critical path identification in the context of a workflow. Inf Softw Technol 44(7):405–417

63.

Tong Z, Deng X, Chen H, Mei J, Liu H (2020) QL-HEFT: a novel machine learning scheduling scheme base on cloud computing environment. Neural Comput Appl 32:5553–5570

64.

Patel P, Ranabahu AH, Sheth AP (2009) Service level agreement in cloud computing. In: Proceeding of international conference on object oriented programming, systems, languages and application (Cloud Workshops at OOPSLA09), Orlando, Florida, USA, October 25–29, 2009, pp 212–217

65.

Calheiros RN, Ranjan R, Beloglazov A, De Rose CAF, Buyya R (2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw Pract Exp 41(1):23–50

66.

http://daggenerator.com/#

67.

Rodriguez MA, Buyya R (2017) A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments. Concurr Comput Pract Exp 29(8):e4041

68.

Durillo JJ, Prodan R (2014) Multi-objective workflow scheduling in Amazon EC2. Cluster Comput 17(2):169–189

69.

Vasile M-A, Pop F, Tutueanu R-I, Cristea V, Kołodziej J (2015) Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Gen Comput Syst 51:61–71

Titel: Task scheduling, resource provisioning, and load balancing on scientific workflows using parallel SARSA reinforcement learning agents and genetic algorithm
verfasst von: Ali Asghari
Mohammad Karim Sohrabi
Farzin Yaghmaee
Publikationsdatum: 06.07.2020
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 3/2021
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03364-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2021

A convolutional autoencoder-based approach with batch normalization for energy disaggregation

First experiences of teaching quantum computing

Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problem

An event-based approach for formally verifying runtime adaptive real-time systems

Image enhancement using deep-learning fully connected neural network mean filter

Adaptive neuro-fuzzy modeling of a soft finger-like actuator for cyber-physical industrial systems