带通信开销的DAG工作流费用优化模型与算法

来源：计算机研究与发展杂志2015年第6期北京时间：

作者：郭禾,陈征,于玉龙,王宇新,陈鑫,

摘要：通信开销在云环境中无法忽略，但现有DAG(directedacyclicgraph)工作流费用优化模型大都未考虑任务之间的通信开销，难以在实际云环境中应用.为此，提出带通信开销的工作流费用优化模型CA-DAG(communicationaware-DAG)，并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communicationawarecostoptimization).CACO使用前向一致规则(forwardconsistent，FC)求解工作流的最小完工时间；根据逆向分层策略将任务分层，使费用优化问题从全局转化到局部；采用动态规划方法收集任务在选择服务时产生的零散“时间碎片”，增加任务的费用优化空间，改善费用优化效果.仿真实验结果表明，在考虑通信开销时，CACO费用优化效果较DTL(deadlinetoplevel)，DBL(deadlinebottomlevel)，TCDBL(temporalconsistencydeadlinebottomlevel)都有显著提高.

关键词：通信开销, 费用优化, 工作流, 分层, DAG调度,