Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing
Workflow is a common model to represent large computations composed of dependent tasks. Most existing workflow scheduling algorithms use computing resources in a non-multiprogrammed way, by which only one task can run on a service (machine) at a time. In this paper, we study a new workflow schedulin...
Saved in:
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2021
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/150516 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-150516 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1505162021-05-28T06:13:55Z Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing Zhu, Zhaomeng Tang, Xueyan School of Computer Science and Engineering Parallel and Distributed Computing Centre Engineering::Computer science and engineering Infrastructure as a Service Directed Acyclic Graph (DAG) Workflow scheduling Multi-resource packing Workflow is a common model to represent large computations composed of dependent tasks. Most existing workflow scheduling algorithms use computing resources in a non-multiprogrammed way, by which only one task can run on a service (machine) at a time. In this paper, we study a new workflow scheduling model on heterogeneous Infrastructure-as-a-Service (IaaS) platforms, which allows multiple tasks to run concurrently on a virtual machine (VM) according to their multi-resource demands. First, we propose a list-scheduling framework for the new multiprogrammed cloud resource model. In the order of a priority list, this framework gradually appoints tasks the best placements found on both existing and new VMs on the platform. Different task prioritization and placement comparison methods can be employed for different scheduling objectives. To fully exploit the heterogeneity of IaaS platforms, the VMs can be scaled up during the scheduling process. Then, we propose a deadline-constrained workflow scheduling algorithm (called DyDL) based on this framework to optimize the cost of workflow execution. This algorithm prioritizes tasks by their latest start times and appoints tasks the placements which can meet their latest start times and incur the minimal cost increases. Experimental results show that DyDL can achieve significantly better schedules in most test cases compared to several existing deadline-constrained workflow scheduling algorithms. Ministry of Education (MOE) Accepted version This work is supported by Singapore Ministry of Education Academic Research Fund Tier 2 under Grant MOE2013-T2-2-067, and Academic Research Fund Tier 1 under Grant 2017-T1-002-024. 2021-05-28T06:13:55Z 2021-05-28T06:13:55Z 2019 Journal Article Zhu, Z. & Tang, X. (2019). Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing. Future Generation Computer Systems, 101, 880-893. https://dx.doi.org/doi.org/10.1016/j.future.2019.07.043 0167-739X https://hdl.handle.net/10356/150516 doi.org/10.1016/j.future.2019.07.043 101 880 893 en MOE2013-T2-2-067 2017-T1-002-024 Future Generation Computer Systems © 2019 Elsevier B.V. All rights reserved. This paper was published in Future Generation Computer Systems and is made available with permission of Elsevier B.V. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering Infrastructure as a Service Directed Acyclic Graph (DAG) Workflow scheduling Multi-resource packing |
spellingShingle |
Engineering::Computer science and engineering Infrastructure as a Service Directed Acyclic Graph (DAG) Workflow scheduling Multi-resource packing Zhu, Zhaomeng Tang, Xueyan Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
description |
Workflow is a common model to represent large computations composed of dependent tasks. Most existing workflow scheduling algorithms use computing resources in a non-multiprogrammed way, by which only one task can run on a service (machine) at a time. In this paper, we study a new workflow scheduling model on heterogeneous Infrastructure-as-a-Service (IaaS) platforms, which allows multiple tasks to run concurrently on a virtual machine (VM) according to their multi-resource demands. First, we propose a list-scheduling framework for the new multiprogrammed cloud resource model. In the order of a priority list, this framework gradually appoints tasks the best placements found on both existing and new VMs on the platform. Different task prioritization and placement comparison methods can be employed for different scheduling objectives. To fully exploit the heterogeneity of IaaS platforms, the VMs can be scaled up during the scheduling process. Then, we propose a deadline-constrained workflow scheduling algorithm (called DyDL) based on this framework to optimize the cost of workflow execution. This algorithm prioritizes tasks by their latest start times and appoints tasks the placements which can meet their latest start times and incur the minimal cost increases. Experimental results show that DyDL can achieve significantly better schedules in most test cases compared to several existing deadline-constrained workflow scheduling algorithms. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Zhu, Zhaomeng Tang, Xueyan |
format |
Article |
author |
Zhu, Zhaomeng Tang, Xueyan |
author_sort |
Zhu, Zhaomeng |
title |
Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
title_short |
Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
title_full |
Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
title_fullStr |
Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
title_full_unstemmed |
Deadline-constrained workflow scheduling in IaaS clouds with multi-resource packing |
title_sort |
deadline-constrained workflow scheduling in iaas clouds with multi-resource packing |
publishDate |
2021 |
url |
https://hdl.handle.net/10356/150516 |
_version_ |
1701270483822968832 |