基于局部关键路径与截止期限分配的云工作流调度算法

蔡艳婧 王 强 程 实

1(南通大学电子信息学院 江苏 南通 226019)2(江苏商贸职业学院电子与信息学院 江苏 南通 226001)3(南通大学计算机科学与技术学院 江苏 南通 226019)

0 引 言

工作流结构广泛应用于复杂计算问题建模，云计算特有的按需提供和付即用的定制资源使用方式使其成为调度工作流的有效方法[1]。与传统批任务调度不同，工作流结构的任务具有严格的逻辑执行次序，需要在满足给定QoS约束的同时，实现与资源间的映射。工作流调度通常由选择被调度任务和选择提供实例两个阶段构成，两阶段决策对于是否能够满足给定约束和全局调度代价均具有重要影响。传统工作流调度方法仅注重执行效率/时间，忽略了资源使用的费用，此时的调度问题在不同资源和不同调度方案下的执行时间和代价均有所不同。因此，同步考虑用调度时间和代价更加符合云资源的使用环境。

为了解决期限约束时的工作流调度代价优化问题，本文设计的调度方法是将全局期限在所有工作流任务上进行分割，以得到任务的子期限，然后在实例提供时仅满足子期限即可。

1 相关研究

对于工作流调度过程的调度与提供两个阶段[2]，给定资源集，调度阶段的目标是决定任务执行的最优序列和与用户相应约束下的任务部署[3]；提供阶段的目标是为工作流内的任务选择资源类型和相应资源数量，并为任务执行预留资源[4-5]。相关研究中，底向下分层[6](Down-Buttom Level,DBL)和底向上分层[7](Down-top Level,DTL)算法是典型的基于期限分配的启发式调度算法。前者以down-top方式对任务进行划分，后者则以top-down方式对任务进行划分。由于工作流可以有向无循环图建模，故DBL将任务划分为不同层次，每个层次包含的任务不具有依赖性。而DTL将任务划分为不同路径(作为同步任务或简单任务，同步任务定义为拥有一个以上父任务或子任务的任务)。为任务分配期限时，全局期限以正比于每个层次的最小执行时间的方式在各层次间进行分割。然而，在DBL算法，首先需要计算最快实例资源，然后再将期限与估算值之差以均匀分布方式在所有层次间进行分配。文献[8]提出了DET算法，算法将任务分为两种类型：关键和非关键任务。关键任务利用动态规化进行调度，非关键任务则在关键任务间进行回填式调度，但该算法忽略了任务间的通信时间。

文献[9]提出了云工作流调度算法PDC，算法将期限以正比于各层次中任务执行时间的方式在层次间进行分割。文献[6，10]提出了最迟完成时间LFT算法，该算法也是将期限在各任务间进行分割，并确保工作流在用户定义期限条件下，执行完任务的最早时间。文献[10]提出了局部关键路径算法，算法可以根据任务在工作流中所处的局部关键路径对任务进行分类，同时，期限根据定义的路径进行重分配。然而，算法在每个局部关键路径PCP执行后，需要重新计算最迟完成时间，开销较大。文献[6]提出了基于动态代价最小的联合内层技术(Joint Inner Technology，JIT)算法，该算法在期限约束下将联合管道任务集建立为单个任务，以消除任务间的数据传输时间。然而，该算法在任务执行实例的选择上并非最优，有待改进。

2 任务调度模型

云工作流模型以有向无循环图DAG建模，表示为G(T,E)，T为n个任务{t1,t2,…,tn}的集合，E为边集。每条边ei,j=(ti,tj)表示任务间的执行次序约束，代表ti必须在tj开始前完成执行。对于给定的DAG，不存在任一父节点的任务称为入口任务tentry，不存在任一子节点的任务称为出口任务texit。由于本文的算法要求应用模型具有单一入口和出口任务，故可以分别在任务DAG的开始和结尾处增加一个傀儡任务tentry和texit。傀儡任务的执行时间为0，且与其他任务的连接边上的权值也为0。

云资源模型由多个云服务提供者组成，每一个均可向用户提供资源。每一个任务ti可由拥有不同QoS属性的不同服务提供者的mi种服务Si={si,1,si,2,…,si,mi}进行处理。本文关注的QoS属性为执行时间和代价，服务代价取决于执行时间，即执行时间越短，代价越高。令ET(ti,s)表示在服务s上处理ti的估计执行时间，EC(ti,s)表示在服务s上处理ti的执行代价。令TT(ei,j,r,s)和TC(ei,j,r,s)分别表示服务r(执行任务ti)与服务s(执行任务tj)间的边ei,j上的估计数据传输时间和传输代价。

3 算法设计

3.1 算法实现思路

基于局部关键路径和截止期限的云工作流调度算法(Workflow Scheduling Based on Partial Critical Path and Deadline Constraint，WS-PCPDC)包括两个阶段：期限分配与资源选择。期限分配阶段中，全局任务DAG的截止期限在个体任务间进行分配，若每个任务可在其子期限内完成，则整个任务DAG可在截止期限内完成。资源选择阶段中，在满足任务子期限的同时，为每个任务选择最优资源完成任务调度，实现代价最优。

3.2 基本定义

对于每个未调度任务ti，令EST(ti)表示任务ti的最早开始时间，该时间是未考虑实际执行该任务的资源时得到的时间。显然，无法计算准确的EST(ti)，由于云环境是异构环境，任务执行时间在不同资源间是变化的。进一步，数据传输时间也取决于所选资源及资源间的传输带宽。任务ti的最小执行时间MET(ti)和最小传输时间可分别定义为：

基于以上定义，最早开始时间可定义为：

式中，pred(ti)表示ti的父节点任务。

对于每个未调度任务ti，令LFT(ti)为整个任务DAG在截止时间D内保证完成时,任务ti能够完成执行的最迟时间，则：

对于每个调度任务ti，令SS(ti)为执行ti的所选资源，AST(ti)为任务ti在资源上的实际开始时间。

3.3 算法步骤

算法1是WS-PCPDC算法的伪代码。步骤3添加两个傀儡节点至任务DAG中，步骤4-步骤7计算所需参数值，步骤8为节点tentry和texit分配子期限，并在步骤9中将这两个任务标记为已分配(assigned)节点。已分配节点表明该任务节点已经分配子期限，未分配子期限的节点称为未分配(unassigned)节点。可以看出，texit的子期限设置为截止期限D，说明出口任务必须在D内完成。步骤10对出口任务调用AssignParent算法(分配节点算法)，该算法的目标是为输入节点的所有未分配父节点分配子期限，从出口任务texit开始分配即可保证为DAG中的所有任务分配子期限。因此，AssignParent算法负责在所有任务间分配全局截止期限。最后，步骤11调用Planning算法，用于在满足子期限的情况下为每个任务选择执行资源。

算法1WS-PCPDC

(1) Procedure ScheduleWorkflow(G(T,E),D)

(2) Request available resource for each task inG

//发出资源请求

(3) addtentry,texitand their correoponding edges toG

//添加进出口任务

(4) using Eq.(1) to computeMET(ti) for each task

//为每个任务计算MET(ti)

(5) using Eq.(2) to computeMTT(ti) for each edge

//为每条边计算MTT(ti)

(6) using Eq.(3) to computeEST(ti) for each task inG

//为每个任务计算EST(ti)

(7) using Eq.(4) to computeLFT(ti) for each task inG

//为每个任务计算LFT(ti)

(8) sub-deadline(tentry)=0,sub-deadline(texit) =D

//为入口出口任务计算子期限

(9) marktentryandtexitas assigned

//标识入出口任务已调度

(10) call function AssignParent(texit)

//调用AssignParent(texit)

(11) call function Planning(G(T,E))

//调用Planning(G(T,E))

(12) end procedure

3.4 AssignParent算法

AssignParent算法伪代码如算法2所示。算法输入一个已分配节点，并尝试分配子期限至其所有父节点上。AssignParent算法(分配节点算法)首先需要寻找终止于输入的未分配节点的局部关键路径。

算法2AssignParent

(1) Procedure AssignParents(t)

(2) while (thas an unassigned parent) do

//若t有未调度父节点

(3)PCP←null,ti←t

//局部关键路径置空

(4) while (there exists an unassigned parent ofti) do

//若仍有未调度父节点

(5) add CriticalParent(ti) to the beginning ofPCP

//添加任务的关键父节点至PCP的队首

(6)ti←CriticalParent(ti)

//提取当前任务

(7) call function AssginPath(PCP)

//调用函数AssginPath(PCP)

(8) for all (ti∈PCP) do

//每个局部关键路径上的任务更新EST和LFT

(9) updateESTfor all unassigned successors ofti

//更新所有未调度子任务的EST

(10) updateLFTfor all unassigned predecessors ofti

//更新所有未调度父任务的LFT

(11) end procedure

以下定义关键父节点的概念：

定义1任务ti的关键父节点为数据到达时间最迟的未分配父节点，即：满足下式的ti的父节点tp：

定义2任务节点ti的局部关键路径为：

1) 若ti不存在任一未分配父节点，则为空；

2) 若ti存在任一未分配父节点，则由其关键父节点tp和tp的局部关键路径组成。

算法2由输入节点开始，沿关键父节点直到到达没有未分配父节点的节点任务，以形成一条局部关键路径。第一次调用该算法时，由texit开始，向回追溯其关键父节点，直到到达tentry。因此，算法可以找到穿越整个DAG的全局关键路径。然后，算法调用AssignPath算法(分配路径算法)，该算法接收一条路径(任务节点序列)作为输入，在任务的最迟完成时间内分配子期限至路径上的每个节点上。当子期限分配至任务后，其未分配后继节点的EST和其未分配父节点的LFT可能发生改变(根据式(3)和式(4))。基于此原因，算法需要在下一次循环中更新路径上所有任务的这两个值。最后，算法通过递归调用AssignParent为局部关键路径上的每个任务节点的父节点分配子期限。

3.5 AssignPath算法

AssignPath算法接受一条路径作为输入，分配子期限至其上的每个任务节点。本文设计三种分配策略，试图为路径创建预计调度方案，并使用算法为路径上的任务分配子期限。由于仅是估计调度方案而非实际方案，故未考虑资源的可用时间。

1) 最优策略。该策略试图寻找在最迟完成时间内执行路径上任务的代价最小调度，然后利用该最佳调度分配子期限至路径上的任务。策略过程如算法3所示。该算法基于回溯法，从路径上的第一个任务开始，向最后一个任务遍历，在每一步中为当前任务选择下一个更慢的资源，即步骤5。因此，对于每个任务的资源是从最快至最慢进行检测。如果没有可用未检测资源剩余，或分配当前任务t至下一个更慢资源s是不可行分配，则算法回溯至路径的前一任务，并为其选择另一资源，即步骤6-步骤8。如果任务t能够在其最迟完成时间内在资源s上完成，即EST(t)+ET(t,s)≤LFT(t)，则定义为一次可行分配。

步骤9-步骤10中，算法检测当前任务是否为路径上的最后一个任务，且当前分配是否拥有比最优分配更低的代价，若满足，在步骤11中设置当前调度为最优best调度。While循环结束后，步骤18检测是否找到最优调度，由于路径上某些任务可能在其LFT内得到调度，所有可能存在最优调度不存在的情形。如果不存在最优调度，则在步骤19中将任务的EST+MET值作为路径上的任务的子期限值分配，否则，根据最优调度best为路径path上的所有任务设置EST和分配子期限。

最后，可能存在额外时间，即最后一个任务的LFT与其分配的子期限之间存在差值，可将其添加至路径上的任务的子期限上。当该额外时间值小于最小值时，可将其添加至最后一个任务的子期限上。若该值较大，可以正比于传输时间减去执行时间的方式将其分配至路径上的任务。

算法3Optimized PathAssigning Algorithm(最优策略算法)

(1) Procedure AssignPath(Path)

(2) best←null

//最优集合先置空

(3)t←first task on the path

//提取当前路径的第一个任务

(4) while (t is not null) do

(5)s←next slower service ∈St

//提取下一个最慢的服务提供者

(6) if (s=assigningtto s is not admissible) then

//若无法分配完成

(7)t←previous task on the path and continue while loop

//继续在该路径上寻找

(8) end if

(9) if (tis the last on the path) then

//若该任务为路径上的最后一个任务

(10) set this schedule as best

//设置该调度解为最优

(11) end if

(12)t←next task on the path

//提取路径上的下一任务

(13) end while

(14) if (best is null) then

//若最优集为空

(15) set sub-deadline(t)=EST(t)+MET(t) for all taskston the path

//更新子期限

(16) else

(17) setESTand sub-deadline according to best for all tasks∈path

//以最优解为基础设置EST和子期限

(18) end if

(19) mark all tasks of the path as assgined

//标记任务是否调度

(20) end procedure

2) 代价降低策略。该策略是一种近似最优的贪婪方法，即策略试图以多项式时间寻找一个较优解(不一定为最优解)。策略首先将最快资源分配至路径上的每个任务，显然该分配是代价最高解。然后，试图在不超过任一任务的LFT的情况下，通过分配代价更低(也更慢)的资源至任务来降低代价。为了决定哪些任务需要重分配至代价更低的资源，需要计算代价降低率CDR，定义为：

(5)

式中:cs为已分配至任务ti的当前资源，ns为比当前资源执行ti更慢的资源。任务t在资源s上的总执行时间TET(t,s)为在资源s上的执行时间+任务t与其路径上的父节点与子节点间的总传输时间(除不存在父/子节点的第一个和最后一个任务节点)。任务t在资源s上的总执行代价TEC(t,s)的定义方式与上类似。

ti的CDR可以衡量一个单位时间的代价可以换来多少执行代价的降低。若t*被选择使得它有最大CDR值，则该任务是可替换的，即将其分配至下一个更慢资源是一个可行分配。最后，t*的当前资源可更改为下一个更慢资源。过程如算法4所示。

算法4低价降低策略算法

(1) Procedure AssignPath(path)

(2) cur←assign the fastest service to each task of the path

//将最慢服务分配给路径上的每个任务得到一个初始解

(3) computeCDR(ti) for each task of the path by Eq.(5)

//计算任务CDR(ti)

(4) repeat

(5)t*←null

(6) for all (ti∈path) do

//判定路径的CDR值的大小

(7) if (CDR(ti)>CDR(t*) andtiis replaceable) then

(8)t*←ti

(9) end if

(10) end for

(11) if (t*is not null) then

(12) update cur by assigningt*to the next slower service

//分配次最慢的服务器更新cur

(13) updateCDR(t*)

//更新CDR

(14) end if

(15) until (t*is null)

//循环至集合为空

(16) if (there is an inadmissible assignment in cur) then

//若在cur集合中存在一个不允许的调度解

(17) set sub-deadline(t)=EST(t)+MET(t) for all tasks t on the path

//更新子期限

(18) else

(19) setESTand sub-deadline according to cur for all tasks∈path

//以最优解为基础设置EST和子期限

(20) end if

(21) mark all tasks of the path as assgined

//标记调度任务

3) 公平策略。该策略以公平的方式为路径上的任务节点分配子期限。首先，策略将路径上的每个任务分配至最慢的资源上。然后，从第一个任务至最后一个任务，在不超过任务的LFT的情况下，策略以下一个更慢资源替换已分配资源。该过程迭代执行至无法替换为止。策略过程如算法5所示，最差情况下，repeat-until循环将执行m次，因此，算法时间复杂度为O(lm)。

算法5Fair PathAssigning Algorithm

(1) Procedure AssignPath(Path)

(2) cur←assign the fastest service to each task of the path

//将最慢服务分配给路径上的每个任务得到一个初始解

(3) for all (ti∈path) do

//对于所有路径上的任务

(4) if (assigningti→next service is admissible) then

//若将任务调度至下一个服务器可行

(5) update cur by assigningti→next slower service

//更新cur集合

(6) until (no change is done)

//直到无法进一步改进

(7) if (there is an inadmissible assignment in cur) then

//若存在不可行解

(8) set sub-deadline(t)=EST(t)+MET(t) for all tasks t on the path

//更新子期限

(9) else

(10) setESTand sub-deadline according to cur for all tasks∈path

//以最优解为基础设置EST和子期限

(11) mark all tasks of the path as assgined

//标记已调度任务

3.6 Planning算法

Planning算法(规划算法)即为算法的第二个阶段(资源选择阶段)，其目标是为每个任务选择最优资源，在确保满足截止期限的同时，以最小化执行代价调度任务。在期限分配阶段，每个任务被分配一个子期限。如果可以调度每个任务，使得任务在其分配子期限内完成，则整个DAG可在截止期限内完成。该阶段算法尝试以贪婪策略通过制定局部最优决策创建全局最优调度解。在每个阶段中，算法选择一个就绪任务，即该任务的所有父任务已经完成调度，然后调度至满足其子期限的价格最低的资源上执行。因此，对于就绪任务ti的所选资源SS(ti)满足：

约束条件为：

AST(ti,s)+ET(ti,s)≤sub-deadline(ti)

(6)

式中:ti在s上的实际开始时间AST(ti,s)为ti的父节点数据到达资源s的最迟时间与资源s上可用时槽开始时间的相对大值。

当没有资源可子期限内完成任务ti时(由于子期限仅是估算调度，并未考虑资源上的实际可用空闲时间槽)，则选择完成时间最小的资源SS(ti)，即满足：

minAST(ti,s)+ET(ti,s)

(7)

Planning算法的伪代码如算法6所示。

算法6Planning

(1) Procedure Planning(G(T,E))

(2) Queue←tentry

//将入口任务输入队列

(3) while (Queue is not empty) do

//若队列不为空

(4) t←delete first task from Queue

//删除队列首任务

(5) query available time slots for each service fromCRP

//查询资源的可用时隙

(6) computeSS(t) according to Eq.(6) and (7)

//计算SS(t)

(7)AST←the actual start time of t onSS(t)

//更新AST

(8) make advance reservation of t onSS(t)

//提前保留

(9) for all (tc∈children oft) do

//对于所有子任务

(10) if (all parent oftcare scheduled ) then

//若所有父节点已被调度

(11) addtcto Queue

//添加至队列

3.7 算法时间复杂度分析

假设调度的任务DAGG(T,E)包含n个任务和e条边，可用资源数量为m，入口任务与出口任务间的最长路径的长度为l。由于G为有向无循环图，则最大边数量为(n-1)(n-2)/2，因此可假设e≈O(n2)。调度算法中，步骤4计算MET的时间复杂度为O(nm)=O(n3)，步骤5计算MTT的时间复杂度为O(em2)=O(n2m)，步骤6计算EST的时间复杂度为O(n+e)=O(n2)，步骤7计算LFT的时间复杂度为O(n+e)=O(n2)，步骤11的Planning算法的时间复杂度为O(nme)=O(n3m)。

对于Planning算法，需要为每个任务尝试所有资源以寻找满足子期限的代价最低的资源。每一次尝试中，需要计算任务在资源上的实际开始时间，该过程需要考虑所有父任务及连接边，故时间复杂度为O(nme)。

AssignParent算法(分配节点算法)为递归过程。第一次在出口任务上调用并在所有DAG任务上进行自调用。算法拥有一个while循环(步骤2-步骤14)处理每个节点的入边，故算法将处理所有DAG的边。在while循环内部，首先需要计算局部关键路径，其时间复杂度为O(l)。然后，算法调用AssignPath，其时间复杂度取决于所选策略。由于AssignPath的时间复杂度取决于l和m，将其考虑为g(l,m)，故AssignParent的时间复杂度为O(el+eg(l,m))。对于AssignPath算法(分配路径算法)，最快的为Fair策略，时间复杂度为O(lm)，因此可忽略时间复杂度的el部分，时间消耗为eg(l,m)。如果替换e，则时间复杂度为O(n2g(l,m))。在分配子期限后，AssignParent需要更新任务的所有未分配子节点的EST和所有未分配父节点的LFT。最差情况下，一个节点拥有n-1个未分配子节点和父节点，因此更新所有任务的EST和LFT的时间复杂度为O(n2)。

在三种不同的AssignPath策略下，AssignParent的时间复杂度分别为O(n2lm)、O(n2l2m)和O(n2lm)。由于l是入口任务至出口任务间最长路径的长度，故其最大值为n(此时为线性DAG)。此时，AssignParent的时间复杂度分别为O(nm)、O(n4m)和O(n3m)，这也是整个算法的时间复杂度。

4 算例分析

以图1所示DAG对算法工作原理进行阐述。算例包括9个任务t1至t9和两个傀儡任务tentry和texit。三种资源Si,1、Si,2和Si,3，能以不同的QoS能力执行任务。表1给出任务在不同资源上的执行时间和执行代价。可以看到，对于任务而言，资源越快，代价越高。图1中，每条边上的数值既表示数据传输时间，也表示对应传输代价。例如：t2与t5间的数据传输时间为2，则用户的传输代价也为2，与两个任务所选资源无关。设置DAG的全局截止期限为35。

表1 执行时间和执行代价

图1 任务DAG

利用WS-PCPDC算法调度图1的DAG，首先需要将所有任务分配至最快资源上计算EST和LFT。然后，算法设置tentry和texit的子期限分别为0和35，并标记两个任务为已分配。接下来算法需要调用AssignParent和Planning，以下作出讨论。

4.1 调用AssignParent算法

首先，在texit上调度AssignParent算法，由于该任务有3个父节点，步骤2的while循环将执行三次，将之称为Step1至Step3，后文进行讨论。进一步，需要选择路径分配策略，以最优策略Optimized为例，每一步得到的任务的EST、LFT和子期限DL如表2所示。标记*表示该值相比前一步骤已发生改变。

Step1首先，AssignParent追踪texit的局部关键父节点寻找其局部关键路径，为t2-t6-t9。然后，调用AssignPath算法(分配路径算法)分配子期限至这些任务。对于以上三个任务共有27种可能的资源分配，其中，S2,3-t2、S6,2-t6和S9,1-t9为拥有最小代价的最优可行分配，该分配用于决定每个任务的子期限值。下一步即是更新这些任务的所有未分配子节点的EST，即t5和t8，及未分配父节点的LFT，即t3。变化后的值如表2的Step1。最后一步是在路径上的所有任务上递归调用AssignParent。由于t2和t9没有未分配父节点，在Step1.1中仅需在t6上调用AssignParent。

Step1.1当在t6上调用AssignParent时，首先寻找该任务的局部关键路径，即t3。然后，调用AssignPath寻找t3的最优分配，即S3,3。由于t3没有未分配子节点或父节点，Step1完成。

Step2现在，回到任务texit，AssignParent试图寻找下一条该任务的局部关键路径，即t5-t8。然后，调用AssignPath，考虑这两个任务的所有9种可能分配，并选择最优可行分配，即S5,1-t5，S8,3-t8。这两个任务没有未分配子节点，但算法需要更新其未分配父节点的LFT，即t1和t4。最后，算法在路径上的所有任务上调用AssignParent，t5没有未分配父节点，因此在Step2.1中仅考虑t8。

Step2.1当在任务t8上调用AssignParent时，寻找其局部关键路径，即t1-t4。然后，调用AssignPath，计算该路径的最优可行分配，即S1,3-t1、S4,2-t4。这两个任务没有未分配父节点，算法需要更新t4的子节点的EST，即t7。由于t1和t4没有未分配父节点，Step2停止。

Step3在最后一步中，AssginParent寻找texit的最后一条局部关键路径，即t7。AssignPath寻找最优可行分配为S7,2-t7，由于没有未分配父节点或子节点，算法停止。

4.2 调用Planing算法

在该算例中，Planning仅将每个任务调度至AssignParent算法计算得到的相同资源上。原因在于：数据传输时间是固定的，且资源是完全可用的。这两个假设使得AssignPath得到的估计调度方案是实际的调度方案。所选资源如表2所示。总时间为35，总代价为64，包括执行代价48和数据传输代价16。

表2 算法每一步的详细计算结果

5 仿真分析

5.1 实验配置

为了评估算法性能，本节设计仿真实验对算法进行测试。利用工作流仿真工具包WorkflowSim对算法进行实验分析。在Workflow平台上配置10个异构数据中心，每个数据中心随机配置10～100个资源节点，资源处理能力与代价配置参考Amazon EC2，单个数据中心的资源拥有相同的处理器速率，数据中心内的资源处理能力约定最快为最慢的10倍。数据中心内部的资源间的带宽随机分布于[100 Mbit/s，512 Mbit/s]之间，数据传输代价正比于带宽，即带宽越高，代价越高。

同时，实验为了测试任务规模对算法性能的影响，配置了三种规模的任务数量，小规模为30个任务，中规模为100个任务，大规模为1 000个任务。使用五种不同科学领域中的合成工作流结构作为数据源，包括：(1) Montage工作流：天文学;(2) Epigenomics工作流：生物学;(3) SIPHT：生物信息学；(4) LIGO工作流：引力物理学；(5) CyberShake工作流：地震学。其结构如图2所示[12]。不同工作流形式在其任务关联、数据聚合、数据分布及数据重分布等组成方面均有所不同。Montage工作流的任务以I/O密集型为主，对CPU处理能力的要求相对较低，且串行任务结构极少。Epigenomics工作流的任务以计算密集型为主，且对内存要求较多，串行任务也较多。SIPHT工作流与Epigenomics同为生物学工作流形式，任务类型相似，但SIPHT工作流结构更为复杂，串行任务极少。LIGO工作流的任务多以CPU计算密集型为主，且拥有较多内存需求，拥有大量较短的串行任务。CyberShake任务以数据密集型为主，同时拥有较大内存需求和CPU计算能力请求。

图2 工作流结构图

5.2 实验结果

利用标准化调度长度makespan(NM)和标准化代价cost(NC)对算法性能进行衡量：

式中:MHEFT表示利用质构最早完成时间算法HEFT[13]得到的调度长度，CC为将所有任务调度至代价最低资源上的调度代价。

为了评估算法性能，需要将截止期限分配至整个工作流任务。显然，该截止期限须大于或等于HEFT算法得到的调度长度。为了设置截止期限，定义一个截止期限因子α，并设置工作流的期限为其到达时间加上αMHEFT。实验中α值的取值范围为[1,5]。选取的基准算法为MDP算法[10]。

表3给出了算法的标准化调度长度小于期限因子的平均比例，可以看出，算法均可以在期限约束内完成所有工作流调度，即使期限较紧的情况下(更小的期限因子取值)。对于LIGO和CyberShake工作流，两种算法几乎利用了所有可用的期限使得执行代价达到最小，即平均差值比例小于1%。Montage工作流几乎是同样的情况，而对于Epigenomics和SIPHT工作流，MDP算法拥有更高的平均差值比例，分别是中规模Epigenomics工作流中的3.07%和小规模SPIHT工作流中的5.99%。而本文的三种算法在小规模SPIHT中也均有相对更高的差值比例。

表3 标准化调度长度小于期限因子的平均比例

图3给出了调度算法得到的执行代价情况。大致上，中小规模工作流拥有类似结果，两类算法在较宽松期限下(期限因子为5)拥有基本相同的标准化代价值(约为2)，这表明当将期限从MHEFT增加到5倍时，对于中小规模工作流标准化代价降低幅度约小于两倍CC，除了中规模Montage例外。对于大规模工作流则拥有完全不同的结果，仅有SIPHT工作流维持与中小规模工作流相同的结果，而Montage工作流拥有最差的性能表现。这表明拥有大数量任务的大规模工作流中，工作流任务间的结构特征比中小规模工作流更加影响任务调度过程。图3还表明，Optimized在三种策略中及所有工作流类型中拥有最佳的性能表现，即最小的代价，也优于参考算法MDP。

(a) 小规模CyberShake (b) 中规模CyberShake

(c) 大规模CyberShake (d) 小规模Epigenomics

(e) 中规模Epigenomics (f) 大规模Epigenomics

(g) 小规模LIGO (h) 中规模LIGO

(i) 大规模LIGO (j) 小规模Montage

(k) 中规模Montage (l) 大规模Montage

(m) 小规模SPIHT (n) 中规模SPIHT

(o) 大规模SPIHT图3 标准化代价情况

对于CyberShake、LIGO和SIPHT工作流，利用Optimized策略的WS-PCPDC算法拥有最佳性能，而Cost Decrease策略则拥有近似表现。Fair策略拥有最差的性能，但仍然比MDP算法表现更优。表4给出WS-PCPDC算法比较MDP算法的性能优势。

表4 WS-PCPDC算法比较MDP算法的性能优势

对于Epigenomics工作流，MDP在某些情况下具有比WS-PCPDC更好的性能，在大中规模情况下可以得到更小的平均代价降低幅度，主要原因是Epigenomics工作流结构中拥有多个并行线性任务。初始状态下，WS-PCPDC寻找工作流的关键路径时，工作流拥有多个入口任务，一个是并行管道任务，其他三个为工作流的终端任务。WS-PCPDC试图为这条关键路径寻找最优调度时，未考虑第一个和第六个任务间的并行性。若考虑并行性，需分配最长的子期限到这四个任务上，由于此时可以留下更多的空闲时间，全局代价也可以得到降低。

大规模Montage在所有算法上均拥有最差性能，即截止期限的增加并未带来代价降低幅度的增加。在大规模Montage中，当增加期限至5倍时，代价降低约为初始值的一半。进一步，利用Optimized的WS-PCPDC算法从小规模至大规模工作流中有所降低，尤其在大规模工作流中，其性能差于MDP。原因在于，对于Montage结构，其全局关键路径由9个任务组成，需优先为该路径分配子期限。对于小规模工作流，所分配的子期限在资源选择阶段得以保留。然而，对于大规模工作流，全局关键路径上第三个任务前的很多任务会在资源选择阶段被调度到更慢的资源上，这会导致关键路径上的第三个任务无法按时完成，并会将这推迟传导至其子节点，从而降低最终的调度性能。Fair在大规模工作流中拥有较好性能，比较MDP的平均代价降低比例为12.07，该策略在中规模工作流中也有较好性能。

6 结 语

为了满足期限约束，最小化执行代价，提出一种基于局部关键路径和截止期限分配的工作流调度算法。算法通过定义工作流的局部关键路径，以递归方式在局部关键路径上的任务间进行子期限分配，并在调度资源选择上满足任务子期限的同时，为每个任务选择执行代价最低的调度，实现调度代价优化。