TY - GEN
T1 - Partitioning-based workflow scheduling in clouds
AU - Almi'Ani, Khaled
AU - Lee, Young Choon
PY - 2016/5/19
Y1 - 2016/5/19
N2 - Many applications in science and engineering become increasingly complex and large scale. These applications often consist of a large number of precedence-constrained tasks forming workflows represented by directed acyclic graph (DAG). In recent years, cloud computing has greatly leveraged the elastic and cost-efficient deployment of these applications. However, their effective deployment is largely dependent on the scheduling algorithm adopted. Most existing workflow scheduling algorithms are designed to optimize deadline or budget/cost, i.e., one being the objective and the other being constraint. In this paper, we present the Partitioning-Based Workflow Scheduling (PBWS) algorithm, which liberates the user from explicitly setting the upper bound of deadline and cost. Instead, PBWS adopts a slack parameter that controls the tradeoff point between deadline and cost. In particular, PBWS partitions a workflow into a number of small task graphs (or simply partitions) for which the granularity of such partitions is determined by the slack parameter. Each of these partitions is then matched with the best performing cloud resource in terms of both the overall execution time (makespan) and cost. The size of partitions may change by rearranging tasks between different partitions for the optimization of resource assignment. Our experimental results show that our PBWSalgorithm outperforms two existing algorithms in terms of cost by a large margin with little overhead on makespan.
AB - Many applications in science and engineering become increasingly complex and large scale. These applications often consist of a large number of precedence-constrained tasks forming workflows represented by directed acyclic graph (DAG). In recent years, cloud computing has greatly leveraged the elastic and cost-efficient deployment of these applications. However, their effective deployment is largely dependent on the scheduling algorithm adopted. Most existing workflow scheduling algorithms are designed to optimize deadline or budget/cost, i.e., one being the objective and the other being constraint. In this paper, we present the Partitioning-Based Workflow Scheduling (PBWS) algorithm, which liberates the user from explicitly setting the upper bound of deadline and cost. Instead, PBWS adopts a slack parameter that controls the tradeoff point between deadline and cost. In particular, PBWS partitions a workflow into a number of small task graphs (or simply partitions) for which the granularity of such partitions is determined by the slack parameter. Each of these partitions is then matched with the best performing cloud resource in terms of both the overall execution time (makespan) and cost. The size of partitions may change by rearranging tasks between different partitions for the optimization of resource assignment. Our experimental results show that our PBWSalgorithm outperforms two existing algorithms in terms of cost by a large margin with little overhead on makespan.
UR - http://www.scopus.com/inward/record.url?scp=84988952141&partnerID=8YFLogxK
U2 - 10.1109/AINA.2016.83
DO - 10.1109/AINA.2016.83
M3 - Conference proceeding contribution
AN - SCOPUS:84988952141
SN - 9781509018574
VL - 2016-May
T3 - International Conference on Advanced Information Networking and Applications Proceedings
SP - 645
EP - 652
BT - Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications, IEEE AINA 2016
A2 - Barolli, Leonard
A2 - Takizawa, Makoto
A2 - Enokido, Tomoya
A2 - Jara, Antonio J.
A2 - Bocchi, Yann
PB - Institute of Electrical and Electronics Engineers (IEEE)
CY - Piscataway, NJ
T2 - 30th IEEE International Conference on Advanced Information Networking and Applications, AINA 2016
Y2 - 23 March 2016 through 25 March 2016
ER -