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

《云计算环境下多有向无环图工作流节能调度算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、志码：A0引言云计算是近几年兴起的一种网络应用模式，使用者可以按需动态地改变访问的资源和服务的种类及数量［1］。随着众多行业和应用对大规模计算能力及海量数据处理能力不断增长的需求，越来越多的企业选择将工作负载传输到云端处理，因此大规模的云计算数据中心应运而生。然而，由大规模的云计算数据中心带来的能耗也快速增长。例如：2011年美国的数据中心全年的耗能大概为1000亿kWh,相当于74亿美元［2］。云计算数据中心的大量能耗带来的不仅是高额的资金消耗，同时也增加了二氧化碳的排放，对环境造成了一定影响。因此，如何构建绿色的云计算数据中心已成为研究人员关注的热点问题。云计算数据

3、中心节能调度问题中针对并行任务节能调度的研究日益受到众多研究者的关注。现有的针对并行任务调度的能耗优化机制，其主要目标是尽量减少占用资源数目和占用时间，提高资源利用率，以达到整个并行任务集群系统性能和能耗之间的平衡。其调度基础是将所有任务按照依赖关系图的拓扑结构分成多条路径，每个路径上的任务分为一组，分配到一个处理器上执行。而针对于分配后负载轻的处理器，如何合理地在不影响其他处理器工作的前提下将其合并，以节省能耗也日渐成为研究的重点。由于CPU在Idle状态下产生的能耗大约为满负载时能耗的70%,因此如何利用并行任务间的松弛时间(即任务最早开始时间和最晚结束时间的处理器

4、时间空隙，在这段时间内CPU处于Idle状态)也成为对于单台处理器能耗优化的研究重点。文献［3］中提到CPU运行频率在长时间内保持一致的情况下能耗较低，可以通过动态电压频率调整(DynamicVoltageandFrequencyScaling,DVFS)机制降低在松弛时间内CPU的运行频率以达到节省能耗的目的。节能调度(EnergyEfficientScheduling,EES)算法通过DVFS机制，在任务容忍限度下，合理地调整CPU运行频率，降低了处理器能耗开销［4-5］o对于通信密集型任务，由于传输能耗在总能耗中的比重较大，基于DVFS机制的EES算法无法获得良好

5、的节能效果［3］。除了DVFS机制外，在处理器松弛时间内，通过对先驱任务的复制执行，可以减少任务间的传输能耗、缩短任务的总体执行时间，达到整体能耗优化的效果［6-7］,能量感知的处理器合并优化(EnergyAwareDuplicationProcessorReductionOptimizing,EADPRO)算法通过基于能量感知的任务复制方法，启发式地对处理器进行合并，从而实现节省系统能耗的目的［8］。然而大多数的研究只考虑一种任务依赖关系，但在实际情况中，一个处理器集群中存在多种任务依赖关系，若用有向无环图(D让ectedAcyclicGraph,DAG)来表示，则意

6、味着在整个数据中心中存在多种DAG工作流。本文在以上研究基础上，设计了一种针对多DAG工作流的能耗优化方法MREO(MultipleRelationEnergy0ptimizing)o该方法通过合理利用任务间的松弛时间，减少服务器使用数目和传输能耗来降低系统总能量，减少服务器使用数目和传输能耗来降低系统总能量开销。对于合并后残留的松弛时间从通信密集型和计算密集型两种不同的任务类型出发，采用最优的处理方式再对局部能耗进行优化。该方法可以分为两大模块：1)任务合并模块。依照任务的依赖关系确定如何合并处理器，减少处理器使用数目和传输能耗。2)残留松弛时间优化模块。针对合并后残

7、留的松弛时间采用最优的处理方式。基于优先级的调度方法为每一个任务分配一个优先等级，根据优先等级将任务分配到处理器上执行。基于聚类的调度方法将有通信情况的任务划分到一个分组，然后按照分组指派处理机，从而减少处理机间的通信开销。基于复制的调度方法利用处理器的空闲时间，复制执行前驱任务，从而降低前驱任务的通信开销，缩短系统整体的运行时间。文献［9］对不同的DAG工作流调度算法进行了对比研究，其中，异构最早完成时间(HeterogeneousEarliestFinishTime,HEFT)算法是线性规划启发式算法的典型代表。文献［10］通过对HE