Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (09): 2410-2415.DOI: 10.11772/j.issn.1001-9081.2013.09.2428

• Network and distributed techno • Previous Articles     Next Articles

Energy efficient scheduling for multiple directed acyclic graph in cloud computing

LIU Danqi1,YU Jiong2,Ying Changtian1   

  1. 1. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 834000, China
    2. School of Software, Xinjiang University, Urumqi Xinjiang 834000, China
  • Received:2013-03-12 Revised:2013-04-26 Online:2013-10-18 Published:2013-09-01
  • Contact: LIU Danqi

云计算环境下多有向无环图工作流的节能调度算法

刘丹琦1,于炯2,英昌甜1   

  1. 1. 新疆大学 信息科学与工程学院,乌鲁木齐 834000
    2. 新疆大学 软件学院,乌鲁木齐 834000
  • 通讯作者: 刘丹琦
  • 作者简介:刘丹琦(1988-),女,新疆克拉玛依人,硕士研究生,主要研究方向:云计算、绿色计算;
    于炯(1964-),男,北京人,教授,博士生导师,博士,主要研究方向:分布式与网格计算、网络安全;
    英昌甜(1989-),女,新疆乌鲁木齐人,博士研究生,主要研究方向:数据库、网格调度算法。
  • 基金资助:

    国家自然科学基金资助项目;国家自然科学基金资助项目

Abstract: Energy-efficient scheduling algorithms based on multiple Directed Acyclic Graph (DAG) fail to save energy efficiently, have a narrow application scope and cannot take performance optimization into account. In order to solve these problems, Multiple Relation Energy Optimizing (MREO) was proposed for multiple DAG workflows. MREO integrated independent tasks to reduce the number of processors used, on the basis of analyzing the characteristics of computation-intensive and communication-intensive tasks. Backtracking and branch-and-bound algorithm were employed to select the best integration path dynamically and reduce the complexity of the algorithm at the same time. The experimental results demonstrate that MREO can reduce the computation and communication energy cost efficiently and get a good energy saving effect on the premise of guaranteeing the performance of multiple DAG workflows.

Key words: multiple Directed Acyclic Graph (DAG), integration, Energy-Efficient Scheduling (EES), energy consumption

摘要: 针对多有向无环图(DAG)工作流节能调度算法中存在的节能效果不佳、适用范围较窄和无法兼顾性能优化等问题,提出了一种新的多DAG工作流节能调度方法——MREO。MREO在对计算密集型和通信密集型任务特点进行分析的基础上,通过整合独立任务,减少了处理器的数量,并利用回溯和分支限界算法对任务整合路径进行动态的优化选择,有效降低了整合算法的复杂度。实验结果证明,MREO在保证多DAG工作流性能的前提下,能够有效降低系统的计算和通信能量开销,获得了良好的节能效果。

关键词: 多有向无环图, 整合, 节能调度, 能耗

CLC Number: