ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (6): 1400-1408.doi: 10.7544/issn1000-1239.2015.20140205

Previous Articles     Next Articles

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

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

CLC Number: