Distributed workflow scheduling under throughput and budget constraints in grid environments

Fei Cao, Michelle M. Zhu, Dabin Ding

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Grids enable sharing, selection and aggregation of geographically distributed resources among various organizations. They are emerging as promising computing paradigms for resource and compute-intensive scientific workflow applications modeled as Directed Acyclic Graph (DAG) with intricate inter-task dependencies. With the growing popularity of real-time applications, streaming workflows continuously produce large quantity of experimental or simulation datasets, which need to be processed in a timely manner subject to certain performance and resource constraints. However, the heterogeneity and dynamics of Grid resources complicate the scheduling of streaming applications. In addition, the commercialization of Grids as a future trend is calling for policies to take resource cost into account while striving to satisfy the users' Quality of Service (QoS) requirements. In this paper, streaming workflow applications are modeled as DAGs. We formulate scheduling problems with two different objectives in mind, namely either maximize the throughput under a budget/cost constraint or minimize the execution cost under a minimum throughput constraint. Two different algorithms named as Budget constrained RATE ( -RATE) and Budget constrained SWAP ( -SWAP) are developed and evaluated under the first objective; Another two algorithms named as Throughput constrained RATE ( -RATE) and Throughput constrained SWAP ( -SWAP) are evaluated under the second objective. Experimental results based on GridSim showed that our algorithms either achieved much lower cost with similar throughput, or higher throughput with similar cost compared with other comparable existing algorithms.

Original languageEnglish
Title of host publicationJob Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers
PublisherSpringer Verlag
Pages62-80
Number of pages19
ISBN (Print)9783662437780
DOIs
StatePublished - 1 Jan 2014
Event17th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2013 - Boston, MA, United States
Duration: 24 May 201424 May 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8429 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2013
CountryUnited States
CityBoston, MA
Period24/05/1424/05/14

Fingerprint

Budget Constraint
Work Flow
Throughput
Scheduling
Grid
Streaming
Resources
Costs
Scientific Workflow
Resource Constraints
Directed Acyclic Graph
High Throughput
Quality of Service
Scheduling Problem
Aggregation
Sharing
Maximise
Paradigm
Quality of service
Real-time

Keywords

  • Grid computing
  • Streaming workflow
  • Task scheduling
  • Throughput and budget

Cite this

Cao, F., Zhu, M. M., & Ding, D. (2014). Distributed workflow scheduling under throughput and budget constraints in grid environments. In Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers (pp. 62-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8429 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-43779-7_4
Cao, Fei ; Zhu, Michelle M. ; Ding, Dabin. / Distributed workflow scheduling under throughput and budget constraints in grid environments. Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers. Springer Verlag, 2014. pp. 62-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cc5a5f69f6d3464c87d03107e182404d,
title = "Distributed workflow scheduling under throughput and budget constraints in grid environments",
abstract = "Grids enable sharing, selection and aggregation of geographically distributed resources among various organizations. They are emerging as promising computing paradigms for resource and compute-intensive scientific workflow applications modeled as Directed Acyclic Graph (DAG) with intricate inter-task dependencies. With the growing popularity of real-time applications, streaming workflows continuously produce large quantity of experimental or simulation datasets, which need to be processed in a timely manner subject to certain performance and resource constraints. However, the heterogeneity and dynamics of Grid resources complicate the scheduling of streaming applications. In addition, the commercialization of Grids as a future trend is calling for policies to take resource cost into account while striving to satisfy the users' Quality of Service (QoS) requirements. In this paper, streaming workflow applications are modeled as DAGs. We formulate scheduling problems with two different objectives in mind, namely either maximize the throughput under a budget/cost constraint or minimize the execution cost under a minimum throughput constraint. Two different algorithms named as Budget constrained RATE ( -RATE) and Budget constrained SWAP ( -SWAP) are developed and evaluated under the first objective; Another two algorithms named as Throughput constrained RATE ( -RATE) and Throughput constrained SWAP ( -SWAP) are evaluated under the second objective. Experimental results based on GridSim showed that our algorithms either achieved much lower cost with similar throughput, or higher throughput with similar cost compared with other comparable existing algorithms.",
keywords = "Grid computing, Streaming workflow, Task scheduling, Throughput and budget",
author = "Fei Cao and Zhu, {Michelle M.} and Dabin Ding",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/978-3-662-43779-7_4",
language = "English",
isbn = "9783662437780",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "62--80",
booktitle = "Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers",

}

Cao, F, Zhu, MM & Ding, D 2014, Distributed workflow scheduling under throughput and budget constraints in grid environments. in Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8429 LNCS, Springer Verlag, pp. 62-80, 17th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2013, Boston, MA, United States, 24/05/14. https://doi.org/10.1007/978-3-662-43779-7_4

Distributed workflow scheduling under throughput and budget constraints in grid environments. / Cao, Fei; Zhu, Michelle M.; Ding, Dabin.

Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers. Springer Verlag, 2014. p. 62-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8429 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Distributed workflow scheduling under throughput and budget constraints in grid environments

AU - Cao, Fei

AU - Zhu, Michelle M.

AU - Ding, Dabin

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Grids enable sharing, selection and aggregation of geographically distributed resources among various organizations. They are emerging as promising computing paradigms for resource and compute-intensive scientific workflow applications modeled as Directed Acyclic Graph (DAG) with intricate inter-task dependencies. With the growing popularity of real-time applications, streaming workflows continuously produce large quantity of experimental or simulation datasets, which need to be processed in a timely manner subject to certain performance and resource constraints. However, the heterogeneity and dynamics of Grid resources complicate the scheduling of streaming applications. In addition, the commercialization of Grids as a future trend is calling for policies to take resource cost into account while striving to satisfy the users' Quality of Service (QoS) requirements. In this paper, streaming workflow applications are modeled as DAGs. We formulate scheduling problems with two different objectives in mind, namely either maximize the throughput under a budget/cost constraint or minimize the execution cost under a minimum throughput constraint. Two different algorithms named as Budget constrained RATE ( -RATE) and Budget constrained SWAP ( -SWAP) are developed and evaluated under the first objective; Another two algorithms named as Throughput constrained RATE ( -RATE) and Throughput constrained SWAP ( -SWAP) are evaluated under the second objective. Experimental results based on GridSim showed that our algorithms either achieved much lower cost with similar throughput, or higher throughput with similar cost compared with other comparable existing algorithms.

AB - Grids enable sharing, selection and aggregation of geographically distributed resources among various organizations. They are emerging as promising computing paradigms for resource and compute-intensive scientific workflow applications modeled as Directed Acyclic Graph (DAG) with intricate inter-task dependencies. With the growing popularity of real-time applications, streaming workflows continuously produce large quantity of experimental or simulation datasets, which need to be processed in a timely manner subject to certain performance and resource constraints. However, the heterogeneity and dynamics of Grid resources complicate the scheduling of streaming applications. In addition, the commercialization of Grids as a future trend is calling for policies to take resource cost into account while striving to satisfy the users' Quality of Service (QoS) requirements. In this paper, streaming workflow applications are modeled as DAGs. We formulate scheduling problems with two different objectives in mind, namely either maximize the throughput under a budget/cost constraint or minimize the execution cost under a minimum throughput constraint. Two different algorithms named as Budget constrained RATE ( -RATE) and Budget constrained SWAP ( -SWAP) are developed and evaluated under the first objective; Another two algorithms named as Throughput constrained RATE ( -RATE) and Throughput constrained SWAP ( -SWAP) are evaluated under the second objective. Experimental results based on GridSim showed that our algorithms either achieved much lower cost with similar throughput, or higher throughput with similar cost compared with other comparable existing algorithms.

KW - Grid computing

KW - Streaming workflow

KW - Task scheduling

KW - Throughput and budget

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

U2 - 10.1007/978-3-662-43779-7_4

DO - 10.1007/978-3-662-43779-7_4

M3 - Conference contribution

AN - SCOPUS:84903642456

SN - 9783662437780

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 62

EP - 80

BT - Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers

PB - Springer Verlag

ER -

Cao F, Zhu MM, Ding D. Distributed workflow scheduling under throughput and budget constraints in grid environments. In Job Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers. Springer Verlag. 2014. p. 62-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-43779-7_4