Research On Multi-DAG Scheduling Algorithm With Communication Cost

Directed Acyclic Graph(DAG)is a common task scheduling model.In recent years,multiDAG(Directed Acyclic Graph)scheduling problems in heterogeneous environments have attracted the attention of many researchers.Taking into account the large number of computing resources,the communication overhead in the scheduling process cannot be ignored.Based on the original DAG model propose CA-DAG model.Multi-DAG scheduling problem can be divided into two taxonomies,static and dynamic scheduling.In this paper,two scheduling algorithms applied for different application scenarios are proposed to solve the problem of cost optimization in static scheduling and priority decision in dynamic scheduling.Aiming at the scheduling problem of static multi-DAG in heterogeneous computing system,this paper proposes CAFS(Communication Aware Fair Scheduling)to arrange the scheduling order reasonably.CAFS has two stages during scheduling.The pre-scheduling stage wields CACO(Communication Aware Cost Optimization)to solve the optimal service of all tasks and optimize the cost,and leverages the fairness algorithm obtain the fair scheduling order.Reaping the benefits of pre-scheduling stage,the scheduling phase adopts the rule of BD to further optimize the overall completion time.Targeting at the problem of dynamic multi-DAG scheduling,this paper proposes FSDP((Fairness Scheduling with Dynamic Priority for Multi Workflow))to tackle dynamic scheduling problems.To ensure the DAGs with different arrival time can be reasonably and fairly scheduled,FSDP first gives the definition of the urgency of each DAG at the current time.Moreover,a dynamic priority policy is presented on top of urgency.Also,improvements is made to E-Fairness to ensure that the newly arrived DAG can join the scheduling without unnecessary procedures.This paper proposes two scheduling strategies for static and dynamic multi-DAG scheduling problems.The simulation results show that CAFS can optimize the scheduling cost of a set of static DAG with regard to communication overhead,and the rule of BD can further optimize the overall completion time.FSDP can add new-arrived DAG to the current scheduling sequence and arrange the scheduling priority according to its fairness and urgency.