预算约束和截止时间敏感的高能效云工作流调度

张雪峰，杜孝平，王晓健，王 哲

(1.北京赛迪工业和信息化工程监理中心有限公司 信息化管理与咨询部，北京 100048； 2.北京航空航天大学 软件学院，北京 100191；3.湘潭大学 信息工程学院，湖南 湘潭 411105)

0 引 言

工作流由特定序列的相互依赖任务集组成，是建模复杂科学与商业应用的有效工具，需要大规模计算与存储能力支持。云计算作为一种按需资源提供技术，其服务提供商CSPs可以通过互联网以即付即用的方式向云用户分发资源和服务。由于具备弹性、高效、可靠等特点，工作流应用在云端部署与执行拥有其它环境不具备的优势。工作流中的任务将运行于数据中心内物理主机上的虚拟机设备上，此时的工作流任务调度则是必须解决的问题[1]。大规模虚拟化云数据中心在执行任务过程中会消耗大量能源，对环境有害。而数据中心高能量代价又会降低CSPs的收益。因此，设计满足能效的工作流调度方法是降低数据中心能耗的关键。此外，CSPs可提供不同类型具有不同能力和不同代价的虚拟机，而在异构云环境中，用户提交的多数工作流应用具有预算约束和截止时间限制，满足预算约束并降低截止时间违例也是工作流调度面临的问题。

鉴于云数据中心中进行工作流任务调度是具有约束条件的优化问题，本文将分两个阶段完成任务执行，设计一种基于预算约束和截止时间敏感的高能效工作流调度算法。首先根据工作流结构中的最长路径计算任务优先级，并在满足剩余预算的前提下进行一次目标虚拟机的初选；然后在不影响工作流执行跨度和预算约束的前提下，利用动态电压/频率调整机制，将上一阶段生成的任务映射方案的执行时间进行扩展，以便进一步降低工作流的整体执行能耗。基于以上工作，有效实现高能效任务调度。

1 相关研究

近年来，云环境中工作流调度问题已有相关研究。许多工作考虑了同质环境[2-4]，而文献[5,6]中也考虑了异质云环境中预算约束的工作流调度问题，但都忽略了调度时的能耗问题。另一方面，文献[7,8]在截止时间约束下对工作流调度能耗进行了优化，但却忽略了执行代价问题。云工作流调度需要同时着眼于绿色计算和CSPs运营代价的降低。为了解决以上问题，本文将设计一种异质云环境下的工作流调度方法，实现在预算约束下截止时间敏感型任务的高能效调度。

工作流调度也可考虑为不同目标的优化问题，如：最小化执行跨度、提升能效或降低代价等。目前主要有单目标优化和多目标优化两类。文献[9]通过有效调度降低了工作流的执行跨度，而文献[5]则将预算满足度考虑为首要目标。相比而言，文献[6]提出一种公平调度策略，可以同时最小化执行跨度和满足预算约束。文献[10]提出一种进化多目标优化方法，有效降低了执行代价和执行跨度。文献[8]设计了基于DVFS的能效工作流调度算法，可在给定截止时间内调度工作流。文献[7]为同时改进资源利用率、降低能耗和满足截止时间设计了一种新的工作流调度算法。文献[11]则从代价和能效方面优化了科学工作流调度。然而，以上研究中，文献[7,8]没有考虑工作流执行代价，而文献[5,6,12]中虽然考虑预算和执行跨度，又未考虑工作流能耗。与以上工作不同，本文将设计新的调度算法，可以在给定预算内，确保工作流的完成，并降低执行能耗和截止时间违例情况发生。

2 系统模型

2.1 云数据中心模型

云计算环境中的数据中心是一种具有标准化、高密度、模块化特征的大型基础设施。在集中化管理的基础上，支持高负荷，且能耗动态的满足用户需求，同时具有很好的伸缩性。数据中心资源使用是即付即用的，这种模式极大地提供了对工作流模式任务调度环境的支持。假设数据中心由n台异构虚拟机VM构成，表示为V={v1,v2,…,vn}。 每台VMvk的特征属性包括：处理速率pk，单位MIPS；单位时间代价ck。假设数据中心提供x种类型VM，表示为Vtype={τ1,τ2,…,τx}，V中的每台VM属于Vtype中的一种特定类型，且相同类型的VM拥有相同特征属性。

2.2 工作流模型

工作流应用W可表示为有向无环图G(T,E)，T={t1,t2,…,tm} 表示任务集，E表示任务间的有向边集。任务ti的长度为li，单位MI。G(T,E) 的有向边代表任务间的依赖。若在ti与tj间存在有向边，则表明ti是tj的直接前驱，而tj是ti的直接后继。集合pre(ti) 和suc(ti) 分别代表ti的所有直接前驱和直接后继集合。ti与tj间的数据传输时间表示为TTij，取决于任务间的数据传输量及数据中心的内部网络带宽。若ti与tj分配至同一VM上，则TTij=0。Tentry表示工作流中无任一前驱的入口任务集，Texit表示无任一前驱的出口任务集。

ti在VMvk上的执行时间定义为ET(ti,vk)

ET(ti,vk)=li/pk

(1)

ti的最早开始时间EST(ti) 和最早完成时间EFT(ti) 通过如下递归方式计算

(2)

EFT(ti)=EST(ti)+ET(ti,vf(ti))

(3)

式中：f(ti) 和f(tp) 分别表示执行ti和tp的VM索引号。

最迟开始时间LST(ti) 和最迟完成时间LFT(ti) 分别通过如下递归方式计算

(4)

LFT(ti)=LST(ti)+ET(ti,vf(ti))

(5)

式中：Wm,e表示工作流的估计执行跨度makespan，计算为

(6)

Wm,e表示的是假设所有任务调度至最快类型VM上执行时得到的执行跨度，它被考虑为工作流的最小执行跨度makespan。因此，工作流的截止时间WD可作如下定义

WD=α·Wm,min

(7)

式中：α为云用户定义的截止时间因子，且α≥1。

2.3 能量模型

假设云基础设施中的物理主机支持动态电压/频率扩展技术DVFS，每台VM分配一个虚拟CPU vCPU，对应于物理主机一个内核。因此，VMvk∈V可以通过在 [Vk,min,Vk,max] 之间改变电压等级运行在特定的CPU频率上，频率范围为 [fk,min,fk,max]。 VMvk的动态功耗表示为

Pk=K·(Vk,l)2·fk,l

(8)

式中：K为与动态功率相关的常量参数，Vk,l为VMvk在等级l上的供应电压，fk,l为VMvm对应电压Vk,l的CPU频率。则ti在vk上的执行能耗E=PkET(ti,vk)。 故工作流W的总执行能耗为

(9)

VMvk的处理速率pk取决于电压和频率，处于区间 [pk,min,pk,max]。pk,l代表电压/频率组合 (Vk,l,fk,l) 时VM的处理速率。尽管虚拟机在工作时可运行于最大电压等级上，但利用DVFS可以动态的调整其电压和频率，从而提升能效。

在云数据中心内进行工作流调度，需要基于当前数据中心内虚拟机的资源配置和使用状况，将每个工作流任务调度至目标函数最优的虚拟机上执行。尤其在异构虚拟机配置下，任务的调度代价、计算时间都有所不同。尤其是，在任务执行时，会导致物理主机相应能耗时，工作流调度问题将需要理更全面的考虑影响因素，进而设计在约束条件下高能效的调度算法。

2.4 工作流预算约束

任务ti在VMvk上的执行费用代价为

(10)

式中：ck为VMvk的单位时间内的使用代价。则工作流的总执行代价为

(11)

令cτq、pτq,min和pτq,max分别表示类型为τq的虚拟机VM的单位时间代价、最小处理速率和最大处理速率。对于相同类型的虚拟机，则拥有相同的单位时间代价和处理速率范围。即：对于类型为τq的虚拟机vk，单位时间代价ck=cτq， 处理速率范围 [pk,min,pk,max]=[pτq,min,pτq,max]。

对于类型为τq的虚拟机vk，计算其cτq/pτq,max。 工作流调度最小代价Cl的计算方式是：将所有工作流任务调度至拥有最小cτq/pτq,max值的虚拟机类型τq上的所得代价。而最高代价Ch则是将所有工作流任务调度至最大cτq/pτq,max值的虚拟机类型τq执行所得代价。因此，可将工作流预算定义为

BW=Cl+β·(Ch-Cl)

(12)

式中：β为预算因子，且β∈[0,1)。

因此，工作流调度的预算约束为：CW≤BW。

3 工作流调度算法ESDWB

工作流调度算法的目标是在确保预算约束的同时，降低执行能耗和截止时间违例。该问题本质上是NP问题，本文将设计一种启发式算法对其进行求解。

3.1 任务的截止时间、优先级和预算

假设每个任务在最快类型的VM上执行，通过式(4)、式(5)可计算其最迟开始时间LST(ti) 和最迟完成时间LFT(ti)。 因此，可以按比例扩展LFT(ti) 决定任务ti的截止时间D(ti)

D(ti)=α·LFT(ti)

(13)

若每个任务在其截止时间内完成，则可确保工作流整体在截止时间WD内完成。

为了实现待调度任务的选择，以下列方式为任务分配优先级

(14)

式中：ETavg(ti)为所有VM类型上任务执行的平均时间，而优先级Pr(ti)代表ti至出口任务间的最长路径。

为了决定单个任务的预算，引入参数工作流剩余预算SBW。初始SBW设置为BW-Cl。令cmin(ti) 为执行ti的最小代价。则对于第一个调度的任务ti，其预算为

B(ti)=SBW+cmin(ti)

(15)

算法需要为ti选择合适的vk，使得ti在vk上的执行代价c(ti,vk) 在B(ti) 以内。而任务ti调度后，SBW更新为

SBW=SBW-(c(ti,vk)-cmin(ti))

(16)

通过这种方式，调度每个任务后，更新SBW，进而在新的SBW基础上决定下一调度任务的预算。

3.2 ESDWB算法详细设计

本文将提出的截止时间敏感和预算约束的能效工作流调度算法命名为ESDWB，详细过程如算法1所示。ASF(ti,vk) 和AFT(ti,vk) 分别代表ti在vk上的实际开始时间和实际完成时间。为了计算ASF(ti,vk)， 引入PST(ti) 代表ti的可能开始时间，定义为

(17)

这表明只有在所有前驱任务完成并发送数据后，ti才可能执行。ASF(ti,vk) 和AFT(ti,vk) 分别递归定义如下

(18)

式中：Tk,i为ti之前调度至vk上的任务集，tb为ti之前vk上的调度任务

AFT(ti,vk)=AST(ti,vk)+ET(ti,vk)

(19)

因此，工作流的实际执行跨度makespanWm,a和截止时间违例比例可分别计算为

(20)

(21)

ESDWD算法：算法1首先尝试将ti调度至正在执行其前驱任务的VM上(步骤(8)～步骤(18))以避免数据传输时间，从而降低ti的实际完成时间，这同时还有助于减小工作流调度的实际makespanWm,a和截止时间违例比例DV。若ti没有前驱，或存在截止时间违例/预算约束问题，无法进行以上选择，则重新为其选择合适的VM类型，即步骤(9)～步骤(38)。此过程中，需要计算在其截止时间以内完成ti的最小处理速率ps(ti)

(22)

计算ps(ti) 后，即可决定截止时间以内可完成ti的VM类型，将其定义为集合Q。算法1将Q按处理速率升序排列并尝试为ti选择VM类型，越低的速率对应越小的电压和频率，能耗也更低。若Q中的VM类型无法保证任务在预算内完成，则选择违例任务截止时间的VM类型。同时需要选择在其预算内可用的最快VM类型，即步骤(31)～步骤(37)。算法1中，G代表在预算B(ti) 内能够调度ti的VM类型集合，τb为G中最快处理速率的VM成员。通过这种方式，可以计算工作流的实际跨度makespanWm,a。

算法1：ESDWB

输入：工作流W，截止时间WD，预算BW

输出：工作流调度解SW

(1)determine deadlineD(ti) of each tasktiin task setTofWusing Eq.(13)

(2)calculate priorityPr(ti) of each task using Eq.(14)

(3)sort the tasks inTin descending order of their prio-rities

(4)SBW←SBW-Cl,SW←null

(5)foreachti∈Tdo

(6)vf(ti)←null

(7) calculateB(ti) using Eq.(15)

(8)if(pred(ti)≠null)then

(9) sort the tasks inpred(ti) in descending order of the data size to be thansferred toti

(10)foreachtp∈pred(ti)do

(11)vk←vf(tp)

(12)if((AFT(ti,vk)≤D(ti) && (c(ti,vk)≤B(ti)))then

(13)vf(ti)←vk,SW←SW∪

(14) updateSBWusing Eq.(16)

(15)break

(16)endif

(17)endforeach

(18)endif

(19)if((pred(ti)=null) or (vf(ti)=null))then

(20) computeps(ti) using Eq.(22)

(21)Q←{τq|τq∈Vtype∧(pτq,max≥ps(ti))}

(22) sort the VM type in setQin ascending order of theirpτq,maxvalues

(23)foreachτq∈Qdo

(24) consider an idle or new VMvkof typeτq

(25)if(c(ti,vk)≤B(ti))then

(26)vf(ti)←vk,SW←SW∪

(27) updateSBWusing Eq.(16)

(28)break

(29)endif

(30)endforeach

(31)if(vf(ti)=null)then

(32)G←{τg|τg∈Vtype∧(li/pτg,max×cτg≤B(ti))}

(33)τb←{τg|τg∈G∧(pτg,max≥pτy,max,τy∈G)}

(34) consider an idle or new VMvkof typeτb

(35)vf(ti)←vk,SW←SW∪

(36) updateSBWusing Eq.(16)

(37)endif

(38)endif

(39)endforeach

(40)calculate actual makespan of workflowWm,ausing Eq.(20)

(41)SW←ERT(SW,Wm,a)//调用算法2

(42)calculate energyEWand costCWusing Eq.(9) and Eq.(11)

(43)calculate Deadline violationDVusing Eq.(21)

(44)returnSW

算法2的作用是在不影响工作流W执行跨度和预算约束下的情况下，利用DVFS扩展前一阶段的任务完成时间以降低能耗。其中，ExFT(ti) 为ti的扩展完成时间，定义为

(23)

上式表明ti的扩展完成时间并未影响工作流的执行跨度和后继任务的实际开始时间。

若ExFT(ti)大于AFT(ti)，则认为ti拥有松驰时间可以扩展。调度至vk上的ti的完成时间可扩展至其可能的完成时间PExET(ti,vk)

(24)

当决定ti在vk上可能的扩展完成时间时，考虑以下两种情况：

Case2：ti之后无其它任务调度至vk。

在可能的扩展完成时间PExFT(ti,vk) 内在vk上完成ti的最小处理速率pmin(ti,vk) 计算为

(25)

算法2需要寻找速率大于等于pmin(ti,vk) 的可行vk集合PS。满足pk,l=min(PS) 条件将得到最小的能耗。vk执行ti的能耗为

E=(K·(Vk,l)2·fk,l)·(li/pk,l)

(26)

由于处理速率正比于频率，则能耗E∝(Vk,l)2。 由后文表1可知，以于给定的VM类型，电压越低，频率越低，处理速率也越低。因此，需要从PS中选择最小的处理速率，并更新VM的频率，即步骤(8)～步骤(12)，这有助于降低能耗。

算法2：ERT-Energy Reduction of Tasks

输入：工作流调度解SW，工作流实际执行跨度Wm,a

输出：更新后的调度解SW

(1)foreachti∈Tdo

(2)vk←vf(ti)

(3) calculateExFT(ti) using Eq.(23)

(4)if(ExFT(ti)>AFT(ti,vk))then

(5) determinePExFT(ti,vk) using Eq.(24)

(6) calculatepmin(ti,vk) using Eq.(25)

(7)PS←{pk,l|pk,l∈[pk,min,pk,max]∧(pk,l≥pmin(ti,vk))}

(8)pk,l←min(PS),fk,l←frequency corresponding topk,l

(9)ifpk,l

(10) update the frequency of VMvkfromfk,maxtofk,lfor taskti

(11) updateET(ti,vk) andAFT(ti,vk) in the scheduleSW

(12)endif

(13)endif

(14)endforeach

(15)returnSW

4 实验评估

4.1 实验搭建

利用WorkflowSim平台[13]模拟云数据中心模型进行实验仿真。数据中心中虚拟机VM类型有3种Type1、Type2和Type3，3种VM类型分别运行ADM Turion MT-34处理器、AMD Opteron 2218处理器和Intel Xeon E5450处理器。表1给出了3类虚拟机中处理器的处理属性。3种VM类型中每台VM的代价分别为$0.0058/hour、$0.0116/hour和$0.023/hour，这些取值对应于Amazon EC2中按需VM实例的vCPU的利用代价[14]。同时，与Google和Amazon的云服务提供商CSPs类似，将VM的帐单周期定义为最小值1 min，即：VM运行不满1 min依然按1 min收费。假设数据中心内虚拟机间的平均带宽为1 Gps。

利用4种现实科学工作流结构CyberShake、Epigeno-mics、SIPHT和Montage进行仿真测试，科学工作流具体特征见文献[15]。由于截止时间因子α和预算因子β对工作流的截止时间满意度具有较大影响，构建不同的(α,β)取值给合进行实验。对于特定的β值，更大的α可以增加截止时间满意的概率。而对于特定的α值，更大的β可以增加预算满意的概率。通过调整(α,β)，用户可以根据工作流调度的时间和代价的优先考虑在其中进行取舍。

表1 不同处理器的电压/频率配置

为了评估ESDWB算法的性能，将其与两种典型工作流调度算法FBCWS[6]和DEWTS[8]进行对比分析。FBCWS算法在满足用户预算的前提下尝试最小化工作流执行跨度，而DEWTS算法在确保执行跨度在截止时间内的前提下降低工作流调度能耗。

4.2 性能指标

标准化能耗NEC：工作流W调度的标准化能耗NEC定义为

NEC=EW/EW,min

(27)

式中：EW为式(9)计算的工作流W的执行能耗，EW,min为所有算法中获得的最小能耗值。

标准化跨度NM：工作流W调度的标准化跨度定义为

NM=Wm,a/WD

(28)

式中：Wm,a为式(20)计算的工作流实际执行跨度，WD为工作流截止时间。若NM大于1，表明截止时间发生违例。

标准化代价NC：工作流W调度的标准化代价NC定义为

NC=CW/BW

(29)

若NC大于1，表明调度代价超过工作流预算约束。

选择标准化能耗、跨度和代价3个指标进行性能对比的原因在于：对于云数据中心环境中的工作流调度问题而言，调度能耗、跨度和代价3个指标间拥有相互冲突的性质。通常，性能越强的虚拟机可以提升工作流执行效率，降低跨度，但执行代价也越高。而执行能耗又同时与执行时间和虚拟机功率(计算性能)相关。而取标准值后可以统一比较的量纲。3个指标的选取也可以更加全面比较调度算法的综合性能。

4.3 实验分析

图1～图3是仿真实验结果。可以看到，FBCWS算法可以保证执行代价在预算以内，并有效降低执行跨度，但会导致较高能耗。DEWTS算法可以降低能耗并满足工作流截止时间限制，但执行代价增加并超过了预算约束。本文的ESDWB算法可以在预算内有效调度工作流，并同时降低了截止时间违例和执行能耗。同时，ESDWB算法得到的执行跨度基本落入截止时间以内，即使未在截止时间内，也仅是较小的比例，但依然保持了代价在预算以内。对于CyberShake和Epigenomics工作流而言，包含大量任务间的数据传输，而ESDWB算法得到的执行跨度依然小于FBCWS和DEWTS算法，这是由于ESDWB算法会尽可能将存在多数据传输的前驱任务和后继任务调度至相同虚拟机类型上，如此降低了数据传输时间。

此外，ESDWB算法还通过DVFS调整虚拟机的电压和频率，有效实现能效提升。尽管一些情况中ESDWB算法的能耗高于DEWTS算法，但依然低于FBCWS算法。而且，与DEWTS算法不同，ESDWB算法的执行代价从未超过预算约束。因此，综合在能效提升、降低执行跨度和代价方面，本文的ESDWB算法依然是3种算法中表现最好的。

对于不同类型的工作流任务而言，Epigenomics任务以计算密集型为主，Montage任务以I/O密集型为主，对CPU要求不高，SIPHT任务以计算密集型为主，对内存要求较高，而CyberShake任务以数据密集型为主，对计算能力和内存存储均有较高要求。在NEC测试结果上，ESDWS算法在CyberShake和Montage工作流上都得到了最少的能耗，在Epigenomics和SIPHT工作流上略高于DEWTS算法。在NM测试结果上，ESDWS算法在CyberShake和Epigenomics工作流上跨度最小，在SIPHT和Montage工作流上略高。在NC测试结果上，ESDWS算法则在4种工作流类型上都拥有最小的执行代价。综合来看，无论工作流中的任务类型如何变化，ESDWS算法在综合优化调度能耗、执行跨度，尤其是计算代价方面，还是具有更稳定的性能。

5 结束语

本文提出了一种面向截止时间敏感和预算约束的能效云工作流调度算法。算法可以保证调度解代价在预算约束内，并通过有效绽放处理器速率将任务调度至合适的虚拟机上，同时避免任务的截止时间违例。此外，基于DVFS的处理器频率降低还提升的调度能效，降低了数据中心能耗。实验结果验证了算法的性能优势。下一步的研究方向可以探索考虑工作流任务间数据传输代价的工作流调度算法研究问题，也可以从多云模型的角度研究工作流的调度问题。