A scheduling algorithm for applications in a cloud computing system with communication changes

doi:10.1111/exsy.12356

2018-11-28

PRE

Xia Shao

Zhiqiang Xie *

DOI：10.1111/exsy.12356

原文链接

原文求助

摘要

En 中文

This paper proposes a scheduling algorithm to solve the problem of task scheduling in a cloud computing system with time-varying communication conditions. This algorithm converts the scheduling problem with communication changes into a directed acyclic graph (DAG) scheduling problem for existing fuzzy communication task nodes, that is, the scheduling problem for a communication-change DAG (CC-DAG). The CC-DAG contains both computation task nodes and communication task nodes. First, this paper proposes a weighted time-series network bandwidth model to solve the indefinite processing time (cost) problem for a fuzzy communication task node. This model can accurately predict the processing time of a fuzzy communication task node. Second, to address the scheduling order problem for the computation task nodes, a dynamic pre-scheduling search strategy (DPSS) is proposed. This strategy computes the essential paths for the pre-scheduling of the computation task nodes based on the actual computation costs (times) of the computation task nodes and the predicted processing costs (times) of the fuzzy communication task nodes during the scheduling process. The computation task node with the longest essential path is scheduled first because its completion time directly influences the completion time of the task graph. Finally, we demonstrate the proposed algorithm via simulation experiments. The experimental results show that the proposed DPSS produced remarkable performance improvement rate on the total execution time that ranges between 11.5% and 21.2%. In view of the experimental results, the proposed algorithm provides better quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than HEFT, PEFT, and CEFT algorithms.

Keyword:

CC-DAG

cloud computing

DPSS

network time series

scheduling algorithm