ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (7): 1503-1516.doi: 10.7544/issn1000-1239.2016.20160137

所属专题: 2016绿色计算专题

• 系统结构 • 上一篇    下一篇

时间约束的异构分布式系统工作流能耗优化算法

蒋军强1,2,林亚平1,2,谢国琪1,张世文1,2   

  1. 1(湖南大学信息科学与工程学院 长沙 410082); 2(可信系统与网络湖南省重点实验室(湖南大学) 长沙 410082) (jjq@hnu.edu.cn)
  • 出版日期: 2016-07-01
  • 基金资助: 
    国家自然科学基金项目(61472125)

Energy Optimization Heuristic for Deadline-Constrained Workflows in Heterogeneous Distributed Systems

Jiang Junqiang1,2, Lin Yaping1,2, Xie Guoqi1, Zhang Shiwen1,2   

  1. 1(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082);2(Key Laboratory for Dependable System and Networks of Hunan Province (Hunan University), Changsha 410082)
  • Online: 2016-07-01

摘要: 针对现有异构分布式可变电压/频率(dynamic voltage/frequency scaling, DVFS)计算系统下具有时间约束的工作流能耗优化算法易陷入局部最优的问题,提出了一种新的全局能耗优化算法:反向蛙跳全局能耗感知算法,该算法利用工作流下界完成时间和约束时间之间存在的盈余,逐步从约束时间开始,以不同的跃度值向下界完成时间反向蛙跳,在此过程中基于局部最优解的判断不断调整跃度值直至蛙跳终点,同时保留该过程中工作流满足时间约束且任务运行能耗最小的调度序列.在此基础上利用处理器松弛时间回收技术,在保持任务间依赖关系和满足工作流时间约束的前提下,调整处理器运行电压/频率至更低的合适级别上,从而进一步降低工作流运行能耗.实验表明:该算法能显著降低工作流整体能耗,节能优势明显.

关键词: 异构分布式系统, 能耗优化, 时间约束, 工作流, 松弛时间回收

Abstract: Most of existing energy optimization heuristics with deadline constraint for workflows in DVFS-enabled heterogeneous distributed systems usually trap in local optima. In this paper, we propose a new energy optimization heuristic called backward frog-leaping global energy conscious scheduling: BFECS. This algorithm makes full use of surplus time between the lowerbound of the workflow and the constrained deadline. Specifically, it starts from the constrained deadline, and leapfrogs towards the lowerbound of the workflow with different leap interval. During the whole process of leapfrogging, the leap intervals are continually changed according to the locally optimal value until the endpoint of leapfrogging is reached; the scheduling sequence with least run energy consumption is also saved at the same time. Furthermore, more energy consumption can be reduced by leveraging slack time reclamation technique, and the idle time slots caused by precedence constraints can be assimilated by the tasks through running at a lower and suitable voltage/frequency using DVFS technique, without violating the precedence constraints of the workflow and breaking the deadline. The experimental results show that the proposed algorithm can decrease energy consumption significantly.

Key words: heterogeneous distributed systems, energy optimization, deadline constraint, workflow, slack time reclamation

中图分类号: