nach oben

The Journal of Supercomputing

Erschienen in:

22.06.2016

CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud

verfasst von: Arash Deldari, Mahmoud Naghibzadeh, Saeid Abrishami

Erschienen in: The Journal of Supercomputing | Ausgabe 2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Workflows are adopted as a powerful modeling technique to represent diverse applications in different scientific fields as a number of loosely coupled tasks. Given the unique features of cloud technology, the issue of cloud workflow scheduling is a critical research topic. Users can utilize services on the cloud in a pay-as-you-go manner and meet their quality of service (QoS) requirements. In the context of the commercial cloud, execution time and especially execution expenses are considered as two of the most important QoS requirements. On the other hand, the remarkable growth of multicore processor technology has led to the use of these processors by Infrastructure as a Service cloud service providers. Therefore, considering the multicore processing resources on the cloud, in addition to time and cost constraints, makes cloud workflow scheduling even more challenging. In this research, a heuristic workflow scheduling algorithm is proposed that attempts to minimize the execution cost considering a user-defined deadline constraint. The proposed algorithm divides the workflow into a number of clusters and then an extendable and flexible scoring approach chooses the best cluster combinations to achieve the algorithm’s goals. Experimental results demonstrate a great reduction in resource leasing costs while the workflow deadline is met.

Vorheriger Artikel P-SEP: a prolong stable election routing algorithm for energy-limited heterogeneous fog-supported wireless sensor networks

Nächster Artikel Energy efficiency of VM consolidation in IaaS clouds

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

Abrishami S, Naghibzadeh M, Epema DHJ (2012) Cost-driven scheduling of grid workflows using partial critical paths. Parallel Distrib Syst IEEE Trans 23(8):1400–1414CrossRef

Bittencourt LF, Madeira ERM (2011) HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds. J Internet Serv Appl 2(3):207–227CrossRef

Naghibzadeh M (2016) Modeling and scheduling hybrid workflows of tasks and task interaction graphs on the cloud. Future Gen Comput Syst 65. doi:10.1016/j.future.2016.05.029

Deelman E, Singh G, Su M-H, Blythe J, Gil Y, Kesselman C, Mehta G, Vahi K, Berriman GB, Good J (2005) Pegasus: a framework for mapping complex scientific workflows onto distributed systems. Sci Progr 13(3):219–237

Berman F, Casanova H, Chien A, Cooper K, Dail H, Dasgupta A, Deng W, Dongarra J, Johnsson L, Kennedy K (2005) New grid scheduling and rescheduling methods in the GrADS project. Int J Parallel Progr 33(2–3):209–229CrossRef

Wieczorek M, Prodan R, Fahringer T (2005) Scheduling of scientific workflows in the ASKALON grid environment. ACM SIGMOD Rec 34(3):56–62CrossRef

Abrishami S, Naghibzadeh M, Epema DHJ (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Gen Comput Syst 29(1):158–169CrossRef

Abraham A, Buyya R, Nath B (2000) Nature’s heuristics for scheduling jobs on computational grids. In: The 8th IEEE international conference on advanced computing and communications (ADCOM 2000), pp 45–52

Aggarwal AK, Kent RD (2005) An adaptive generalized scheduler for grid applications. In: 19th International symposium on, high performance computing systems and applications, HPCS 2005, pp 188–194

10.

Chang V (2014) An introductory approach to risk visualization as a service. Open J Cloud Comput 1:1–9CrossRef

11.

Chang V (2014) The business intelligence as a service in the cloud. Future Gen Comput Syst 37:512–534CrossRef

12.

Arabnejad H, Barbosa JG (2014) A budget constrained scheduling algorithm for workflow applications. J Grid Comput 12(4):665–679CrossRef

13.

Dougan A, Özgüner F (2005) Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems. Comput J 48(3):300–314CrossRef

14.

Singh G, Kesselman C, Deelman E (2007) A provisioning model and its comparison with best-effort for performance-cost optimization in grids. In: Proceedings of the 16th international symposium on high performance distributed computing, pp 117–126

15.

Su S, Li J, Huang Q, Huang X, Shuang K, Wang J (2013) Cost-efficient task scheduling for executing large programs in the cloud. Parallel Comput 39(4):177–188CrossRef

16.

Szabo C, Kroeger T (2012) Evolving multi-objective strategies for task allocation of scientific workflows on public clouds. In: Evolutionary computation (CEC), IEEE congress on, pp 1–8

17.

Maheswaran M, Ali S, Siegal HJ, Hensgen D, Freund RF (1999) Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems. In: 8th Proceedings on, heterogeneous computing workshop (HCW’99), pp 30–44

18.

Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freund RF (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distrib Comput 59(2):107–131CrossRef

19.

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

20.

Topcuoglu H, Hariri S, Wu M (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel Distrib Syst IEEE Trans 13(3):260–274CrossRef

21.

Sarkar V (1989) Partitioning and scheduling parallel programs for multiprocessors. Pitman, MA, USA Cambridge

22.

Bittencourt LF, Madeira ERM (2008) A performance-oriented adaptive scheduler for dependent tasks on grids. Concurr Comput Pract Exp 20(9):1029–1049CrossRef

23.

Yao G, Ding Y, Jin Y, Hao K (2016) Endocrine-based coevolutionary multi-swarm for multi-objective workflow scheduling in a cloud system. Soft Comput. doi:10.1007/s00500-016-2063-8

24.

Grandinetti L, Pisacane O, Sheikhalishahi M (2013) An approximate \(\epsilon \)-constraint method for a multi-objective job scheduling in the cloud. Future Gen Comput Syst 29(8):1901–1908CrossRef

25.

Chang W-L, Ren T-T, Feng M (2015) Quantum algorithms and mathematical formulations of biomolecular solutions of the vertex cover problem in the finite-dimensional hilbert space. NanoBiosci IEEE Trans 14(1):121–128CrossRef

26.

Aggarwal M, Kent RD, Ngom A (2005) Genetic algorithm based scheduler for computational grids. In: 19th International symposium on, high performance computing systems and applications, HPCS 2005, pp 209–215

27.

Alhusaini AH, Prasanna VK, Raghavendra CS (1999) A unified resource scheduling framework for heterogeneous computing environments. In: 8th Proceedings on, heterogeneous computing workshop (HCW’99), pp 156–165

28.

Bajaj R, Agrawal DP (2004) Improving scheduling of tasks in a heterogeneous environment. Parallel Distrib Syst IEEE Trans 15(2):107–118CrossRef

29.

Yu J, Ramamohanarao K, Buyya R (2009) Deadline/budget-based scheduling of workflows on utility grids. In: Buyya R, Bubendorfer K (eds) Market-oriented grid and utility computing. Wiley, Hoboken, pp 427–450

30.

Zheng W, Sakellariou R (2013) Budget-deadline constrained workflow planning for admission control. J Grid Comput 11(4):633–651CrossRef

31.

Yang T, Gerasoulis A (1994) DSC: scheduling parallel tasks on an unbounded number of processors. Parallel Distrib Syst IEEE Trans 5(9):951–967CrossRef

32.

Bittencourt LF, Madeira ERM (2010) Towards the scheduling of multiple workflows on computational grids. J Grid Comput 8(3):419–441CrossRef

33.

Garg SK, Yeo CS, Anandasivam A, Buyya R (2011) Environment-conscious scheduling of HPC applications on distributed cloud-oriented data centers. J Parallel Distrib Comput 71(6):732–749CrossRefMATH

34.

Beloglazov A, Abawajy J, Buyya R (2012) Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future Gen Comput Syst 28(5):755–768CrossRef

35.

Younge AJ, Von Laszewski G, Wang L, Lopez-Alarcon S, Carithers W (2010) Efficient resource management for cloud computing environments. In: Green computing conference international, pp 357–364

36.

Nathani A, Chaudhary S, Somani G (2012) Policy based resource allocation in IaaS cloud. Future Gen Comput Syst 28(1):94–103CrossRef

37.

Wang W, Zeng G, Tang D, Yao J (2012) Cloud-DLS: dynamic trusted scheduling for cloud computing. Expert Syst Appl 39(3):2321–2329CrossRef

38.

Frîncu ME (2014) Scheduling highly available applications on cloud environments. Future Gen Comput Syst 32:138–153CrossRef

39.

Malawski M, Juve G, Deelman E, Nabrzyski J (2012) Cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds. In: Proceedings of the international conference on high performance computing, storage and analysis, networking, p 22

40.

Abrishami S, Naghibzadeh M (2011) Budget constrained scheduling of grid workflows using partial critical paths. In: World congress in computer science, computer engineering, and applied computing (WORLDCOMP’11)

41.

Poola D, Garg SK, Buyya R, Yang Y, Ramamohanarao K (2014) Robust scheduling of scientific workflows with deadline and budget constraints in clouds. In: The 28th IEEE international conference on advanced information networking and applications (AINA-2014), pp 1–8

42.

Deelman E, Gannon D, Shields M, Taylor I (2009) Workflows and e-Science: an overview of workflow system features and capabilities. Future Gen Comput Syst 25(5):528–540CrossRef

43.

Yu J, Buyya R (2005) A taxonomy of workflow management systems for grid computing. J Grid Comput 3(3–4):171–200CrossRef

44.

Bharathi S, Chervenak A, Deelman E, Mehta G, Su M-H, Vahi K (2008) Characterization of scientific workflows. In: Workflows in support of large-scale science, WORKS 2008, 3 Workshop on, pp 1–10

Titel: CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud
verfasst von: Arash Deldari
Mahmoud Naghibzadeh
Saeid Abrishami
Publikationsdatum: 22.06.2016
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 2/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-016-1789-5

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 2/2017

Highly scalable implementation of an implicit matrix-free solver for gas dynamics on GPU-accelerated clusters

P-SEP: a prolong stable election routing algorithm for energy-limited heterogeneous fog-supported wireless sensor networks

A GPU-accelerated real-time contextual awareness application for the visually impaired on Google’s project Tango device

Parallel computing technologies 2016

On the iota-delta function: a link between cellular automata and partial differential equations for modeling advection–dispersion from a constant source

Hierarchical redesign of classic MPI reduction algorithms