截止时间约束云工作流调度代价优化遗传算法

余科军，张建州

(1.成都师范学院 计算机科学学院，四川 成都 610000；2.四川大学 计算机学院，四川 成都 610065)

0 引 言

工作流调度广泛应用于各领域中大规模科学与工程问题的建模[1]，其常见定义方式为拥有多个节点和边的有向无循环图DAG形式，图的节点即为任务，边即为任务的依赖关系。由于工作流规模大，任务量多变，云计算的出现为其提供了一种更高效的运行环境。云计算以效用方式提供计算模式[2]，其服务类型包括IaaS、PaaS和SaaS，IaaS以虚拟机VMs形式提供硬件资源，PaaS为用户提供开发及部署环境，SaaS则提供运行于云设施上Web应用，显然，IaaS云环境更加适用于科学工作流调度问题[3,4]。

工作流调度相关研究中，文献[5]提出一种局部关键路径调度算法IC-PCP，可在满足截止时间约束下最小化执行代价。算法优先将处于局部关键路径PCP的所有任务调度至费用最低的VM上，避免了PCP上的通信代价，但算法忽略了VMs的启动和部署时间。文献[6]中的RTC和RCT算法则是分别针对执行时间优先和执行代价优先的工作流调度算法，均属于单目标无约束最优化，不符合云工作流的实际调度特征。文献[7]提出一种约束条件下代价最优化调度PSO算法，算法虽然考虑了云资源提供弹性与异构特征，但仍未解决PSO存在的早熟问题。文献[8]在混合云环境下提出混合整数非线性规化解决工作流调度问题，目标是满足期限约束并最小化执行代价。类似文献[8]，文献[9]提出动态规化算法处理多约束工作流调度问题，但未考虑多类型VMs的提供环境。

本质上，工作流调度是NP-完全问题，即：无法满足工作流的时间依赖约束或无法为任务选择正确的资源类型，这些均可导致过高的服务使用成本。针对这一问题，提出一种满足截止时间约束的工作流调度代价最优化遗传算法CODC-GA，算法通过遗传操作，以尽可能高的约束满意度获得调度代价最小化方案，并通过实际科学工作流测试算法性能。

1 系统模型

1.1 工作流模型

将工作流以有向无循环图DAG表示为W=(T,E)，T=(t1,t2,…,tm) 为任务集合，E为边集，ei,j为任务ti至tj间的有向边，ti,tj∈T且ti≠tj， 即两个任务间的数据依赖关系，任务ti称为tj的父(前驱)任务，任务tj称为ti的子(后继)任务，这种父子约束关系表明只有父任务ti完成后，子任务tj才可以开始执行。通常，工作流DAG拥有单个入口任务tentry和出口任务texit，入口任务不存在父任务，出口任务不存在子任务。如图1为拥有9个任务的工作流，边上的权值表示任务间的数据传输量或传输时间，每个工作流拥有一个执行截止时间约束TD，表示工作流完成的最晚期限。

图1 工作流结构

1.2 云资源模型

(1)

TT(eij)=Data(ti,out)/β

(2)

其中，Size(ti)为任务ti的大小，以浮点运行次数度量，PC(VMk)为VMk的处理能力，以每秒进行的浮点运行次数度量，TT(eij)为任务ti与tj之间数据传输量为Data(ti,out)和带宽为β时的数据传输时间。假设同一云数据中心内部的数据传输宽带是相同的。

1.3 最优化调度

将以上工作流调度问题定义为：寻找给定工作流W的可行调度S，使得总执行时间TET不超过TD的同时，使总执行代价TEC达到最小，即

(3)

式中：Ctype(vmk)为vmk的单位时间间隔的使用成本。

2 CODC-GA算法设计

本文设计了适用于解决云工作流调度的遗传操作，包括：问题编码、种群初始化、交叉与变异，并提出了满足截止时间约束的代价优化遗传算法CODC-GA(cost optimization genetic algorithm under deadline constraint)。

2.1 符号定义

表1给出符号说明及定义。

定义1pred(ti)和succs(ti)。对于任务ti，其前驱任务集和后继任务集分别为

pred(ti)={ti|tj∈T∧(tj,ti)∈E}

(4)

succs(ti)={ti|tj∈T∧(ti,tj)∈E}

(5)

定义2EST(ti)和EFT(ti)。任务的最早开始时间为当所有前驱pred(tp)已经执行且pred(tp)与ti间的输出数据已经传输时，ti在最快VM上的开始执行时间，最早完成时间为任务ti执行完成的时间，分别为

(6)

EFT(ti)=EST(ti)+MET(ti)

(7)

定义3MET(ti)。任务ti的最小执行时间定义为

(8)

定义4MET_W。工作流的最小执行时间定义为

(9)

定义5Lev(ti)。任务ti在DAG中的拓扑分级定义为

(10)

表1 符号说明

定义6ST(ti)和FT(ti)。任务ti的开始时间和完成时间分别定义为

(11)

(12)

定义7Avail(VMk)。如果任务ti是VMk上最后分配的任务，则VMk的就绪时间定义为

(13)

定义8LSTVMk和LETVMk。VMk的租用开始时间即为VMk执行任务的就绪时间，VMk的租用结束时间即为VMk资源提供停止时间。

2.2 问题编码

为了表示工作流调度的染色体形式，引入3个数组：Task2Index、Task2VM和VM2Host，Task2Index为任务索引，即根据任务执行顺序为每个任务分配整数索引，Task2VM为任务-虚拟机映射，即任务被分配至目标虚拟机VM，VM2Host为VM-主机部署，即选择VM的部署目标主机资源池。初始状态下，算法根据工作流的依赖约束寻找可能的任务顺序，然后分配索引(从1至任务最大数量)至每个任务。

一个调度则可由Task2Index、Task2VM和VM2Host这3个数组表示，图1表示的工作流结构对应的一种调度可以图2进行编码，第一行为任务位置(Task2Index)，由任务序列中ti的索引l表示，第二行为对应每个索引l的任务ti所映射的VM(Task2VM)，第三行为任务ti所映射的VM所部署的主机。如：索引5对应的任务t3被映射至VM1，而VM1部署于资源3。

图2 调度方案染色体编码方案

2.3 种群初始化

种群初始化过程为：首先，产生n个有序任务列表List(Oi)={O1,O2,…,On}∈O，n表示CODC-GA的种群大小，每个List(Oi)均包括所有任务， (ti)={t1,t2,…,tm}∈T，m为任务总数。利用图3的方法对所有任务进行排序。方法输入为有序List(Oi)空集和任务 (ti)={t1,t2,…,tm}∈T， 初始状态下，选择一个有序List(Oi)∈O空集，然后，选择任务ti并将ti置入List(Oi)列表尾部，如果ti的所有前驱任务已被添加至List(Oi)或tp∈pred(ti)==∅， 则从T中移除ti，更新T=T-{ti}； 否则，将ti的前驱任务添加至List(Oi)，并重复该过程直到所有任务ti被添加至List(Oi)为止。至此，List(Oi)∈O包含所有任务ti且满足工作流任务间的依赖关系。如果此时仍存在List(Oi)空集，则重复该过程。该过程完成后，可形成n个有序列表List(Oi)，每个List(Oi)中包含满足依赖关系的所有任务 (ti)={t1,t2,…,tm}∈T。

图3 种群初始化

同时，为List(Oi)中的每个任务分配VM时，将任务调度至成本最低的VM上，即产生CODC-GA的初始种群。

2.4 适应度评估

算法产生的调度方案适应度评估方法如图4所示，具体步骤为：输入为染色体(Task2Index,Task2VM,VM2Host)编码、工作流任务总量m及VMs总数量k，然后，对包含VMs的VM_Pool初始化为空、exeTime矩阵、transferTime矩阵、Map、TET和TEC均初始化为0，利用式(1)计算任务在可用VMs上的exeTime[m][k]，利用式(2)计算任务ti与tj间的transferTime[m][m]，从Task2Index中选择索引对应的每个任务ti，将其调度目标选择为Task2VM的VMk上，并利用式(11)和式(12)分别计算任务的开始时间ST(ti)和完成时间FT(ti)。

图4 适应度评估

然后，以开始时间ST(ti)和完成时间FT(ti)将ti调度至VMk，更新包括ti的VMk上的映射Map。计算VMk的租用开始时间LSTVMk和租用结束时间LETVMk。如果该VM不在VM_Pool中，则需要重新VM_Pool；否则，无需更新LSTVMk，租用结束时间LETVMk直接等同于ti的完成时间FT(ti)。重复以上过程直到所有任务被调度。最后，通过式(3)计算TET和TEC。

2.5 遗传算子

(1)交叉操作

算法通过已有的两个父调度间的交叉操作产生新的子调度。首先，考虑两个交叉概率pc为100%的父调度P1和P2，选择[0,1]间的随机值与交叉概率100%比较，如果随机值小于或等于100%，则执行交叉操作，否则，终止交叉。执行交叉时，随机选择两个整数i，j，1≤i≤j≤m，m为任务总量，表示父调度P1中的任务索引。然后，选择父调度P1的索引l∈[i,j]间的所有任务，将这些任务放入子调度C1中，但其任务顺序及相应的Task2VM和VM2Host从父调度P2得到，因此，此时得到的子调度两个索引间j-i+1个任务间依然服从父调度P2中的依赖约束，同时将其它剩余任务(索引l∈(1,…,i-1,j+1,…,m)) 按照在父调度P1中的位置直接拷贝至子调度C1中。同理，父调度P2的子调度C1根据以上同样的方式得到。

以图5为例：在父调度P1上随机选择两个值i=3和j=6，即对应于Task2Index中索引i=3和j=6间的任务为 (t4,t5,t3,t6)， 然后，从父调度P2中选择任务 (t4,t5,t3,t6) (P2中4个任务的执行顺序为 (t3,t4,t6,t5)， 对应VM为 (1,4,3,1)， 对应主机类型为 (2,2,2,1)) 置入子调度中，因此，P1的子调度中索引i=3和j=6间将包括任务 (t4,t5,t3,t6)， 并更改对应VM为 (1,4,3,1)， 对应类型为 (2,2,2,1)。 同时，将在索引1、2、7、8上的剩余任务t1、t2、t7和t8拷贝至子任务C1的对应位置上。父调度P2的子调度C2产生过程可同上得到。

图5 交叉操作

(2)变异操作

算法通过每个任务的拓扑分级保持任务依赖的方式进行变异操作。首先，对于一个新调度，在[0,1]间选择一个随机值，并与变异概率pm比较，决定是否进行变异，将变异概率设置为小于或等于30%。如果随机值小于或等于30%，则执行变异，随机选择两个整数i，j，1≤i≤j≤m，如果lev(Task2Index[i]=lev(Task2Index[j]， 则将Task2Index[i] 与Task2Index[j] 对应的任务进行互换。同时，如果在Task2Index[i] 与Task2Index[j] 间存在索引q对应的任务tl，使得lev(tl)

以图6为例：随机选择两个值i=4和j=6，lev(Task2Index[4]=lev(Task2Index[6]， 将两个索引Task2Index[4]和Task2Index[6]对应的任务t5和t6互换，进一步，由于Task2Index[4]和Task2Index[6]间存在索引5对应任务t3，且lev(t3)

图6 变异操作

CODC-GA算法在执行过程中如果得到的新调度在满足截止时间约束的同时拥有更小的执行代价，将取代种群中原有的调度，并不断迭代，直至产生最优调度方案。

3 仿真实验

3.1 实验配置

为了评估CODC-GA算法性能，利用仿真工具包CloudSim[10]进行仿真测试，并引入4种科学工作流作为测试源，包括：Montage、LIGO、Epigenomics及CyberShake[11]，每种工作流包含不同的结构和特征，结构如图7所示。Montage为天文学领域中的工作流形式，任务以I/O密集型为主，对CPU计算能力要求不高，LIGO为物理学领域引力波工作流形式，任务以计算密集型为主，且对内存要求较多，Epigenomics为信息生物领域的工作流形式，任务以计算密集型为主，且对内存要求较多，CyberShake为地震学领域的工作流形式，任务以数据密集型为主，且对计算能力和内存存储均有较高要求。同时，为了符合现实科学工作流的随机化规模特点，笔者在每种工作流中设置了3种不同大小的任务规模，包括：small(50个任务)、medium(100个任务)及large(1000个任务)。

图7 4种工作流结构

实验配置包含5种不同计算能力的VMs，参考Amazon EC2[12]的VM配置，具体参数见表2。表2中，一个ECU等同于1.0 GHz～1.2 GHz的CPU处理能力，任务的处理时间可由该值计算得到，单个数据中心中VMs的性能变化服从均值12%和标准差10%的正态分布，数据传输时间变化服从均值9.5%和标准值5%的正态分布。

表2 VMs类型

为了评估算法性能，定义每种工作流的截止时间约束，首先将所有任务按顺序调度至最快VM上，然后计算工作流最小执行时间MET_W，该值为执行跨度下限。为了设置工作流截止时间，考虑两种截止时间约束：硬约束和软约束，截止时间通过下式设置

D=MET_W×(1+γ)

(14)

式中：γ为约束因子，MET_W为工作流最小执行时间，即式(9)，当0≤γ<12时表示截止时间硬约束，当12≤γ≤32时表示截止时间软约束，实验中γ值以步长0.4进行改变。

遗传参数设置为：种群规模为400，最大迭代次数为500，交叉概率为100%，变异概率为30%，通过CODCGA算法的交叉、变异及适应评估方法对初始种群进行优化，不断迭代，直到找到满足约束的代价最小化调度可行解。

选择IC-PCP[5]、RTC[6]、RCT[6]和PSO[7]算法作为性能比较的基准算法。IC-PCP基于云资源按需提供与即付即用定价模式等特征，重点在工作流调度时考虑了VMs的异构性、性能动态变化特征和任务间的数据传输时间等要素，但未考虑任务计算时间和VM的启动时间影响。RTC和RCT是分别针对执行时间优先和执行代价优先提出的工作流调度最优化算法，重点侧重于健壮性和容错问题。PSO通过将粒子表示工作流任务进行编码，但没有表示资源信息，且粒子在不同方向的移动可能导致个体最优，无法得到全局最优，另外，该算法在硬约束时，较难找到可行解。

3.2 实验结果

(1)截止时间性能评估

表3比较了算法对截止时间满意度的情况。在Montage工作流的硬约束中，CODC-GA拥有高于IC-PCP 93%的满意度，对于LIGO和CyberShake工作流，CODC-GA优于IC-PCP 88.5%，对于Epigenomics工作流，CODC-GA优于IC-PCP 83.5%，显然，对于硬约束，IC-PCP在每种工作流中均无法满足截止时间约束，而CODC-GA比IC-PCP更优。同时，3种工作流中，无论硬约束还是软约束，CODC-GA均拥有比RTC、RCT和PSO更高的约束满意度。

表3 截止时间满意度/%

另外，可以看出，IC-PCP在软约束下性能是有所提高的，但综合看来，IC-PCP在两类约束下性能均较差，主要是由于该算法忽略了云的动态特征和VMs性能的动态变化，此外，该算法也没有考虑延时问题，这对工作流的执行跨度拥有较大影响。CODC-GA同时考虑了以上因素，能够估算单个任务的开始时间和完成时间，确保任务在截止时间内完成。RCT和RTC基于资源选择策略，一定程度上忽略了VMs的性能变化。PSO与CODC-GA均属于智能算法，但PSO的调度方案编码方式缺乏资源信息，可能导致因VM性能的不同而无法满足截止时间约束的情况。

(2)执行时间和执行代价性能评估

图8和图9比较了算法的执行时间和执行代价情况，其中，横坐标的含义为：若小于或等于1.2，表示硬约束，否则表示软约束。

图8 执行时间

图9 执行代价

可以看出，IC-PCP在每种工作流中均拥有最长的执行时间，而执行代价也最小，由于该算法无法满足工作流的截止时间约束，因此，即使代价最小也无法完成最优化调度目标。其它算法中，CODC-GA在Montage工作流中拥有比RCT低28%的执行时间，比PSO低11%，比RTC低22%。在LIGO工作流中，CODC-GA的执行时间比RCT低22%，比PSO低43%，比RTC低43%。在CyberShake工作流中，CODC-GA的执行时间比RCT低27%，比PSO低17%，比RTC低6%。在Epigenomics工作流中，CODC-GA的执行时间比RCT低38%，比PSO低20%，比RTC低47%。同样地，CODC-GA在执行代价方面也均优于其它算法。

综合执行代价、执行时间及截止时间约束满意度等结果来看，CODC-GA可以在降低执行代价的同时得到最高的约束满意度，在硬约束中，CODC-GA在4种工作流形式中均拥有最高的约束满意度并更低的执行代价。截止时间约束相对宽松后，CODC-GA可以同时降低执行时间和执行代价。

4 结束语

云计算可以提供高性能计算资源解决大规模科学工作流调度问题。为了解决满足工作流截止时间约束同时的执行代价最优化问题，提出了一种工作流调度遗传算法，算法重点考虑了云资源异构、VMs性能动态可变等特征，设计了全新的调度编码方案、种群初始化以及遗传交叉和变异操作，以得到最优的工作流调度方案。现实工作流的测试结果表明，比较同类算法，算法不仅拥有最高的截止时间满意度，而且执行时间更短，执行代价更低。