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

来源：计算机应用杂志2015年第11期北京时间：

作者：王宇新, 曹仕杰, 郭禾, 陈征, 陈鑫

单位：1. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024;2. 大连理工大学 软件学院, 辽宁 大连 116024

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

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

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