Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environment

Fei Cao, Michelle Zhu

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

This paper considers a decentralised hybrid algorithm for scheduling scientific workflow applications onto an underlying distributed computing environment with heterogeneous resources for minimum end-to-end delay (EED). Distributed scientific workflow applications modelled as directed acyclic graphs (DAGs) are widely applied to various research areas to enable efficient knowledge discovery by automated data processing. Owing to the NP-hardness of this problem, heuristic algorithms are commonly proposed to achieve the EED. Our algorithm combines iterative critical path search and layer-based priority techniques (HICPP) to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HICPP. Our simulation results illustrate that HICPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

Original languageEnglish
Pages (from-to)324-336
Number of pages13
JournalInternational Journal of High Performance Computing and Networking
Volume8
Issue number4
DOIs
StatePublished - 1 Jan 2015

Fingerprint

Scheduling algorithms
Distributed computer systems
Heuristic algorithms
Data mining
Hardness
Scheduling

Keywords

  • DAG
  • Decentralised
  • Directed acyclic graph
  • Distributed computing
  • Minimum end-to-end delay
  • Workflow mapping and scheduling

Cite this

@article{30f76c28e79d498ca0ddc8808b73d16b,
title = "Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environment",
abstract = "This paper considers a decentralised hybrid algorithm for scheduling scientific workflow applications onto an underlying distributed computing environment with heterogeneous resources for minimum end-to-end delay (EED). Distributed scientific workflow applications modelled as directed acyclic graphs (DAGs) are widely applied to various research areas to enable efficient knowledge discovery by automated data processing. Owing to the NP-hardness of this problem, heuristic algorithms are commonly proposed to achieve the EED. Our algorithm combines iterative critical path search and layer-based priority techniques (HICPP) to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HICPP. Our simulation results illustrate that HICPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.",
keywords = "DAG, Decentralised, Directed acyclic graph, Distributed computing, Minimum end-to-end delay, Workflow mapping and scheduling",
author = "Fei Cao and Michelle Zhu",
year = "2015",
month = "1",
day = "1",
doi = "10.1504/IJHPCN.2015.072783",
language = "English",
volume = "8",
pages = "324--336",
journal = "International Journal of High Performance Computing and Networking",
issn = "1740-0562",
publisher = "Inderscience Enterprises Ltd.",
number = "4",

}

Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environment. / Cao, Fei; Zhu, Michelle.

In: International Journal of High Performance Computing and Networking, Vol. 8, No. 4, 01.01.2015, p. 324-336.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environment

AU - Cao, Fei

AU - Zhu, Michelle

PY - 2015/1/1

Y1 - 2015/1/1

N2 - This paper considers a decentralised hybrid algorithm for scheduling scientific workflow applications onto an underlying distributed computing environment with heterogeneous resources for minimum end-to-end delay (EED). Distributed scientific workflow applications modelled as directed acyclic graphs (DAGs) are widely applied to various research areas to enable efficient knowledge discovery by automated data processing. Owing to the NP-hardness of this problem, heuristic algorithms are commonly proposed to achieve the EED. Our algorithm combines iterative critical path search and layer-based priority techniques (HICPP) to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HICPP. Our simulation results illustrate that HICPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

AB - This paper considers a decentralised hybrid algorithm for scheduling scientific workflow applications onto an underlying distributed computing environment with heterogeneous resources for minimum end-to-end delay (EED). Distributed scientific workflow applications modelled as directed acyclic graphs (DAGs) are widely applied to various research areas to enable efficient knowledge discovery by automated data processing. Owing to the NP-hardness of this problem, heuristic algorithms are commonly proposed to achieve the EED. Our algorithm combines iterative critical path search and layer-based priority techniques (HICPP) to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HICPP. Our simulation results illustrate that HICPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

KW - DAG

KW - Decentralised

KW - Directed acyclic graph

KW - Distributed computing

KW - Minimum end-to-end delay

KW - Workflow mapping and scheduling

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

U2 - 10.1504/IJHPCN.2015.072783

DO - 10.1504/IJHPCN.2015.072783

M3 - Article

VL - 8

SP - 324

EP - 336

JO - International Journal of High Performance Computing and Networking

JF - International Journal of High Performance Computing and Networking

SN - 1740-0562

IS - 4

ER -