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

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

作　　者：蒋军强[1,2] 林亚平[1,2] 谢国琪[1] 张世文[1,2] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082 [2]可信系统与网络湖南省重点实验室,湖南大学,长沙410082

出　　处：《计算机研究与发展》2016年第7期1503-1516,共14页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61472125)~~

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]