Budget and Deadline Aware e-Science Workflow Scheduling in Clouds

Basic science is becoming ever more computationally intensive, increasing the need for large-scale compute and storage resources, be they within a High Performance Computer cluster, or more recently within the cloud. In most cases, large scale scientific computation is represented as a workflow for...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2019-01, Vol.30 (1), p.29-44
Main Authors: Arabnejad, Vahid, Bubendorfer, Kris, Ng, Bryan
Format: Article
Language:English
Subjects:
Algorithms
budget
Budgeting
Budgets
cloud
Cloud computing
deadline
Dynamic scheduling
Elasticity
Heuristic scheduling
Mapping
Provisioning
Run time (computers)
Schedules
scheduling
Scheduling algorithms
Scientific workflow
Sensitivity analysis
Stability analysis
State of the art
Task analysis
Workflow
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Basic science is becoming ever more computationally intensive, increasing the need for large-scale compute and storage resources, be they within a High Performance Computer cluster, or more recently within the cloud. In most cases, large scale scientific computation is represented as a workflow for scheduling and runtime provisioning. Such scheduling become an even more challenging problem on cloud systems due to the dynamic nature of the cloud, in particular, the elasticity, the pricing models (both static and dynamic), the non-homogeneous resource types, the vast array of services, and virtualization. This mapping of workflow tasks on to a set of provisioned instances is an example of the general scheduling problem and is NP-complete. In addition, we also need to ensure that certain runtime constraints are met - the most typical being the cost of the computation and the time which that computation requires to complete. In this article, we introduce a new heuristic scheduling algorithm, Budget Deadline Aware Scheduling (BDAS), that addresses eScience workflow scheduling under budget and deadline constraints in Infrastructure as a Service (IaaS) clouds. The novelty of our work is satisfying both budget and deadline constraints while introducing a tunable cost-time trade off over heterogeneous instances. In addition, we study the stability and robustness of our algorithm by performing sensitivity analysis. The results demonstrate that overall BDAS finds a viable schedule for more than 40000 test cases accomplishing both defined constraints: budget and deadline. Moreover, our algorithm achieves a 17.0-23.8 percent higher success rate when compared to state of the art algorithms.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2018.2849396