A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment

Michelle Zhu, Fei Cao, Jia Mi

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)

Abstract

Computing intensive scientific workflows structured as a directed acyclic graph (DAG) are widely applied to various distributed science and engineering applications to enable efficient knowledge discovery by automated data processing. Effective mapping and scheduling the workflow modules to the underlying distributed computing environment with heterogeneous resources for optimal network performance has remained as a challenge and attracted research efforts with many simulations and real experiments carried out in the grid and cloud infrastructures. Due to the computing intractability of this type of optimization problem, heuristic algorithms are commonly proposed to achieve the minimum end-to-end delay (EED) or other objectives such as maximum reliability and stability. In this paper, a Hybrid mapping algorithm combining Recursive Critical Path search and layer-based Priority techniques (HRCPP) is designed and developed to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HRCPP. Our simulation results illustrate that HRCPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

Original languageEnglish
Title of host publicationIntelligent Distributed Computing V
Subtitle of host publicationProceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011
EditorsFrances M.T. Brazier, Kees Nieuwenhuis, Gregor Pavlin, Martijn Warnier, Costin Badica
Pages117-127
Number of pages11
DOIs
StatePublished - 22 Nov 2011

Publication series

NameStudies in Computational Intelligence
Volume382
ISSN (Print)1860-949X

Fingerprint

Scheduling algorithms
Distributed computer systems
Heuristic algorithms
Network performance
Data mining
Scheduling
Experiments

Cite this

Zhu, M., Cao, F., & Mi, J. (2011). A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment. In F. M. T. Brazier, K. Nieuwenhuis, G. Pavlin, M. Warnier, & C. Badica (Eds.), Intelligent Distributed Computing V: Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011 (pp. 117-127). (Studies in Computational Intelligence; Vol. 382). https://doi.org/10.1007/978-3-642-24013-3_12
Zhu, Michelle ; Cao, Fei ; Mi, Jia. / A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment. Intelligent Distributed Computing V: Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011. editor / Frances M.T. Brazier ; Kees Nieuwenhuis ; Gregor Pavlin ; Martijn Warnier ; Costin Badica. 2011. pp. 117-127 (Studies in Computational Intelligence).
@inbook{62549409c26a4bf882d2284c85fcf17c,
title = "A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment",
abstract = "Computing intensive scientific workflows structured as a directed acyclic graph (DAG) are widely applied to various distributed science and engineering applications to enable efficient knowledge discovery by automated data processing. Effective mapping and scheduling the workflow modules to the underlying distributed computing environment with heterogeneous resources for optimal network performance has remained as a challenge and attracted research efforts with many simulations and real experiments carried out in the grid and cloud infrastructures. Due to the computing intractability of this type of optimization problem, heuristic algorithms are commonly proposed to achieve the minimum end-to-end delay (EED) or other objectives such as maximum reliability and stability. In this paper, a Hybrid mapping algorithm combining Recursive Critical Path search and layer-based Priority techniques (HRCPP) is designed and developed to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HRCPP. Our simulation results illustrate that HRCPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.",
author = "Michelle Zhu and Fei Cao and Jia Mi",
year = "2011",
month = "11",
day = "22",
doi = "10.1007/978-3-642-24013-3_12",
language = "English",
isbn = "9783642240126",
series = "Studies in Computational Intelligence",
pages = "117--127",
editor = "Brazier, {Frances M.T.} and Kees Nieuwenhuis and Gregor Pavlin and Martijn Warnier and Costin Badica",
booktitle = "Intelligent Distributed Computing V",

}

Zhu, M, Cao, F & Mi, J 2011, A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment. in FMT Brazier, K Nieuwenhuis, G Pavlin, M Warnier & C Badica (eds), Intelligent Distributed Computing V: Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011. Studies in Computational Intelligence, vol. 382, pp. 117-127. https://doi.org/10.1007/978-3-642-24013-3_12

A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment. / Zhu, Michelle; Cao, Fei; Mi, Jia.

Intelligent Distributed Computing V: Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011. ed. / Frances M.T. Brazier; Kees Nieuwenhuis; Gregor Pavlin; Martijn Warnier; Costin Badica. 2011. p. 117-127 (Studies in Computational Intelligence; Vol. 382).

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment

AU - Zhu, Michelle

AU - Cao, Fei

AU - Mi, Jia

PY - 2011/11/22

Y1 - 2011/11/22

N2 - Computing intensive scientific workflows structured as a directed acyclic graph (DAG) are widely applied to various distributed science and engineering applications to enable efficient knowledge discovery by automated data processing. Effective mapping and scheduling the workflow modules to the underlying distributed computing environment with heterogeneous resources for optimal network performance has remained as a challenge and attracted research efforts with many simulations and real experiments carried out in the grid and cloud infrastructures. Due to the computing intractability of this type of optimization problem, heuristic algorithms are commonly proposed to achieve the minimum end-to-end delay (EED) or other objectives such as maximum reliability and stability. In this paper, a Hybrid mapping algorithm combining Recursive Critical Path search and layer-based Priority techniques (HRCPP) is designed and developed to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HRCPP. Our simulation results illustrate that HRCPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

AB - Computing intensive scientific workflows structured as a directed acyclic graph (DAG) are widely applied to various distributed science and engineering applications to enable efficient knowledge discovery by automated data processing. Effective mapping and scheduling the workflow modules to the underlying distributed computing environment with heterogeneous resources for optimal network performance has remained as a challenge and attracted research efforts with many simulations and real experiments carried out in the grid and cloud infrastructures. Due to the computing intractability of this type of optimization problem, heuristic algorithms are commonly proposed to achieve the minimum end-to-end delay (EED) or other objectives such as maximum reliability and stability. In this paper, a Hybrid mapping algorithm combining Recursive Critical Path search and layer-based Priority techniques (HRCPP) is designed and developed to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HRCPP. Our simulation results illustrate that HRCPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

UR - http://www.scopus.com/inward/record.url?scp=81355123297&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-24013-3_12

DO - 10.1007/978-3-642-24013-3_12

M3 - Chapter

AN - SCOPUS:81355123297

SN - 9783642240126

T3 - Studies in Computational Intelligence

SP - 117

EP - 127

BT - Intelligent Distributed Computing V

A2 - Brazier, Frances M.T.

A2 - Nieuwenhuis, Kees

A2 - Pavlin, Gregor

A2 - Warnier, Martijn

A2 - Badica, Costin

ER -

Zhu M, Cao F, Mi J. A hybrid mapping and scheduling algorithm for distributed workflow applications in a heterogeneous computing environment. In Brazier FMT, Nieuwenhuis K, Pavlin G, Warnier M, Badica C, editors, Intelligent Distributed Computing V: Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011. 2011. p. 117-127. (Studies in Computational Intelligence). https://doi.org/10.1007/978-3-642-24013-3_12