ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (6): 1400-1408.doi: 10.7544/issn1000-1239.2015.20140205

• 信息安全 • 上一篇    下一篇

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

郭禾1,陈征1,于玉龙1,王宇新2,陈鑫1   

  1. 1(大连理工大学软件学院 辽宁大连 116620);2(大连理工大学计算机科学与技术学院 辽宁大连 116024) (guohe@dlut.edu.cn)
  • 出版日期: 2015-06-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61300016,11372067)

A Communication Aware DAG Workflow Cost Optimization Model and Algorithm

Guo He1, Chen Zheng1, Yu Yulong1, Wang Yuxin2, Chen Xin1   

  1. 1(School of Software, Dalian University of Technology, Dalian, Liaoning 116620);2(School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024)
  • Online: 2015-06-01

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

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

Abstract: Communication overhead can not be neglected in cloud environment. However, without considering communication overhead among tasks, a cost optimization model of DAG(directed acyclic graph) workflow is difficult to apply in the actually cloud environment. Therefore, this paper puts forward a cost optimization model of DAG workflow with communication overhead. In addition, based on the hierarchical algorithm, which distributes the tasks into groups based on levels and schedules them by level, the paper proposes a cost optimization awared communication algorithm (CACO). CACO uses the forward consistent (FC) rules to solve the minimum completion time of the workflow. Also, by using the bottom hierarchical strategy to divide the task into separated layers, CACO transfers the cost optimization problem from the whole to the part. Furthermore, in order to increase the space of cost optimization and improve the results, CACO adopts dynamic programming method to collect discrete “time pieces” that is produced during the selecting services. The simulation results show that, compared with DTL(deadline top level),DBL(deadline bottom level),TCDBL(temporal consistency deadline bottom level), CACO has greatly enhanced the cost optimization effect considering communication overhead.

Key words: communication overhead, cost optimization, workflow, hierarchical, DAG schedule

中图分类号: