Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Cluster Computing
Erschienen in: Cluster Computing 3/2016

01.09.2016

Ant colony based constrained workflow scheduling for heterogeneous computing systems

verfasst von: Somayeh Kianpisheh, Nasrolah Moghadam Charkari, Mehdi Kargahi

Erschienen in: Cluster Computing | Ausgabe 3/2016

Einloggen

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

search-config
loading …

Abstract

The problem of constrained workflow scheduling on heterogeneous computing systems has been of major interest in the recent years. The user requirements are described by defining constraints on the workflow makespan and/or its execution cost. The uncertainty in the activity execution path and the dynamicity in the resource workload may cause some run-time changes of the makespan or cost. To prohibit run-time constraint violation, the system needs robust schedules. In this paper, probability of violation (POV) of constraints is proposed as a criterion for the schedule robustness. An ant colony system is then used to minimize an aggregation of violation of constraints and the POV. Simulation results on real world workflows show the effectiveness of the proposed method in finding feasible schedules. The results also indicate that the proposed method decreases the POV, as well as the expected penalty at run-time.
Vorheriger Artikel Architecture-aware configuration and scheduling of matrix multiplication on asymmetric multicore processors
Nächster Artikel QDR: a QoS-aware data replication algorithm for Data Grids considering security factors

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

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

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"

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
Fußnoten
1
Note that larger workflows may require more computations. Therefore, the lower/upper bounds of makespan and cost becomes greater. Thus, according to (5), for a specific tightness coefficient, higher deadline and budget are assigned.
 
2
Resource contention is the situation that several activities on the critical path be mapped to the same resource.
 
Literatur
1.
Xu, Y., Li, K., Hu, J., Li, K.: A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf. Sci. 270, 255–287 (2014)MathSciNetCrossRefMATH
2.
Khokhar, A., Prasanna, V.K., Shaaban, M., Wang, C.L.: Heterogeneous computing: challenges and opportunities. Computer 26, 18–27 (1993)CrossRef
3.
Hagras, T., Janecek, J.: A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems. Parallel Comput. 31, 653–670 (2005)CrossRefMATH
4.
Tan, M., Siegel, H.J., Antonio, J.K., Alexander, Y.: Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system. IEEE Trans. Parallel Distrib. Syst. 8, 857–871 (1997)CrossRef
5.
Yu, J., Buyya, R.: A taxonomy of workflow management systems for grid computing. J. Grid Comput. 3, 171–200 (2005)CrossRef
6.
Kwok, Y.K., Ishfaq, A.: Static scheduling algorithms for allocating directed task graphs to multiprocessrs. ACM Comput. Surv. 31, 406–471 (1999)CrossRef
7.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)MATH
8.
Delavar, A.G., Aryan, Y.: HSGA: a hybrid heuristic algorithm for workflow scheduling in cloud systems. J. Clust. Comput. 17, 129–137 (2014)CrossRef
9.
Durillo, J.J., Prodan, R.: Multi-objective workflow scheduling in Amazon EC2. J. Clust. Comput. 17, 169–189 (2014)CrossRef
10.
Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13, 260–274 (2002)CrossRef
11.
Yu, Z., Wang, C., Shi, W.: Failure-aware workflow scheduling in cluster environments. J. Clust. Comput. 13, 421–434 (2010)CrossRef
12.
Cao, H., Jin, H., Wu, X., Wu, S., Shi, X.: DAGMap: efficient and dependable scheduling of DAG workflow job in Grid. J. Supercomput. 51, 201–223 (2010)CrossRef
13.
Yuan, Y., Li, X., Wang, Q., Zhu, X.: Deadline division-based heuristic for cost optimization in workflow scheduling. Inf. Sci. 179, 2562–2575 (2009)CrossRefMATH
14.
Abrishami, S., Naghibzadeh, M., Epema, D.H.J.: Deadline-constrained workflow scheduling algorithms for infrastructure as a Service Clouds. Future Gener. Comput. Syst. 29, 158–169 (2013)CrossRef
15.
Ramakrishnan, L., Reed, D.A.: Predictable quality of service atop degradable distributed systems. J. Clust. Comput. 16, 321–334 (2013)CrossRef
16.
Tsiakkouri, E., Sakellariou, R.: Scheduling workflows with budget constraints. In: Workshop on Integrated research in Grid Computing, pp. 189–202 (2005)
17.
Fard, H.M., Prodan, R., Fahringer, T.: Multi-objective list scheduling of workflow applications in distributed computing infrastructures. J. Parallel Distrib. Comput. 74, 2152–2165 (2014)CrossRefMATH
18.
Chen, W.N., Zhang, J.: An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements. IEEE Trans. Syst. Man Cybern. 39, 29–43 (2009)CrossRef
19.
Liu, X., Ni, Z., Wu, Z., Yuan, D., Chen, J., Yang, Y.: A novel general framework for automatic and cost-effective handling of recoverable temporal violations in scientific workflow systems. Syst. Softw. 84, 492–509 (2011)CrossRef
20.
Zeng, L., Veeravalli, B., Li, X.: ScaleStar: budget conscious scheduling precedence-constrained many-task workflow applications in cloud. In: International Conference on Advanced Information Networking and Applications, pp. 534–541 (2012)
21.
Canon, L.C., Jeannot, E.: Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments. IEEE Trans. Parallel Distrib. Syst. 21, 532–546 (2010)CrossRef
22.
Adyanthaya, S., Zhang, Z., Geilen, M., Voeten, J.: Robustness analysis of multiprocessor schedules. In: International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, pp. 9–17 (2014)
23.
Sugavanam, P., Siegel, H.J., Maciejewski, A.A., Oltikar, M., Mehta, A., Pichel, R.: Robust static allocation of resources for independent tasks under makespan and dollar cost constraints. J. Parallel Distrib. Comput. 67, 400–416 (2007)CrossRefMATH
24.
Ferguson, A.D., Bodik, P., Kandula, S., Boutin, E., Fonseca, R.: Jockey: guaranteed job latency in data parallel clusters. In: ACM European Conference on Computer Systems, pp. 99–112 (2012)
25.
Kianpisheh, S., Charkari, N.M.: A grid workflow quality-of-service estimation based on resource availability prediction. J. Supercomput. 67, 496–527 (2014)CrossRef
26.
Briceño, L.D., Smith, J., Siegel, H.J., Maciejewski, A.A., Maxwell, P., Wakefield, R.: Robust static resource allocation of DAGs in a heterogeneous multicore system. J. Parallel Distrib. Comput. 73, 1705–1717 (2013)CrossRef
27.
Boloor, K., Chirkova, R., Salo, T., Viniotis, Y.: Analysis of response time percentile service level agreements in SOA-based applications. In: Global Telecommunications Conference, pp. 1–6 (2011)
28.
Banachowski, S., Wu, J., Brandt, S.A.: Missed deadline notification in best-effort schedulers. In: Electronic Imaging, pp. 123–135 (2004)
29.
Xiao, Z., Ming, Z.: A method of workflow scheduling based on colored Petri nets. Data Knowl. Eng. 70, 230–247 (2011)CrossRef
30.
Wu, Z., Liu, X., Ni, Z., Yuan, D., Yang, Y.: A market-oriented hierarchical scheduling strategy in cloud workflow systems. J. Supercomput. 63, 256–293 (2013)CrossRef
31.
Lin, M., Ding, C.: Parallel genetic algorithms for dvs scheduling of distributed embedded systems. In: High Performance Computing and Communications, pp. 180–191. Springer, Berlin (2007)
32.
Yu, J., Buyya, R., Tham, C.K.: Cost-based scheduling of scientific workflow applications on utility grids. In: International Conference on e-Science and Grid Computing, pp. 140–147 (2005)
33.
Menasce, D.A., Casalicchio, E.: A framework for resource allocation in grid computing. In: International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, pp. 259–267 (2004)
34.
Yu, J., Buyya, R.: Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Sci. Program. 14, 217–230 (2006)
35.
Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Vahi, K., et al.: Mapping abstract complex workflows onto grid environments. Grid Comput. 1, 25–39 (2003)CrossRef
36.
Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C.: Grid information services for distributed resource sharing. In: Symposium on High Performance Distributed Computing, pp. 181–194 (2001)
37.
Smith, W., Foster, I., Taylor, V.: Scheduling with advanced reservations. In: Symposium on Parallel and Distributed Processing, pp. 127–132 (2000)
38.
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol. Comput. 1, 53–66 (1997)CrossRef
39.
Chang, D.-H., Son, J.H., Kim, M.H.: Critical path identification in the context of a workflow. Inform. Softw. Technol. 44, 405–417 (2002)CrossRef
40.
Abrishami, S., Naghibzadeh, M., Epema, D.H.J.: Cost-driven scheduling of grid workflows using partial critical paths. IEEE Trans. Parallel Distrib. Syst. 23, 1400–1414 (2011)CrossRef
41.
42.
Pedemonte, M., Nesmachnow, S., Cancela, H.: A survey on parallel ant colony optimization. Appl. Soft Comput. 11, 5181–5197 (2011)CrossRef
43.
44.
Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., Vahi, K.: Characterizing and profiling scientific workflows. future Gener. Comput. Syst. 29, 682–692 (2013)CrossRef
45.
Ramakrishnan, L., Gannon, D.: A survey of distributed workflow characteristics and resource requirements. Indiana University Technical Report TR671 (2008)
Metadaten
Titel
Ant colony based constrained workflow scheduling for heterogeneous computing systems
verfasst von
Somayeh Kianpisheh
Nasrolah Moghadam Charkari
Mehdi Kargahi
Publikationsdatum
01.09.2016
Verlag
Springer US
Erschienen in
Cluster Computing / Ausgabe 3/2016
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-016-0575-8

Weitere Artikel der Ausgabe 3/2016

Cluster Computing 3/2016 Zur Ausgabe

OriginalPaper

Transportation route optimization with cost object in China

OriginalPaper

Fast fuzzy trajectory clustering strategy based on data summarization and rough approximation

OriginalPaper

P-Aware: a proportional multi-resource scheduling strategy in cloud data center

OriginalPaper

Building associated semantic representation model for the ultra-short microblog text jumping in big data

OriginalPaper

Implementation of context prediction system based on event recurrence time

OriginalPaper

Performance analysis of optical interconnects’ architectures for data center networks