Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3017-3020.DOI: 10.11772/j.issn.1001-9081.2015.11.3017

• DPCS 2015 Paper •     Next Articles

Communication aware multiple directed acyclic graph scheduling considering cost and fairness

WANG Yuxin1, CAO Shijie1, GUO He2, CHEN Zheng2, CHEN Xin2   

  1. 1. College of Computer Science and Technology, Dalian University of Technology, Dalian Liaoning 116024, China;
    2. College of Software, Dalian University of Technology, Dalian Liaoning 116620, China
  • Received:2015-06-17 Revised:2015-07-09 Online:2015-11-10 Published:2015-11-13

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

王宇新1, 曹仕杰1, 郭禾2, 陈征2, 陈鑫2   

  1. 1. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024;
    2. 大连理工大学 软件学院, 辽宁 大连 116024
  • 通讯作者: 王宇新(1973-),男,辽宁大连人,副教授,博士,CCF会员,主要研究方向:计算机系统结构、并行计算.
  • 作者简介:曹仕杰(1992-),男,陕西汉中人,硕士研究生,主要研究方向:计算机系统结构、工作流调度; 郭禾(1955-),男,辽宁大连人,教授,主要研究方向:高性能计算、系统结构; 陈征(1989-),女,河南安阳人,硕士研究生,主要研究方向:计算机系统结构; 陈鑫(1983-),男,辽宁锦州人,讲师,博士,主要研究方向:组合优化与调度.
  • 基金资助:
    国家自然科学基金资助项目(11372067,61300016).

Abstract: 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 been reduced by 19.82%.

Key words: multiple directed acyclic graph scheduling, communication overhead, cost, fairness, workflow

摘要: 针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS.CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度.实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%.

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

CLC Number: