兼顾费用与公平的带通信开销的多有向无环图调度  

Communication aware multiple directed acyclic graph scheduling considering cost and fairness

作　　者：王宇新[1] 曹仕杰 郭禾[2] 陈征[2] 陈鑫[2] 

机构地区：[1]大连理工大学计算机科学与技术学院,辽宁大连116024 [2]大连理工大学软件学院,辽宁大连116024

出　　处：《计算机应用》2015年第11期3017-3020,3025,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(11372067;61300016)

摘　　要：针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS。CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度。实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%。Multiple Directed Acyclic Graphic （DAG） scheduling algorithms are supposed to take many factors into account, such as execution time, communication overhead, cost and fairness of all DAG. Therefore, in order to increase fairness and reduce cost, a new scheduling strategy CAFS （Communication Aware Fair Scheduling）, based on CA-DAG （ Communication Aware-DAG）, was proposed. Also, a BD （ Backward Difference） rule was introduced to optimize finish time of all DAGs. CAFS is consisted of two parts： the pre-scheduling part adopts CACO （ Communication Aware Cost Optimization） to optimize the total cost, and utilizes the classical fairness algorithm to decide the sequence for scheduling. Based on the sequence the second part schedules all the DAGs using BD rule to reduce the finish time. The simulation results show that CAFS can reduce the finish time without increasing cost and guarantee the fairness, and the average execution time has beenreduced by 19.82%.

关 键 词：多有向无环图调度 通信开销 费用 公平 工作流 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]