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...

Full description

Saved in:
Bibliographic Details
Main Authors: Zhu, Zhaomeng, Tang, Xueyan
Other Authors: School of Computer Science and Engineering
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