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

Mengxia Zhu; Fei Cao; Jia Mi

doi:10.1007/978-3-642-24013-3_12

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

Mengxia Zhu, Fei Cao, Jia Mi

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

3 Scopus citations

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 language	English
Title of host publication	Intelligent Distributed Computing V
Subtitle of host publication	Proceedings of the 5th International Symposium on Intelligent Distributed Computing - IDC 2011, Delft, The Netherlands - October 2011
Editors	Frances M.T. Brazier, Kees Nieuwenhuis, Gregor Pavlin, Martijn Warnier, Costin Badica
Pages	117-127
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-24013-3_12
State	Published - 2011

Publication series

Name	Studies in Computational Intelligence
Volume	382
ISSN (Print)	1860-949X

Access to Document

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

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, Mengxia ; 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 = "Mengxia Zhu and Fei Cao and Jia Mi",

year = "2011",

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, Mengxia; 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 proceeding › Chapter › peer-review

TY - CHAP

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

AU - Zhu, Mengxia

AU - Cao, Fei

AU - Mi, Jia

PY - 2011

Y1 - 2011

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). doi: 10.1007/978-3-642-24013-3_12

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

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this