Hybrid Scheduling Deadline-Constrained Multi-DAGs Based on Reverse HEFT
Xiu-Jie XU
College of Computer Science
Beijing University of Technology
Beijing, China
College of Management Engineering
Shandong Jianzhu University. Jinan, China
xiujie_xu@163.com
Chuang-Bai XIAO
College of Computer Science
Beijing University of Technology
Beijing, China
xiaocb@bjut.edu.cn
Guo-Zhong TIAN
Department of Computer Information and Engineering
Changzhou Institute of Technology
Changzhou, China
tiangz_bjut@qq.com
Ting SUN
College of Computer Science,
Beijing University of Technology
Beijing, China
971834529@qq.com
Abstract—Scheduling complex DAG (Directed Acyclic Graph)
scientific workflow in the distributed heterogeneous system has
attracted widespread attention. Recent researches about
multiple DAG workflows in heterogeneous system have been
making progress and have solved some problems, but fail to
address and to solve some important problems of scheduling
Deadline-Constrained multi-DAGs sharing a bounded number
of machines in a heterogeneous system. In this work, we
propose a reverse HEFT (Heterogeneous Earliest Finish Time)
scheduling policy, which can quickly get the latest start time
and sub-deadline for each task. Based on the latest start time of
in highest priority tasks in each DAG, we define a new relative
laxity degree metrics for them. By comparing these tasks’
metrics, the current task to be scheduled is chosen and then
mapped to the time slot with the earliest finish time in all
resources. If the resources are not enough, oversaturation can
be rapidly determined in accordance with sub-deadline, and
some DAGs is reasonably discarded and other resources is
chosen. This multi-DAGs scheduling policy select a relative
urgency scheduling task only by a simple calculation without
the remaining tasks pre-scheduling in each DAG scheduling.
The experimental results show that it has a better performance
than other three policies on throughput capacity, waste time
slot ratio and fairness, and time complexity is much lower.
Keywords- Multi-DAGs; deadline constrained; reverse
HEFT; relative laxity degree for sub task; throughout capacity
I.
I
NTRODUCTION
Over the years, scientific workflow problems have
emerged as a paradigm for representing complex distributed
scientific computations. Most scientific workflows can be
composed of a large number of tasks and can be abstracted
as DAG. There are some dependency and parallel
relationship between these tasks. The scheduling problem of
DAG workflow in distributed resources has been widely
studied. The research on single DAG scheduling start earlier
and has been more mature. There are more than 100 kinds
of scheduling schemes and algorithms before 2004 [1].
Among them, the DAG scheduling model and the HEFT
algorithm based on the chain proposed by the famous
scholar Topcuoglu in 2002[2] have been widely accepted. It
is the basic model and method for the general use of
workflow scheduling in grid and cloud computing.
Due to the data transmission delay between the tasks and
unbalanced DAG structure, the idle time slot of a single
DAG tasks is big and resource utilization is low. For
effectively improving these, Honig[3] H.Zhao and [4] first
proposed the scheduling problem of multi-DAGs sharing a
set of distributed resource in 2006. One DAG tasks can use
the idle time slot generated by the other DAG tasks
scheduling on the same distributed resource group. And they
also put forward some solutions to the problems such as the
minimization of the makespan and the fairness of
scheduling. The research in the papers[5,6,7] also made
some improvements on this basis, but these multi-DAGs
scheduling are not considered deadline constraints.
However, only a few studies have been made on the DAG
scheduling with deadline constraints. EDF (Earliest
Deadline First)[8] is the application of the sequential
scheduling method based on the deadline. Learn from EDF
scheme, the papers[9,10] uses the deadline for each DAG to
determine the priority of the task scheduling of multi-DAGs
and can make use of the time slot for the DAG non
precision computing tasks. This method is good for such
DAGs with the similar DAG structure and size. However,
the amount of DAG tasks are different, the deadline is not
enough to respond to the emergency state of DAG. The
MDRS(Relative Strictness of Multi-DAGs with
Deadlines)[11,12] scheduling strategy improved fairness
based on the relative strictness of each DAG. Before a
scheduling task is chosen, HEFT algorithm is used for pre-
scheduling the rest tasks of each DAG. Then calculate the
relative duration of each DAG, the highest rank task in the
most urgent DAG is the task to be scheduled. Thus, each
DAG can disperse the mixed scheduling before deadline
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.77
195
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.77
195
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.77
196