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工作流性能的前提下,能够有效降低系统的计算和通信能量开销,获得了良好的节能效果。

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