预算约束下关联式云任务调度算法

何留杰

(黄河科技学院 现代教育技术中心， 郑州 450063)

0 引 言

关联式云任务即为工作流任务形式，是科学研究领域中最常用的应用模型。由于云计算可以即付即用的形式提供高性能的计算能力，利用云资源执行工作流任务正成为时下的研究热点问题。作为数据密集型科学实验的发展，工作流调度问题是应用领域中必须面临的难题。原因在于：工作流的任务规模动态可变，且特征异构，对于资源的需求和依赖性也显示出不确定性。云可以按需提供大范围实例类型，显然比传统的一般分布式计算环境具有更好的执行效率[1]。与传统工作流不同，科学工作流规模更大，任务的数据计算与通信代价更高，其本质是实现相互依赖的任务至资源间的映射，同时要求满足用户定义的服务质量(Quality of Service, QoS)约束(截止时间或预算)。传统的工作流调度算法仅侧重于考虑优化执行效率(执行时间)，未考虑资源代价，而云计算是商业化环境，其资源使用是有偿付费的，资源能力越高，价格越高，此时，使用不同资源及不同调度方案得到的执行代价和时间是不同的[2]。因此，云环境中的工作流调度需要同步考虑用时间和代价问题。本文将重点研究用户预算约束下的任务调度优化问题，并侧重于从满足约束的同时，提高调度效率和调度成功率的角度，实现工作流任务与资源实例间的有效映射。

1 相关研究

云计算环境中，截止期限和预算等QoS约束下的工作流调度问题是研究热点问题。多数截止期限约束的调度算法主要思想是如何将用户定义的期限在工作流任务或层次间进行分布[3-4]，更多强调调度效率，忽略调度成本。而云环境是即付即用的资源提供环境，相比而言，预算约束是其更应该考虑的约束条件。该领域中的相关研究大致可分为两类：代价优化和预算约束。

(1) 代价优化。文献[5]中在经典异构最早完成时间算法[6]的基础上改进设计了一种代价感知启发式调度算法，该算法首先构建了任务优先级列表，然后按优先级将任务调度至代价效率最高的资源上。然而，算法仅考虑了一种资源类型和价格模型，显然不符合云资源的牲。文献[7]中提出一种安全与预算感知的工作流调度算法，试图最小化工作流执行时间。然而，算法在超过预算时无法做到有效控制，因此，应属于代价优化一类策略。文献[8]中提出一种优化有效的启发式调度算法，然而，算法所考虑的代价模型仅考虑了CPU周期的利用数量，该模型中总代价为所有任务的代价之和，而这与常规的云资源提供环境(如Amazon)是完全不一致的，云资源是按最小周期时间索取费用，即使实例仅使用最小周期的一部分时间。

(2) 预算约束。文献[9-10]中在HEFT基础上设计了预算约束异构最早完成时间算法(Budget Heterogenous Earliest Finish Time, BHEFT)，算法引入当前任务预算因子在未调度任务间进行剩余预算的分布，该分配方式不同于本文，BHEFT是逐个任务的进行剩余预算的分布。而文献[10]中的任务选择则是基于升秩排序。本文中，由一组任务组成的约束关键路径(Constrainted Critical Path,CCP)被选择同时调度以降低通信与数据传输代价。文献[11]中提出一种预算约束的包任务调度算法，并使用了任务间存在优先性的假设，这可能导致任务间的干扰、延迟及重分配问题。本文模型不同于文献[11]，所使用的任务模型为工作流模型，且对约束有更少的依赖性。文献[12]中提出一种预算感知的工作流回溯调度算法，其资源利用了可分解的资源模型。然而，实际的云资源通过会使用至少一小时的帐单周期模型，过小的资源利用周期不利于资源方的经济收益。文献[13]中提出一种预算约束的多工作流调度算法，其预算是以正比例的方式在不同工作流间进行分配，同样不同于本文的工作。文献[14-15]中提出预算约束的端到端最小延时调度算法，在进行任务的初始调度后，算法将所有关键任务利用关键贪婪算法进行了重新调度，与本文研究有些类似，但在资源选择方面并未作出优化。

2 系统模型

2.1 工作流模型

有向无循环图(Directed Aclyce Graph,DAG)是工作流结构的常用表示模型，将工作流定义为图G=(T,E)，T={t0,t1,…,tn}为图顶点代表的任务集合，E={ei,j|ti,tj∈T}为图的有向边集合，代表任务ti与tj间的数据或控制依赖。边ei,j∈E表示两个任务ti与tj间的有向边，ti,tj∈T，代表两个任务间的优先顺序约束，其具体含义是：仅当任务ti执行完成后并收到ti的所有数据后，任务tj才可以开始执行。换言之，任务ti是tj的父任务，tj是ti的后继或子任务。单个任务可拥有一个或多个父任务和子任务。直到其所有父任务完成后，子任务ti才可以开始执行。

2.2 相关定义

任务ti在执行时间最短的实例上的最早开始时间(Earliest Start Time, EST)定义为：

(1)

式中，wtj表示任务tj在速度最快的实例上的执行时间。

ECT(ti)为作务ti在所有实例上最早完成时间ECT，定义为：

ECT(ti)=EST(ti)+wti

(2)

在实例pj上执行任务ti的代价为：

(3)

执行工作流的所有任务的总代价为：

(4)

约束关键路径CCP：关键路径(Critical Path,CP)为工作流结构中从入口任务至出口任务间的最长路径。关键路径的长度|CP|为任务的计算代价与通信代价之和，可考虑为工作流调度的下界。而仅包含就绪任务的任务集合构成一个约束关键路径CCP[16]。当所有前驱任务已完成且任务要求的数据已到达时，视任务为就绪任务。

2.3 云服务模型

假设云供应商可提供无上限的异构实例数量：

P={p0,p1,…,pn}

式中，n为实例类型的索引。

3 WTSBC算法设计

基于预算约束的工作流任务调度算法(Workflow Tasks Scheduling Based on Budget Constraint,WTSBC)的目标是在满足预算约束的前提下最小化执行时间。同时，由于任务调度中任务层次的重要性，算法需要将预算在不同层次中进行重新分配。具体来说，WTSBC算法包括以下4个阶段：

(1) 工作流划分。工作流根据任务间的依赖性进行层次划分。

(2) 预算分配。用户定义的工作流执行预算在每个工作流层次间进行分配。

(3) 任务选择。根据任务优先级，选择约束关键路径上的任务集，作为执行的就绪队列。

(4) 实例选择。选择满足可用预算的实例执行任务。

3.1 工作流划分

工作流划分过程是通过分配任务至不同层次最大化任务并行执行的程度，同一层次中的任务相互之间不存在依赖性，可并行执行。因此，每一层次中任务可考虑为包含独立任务集的包任务。

定义任务ti的层次为一个整数，代表任务ti至工作流出口任务间所有路径的边的最大值。令NL为包任务中一个任务的层次值，可表示为：

(5)

式中，succ(ti)为任务ti的直接后继任务集合。以自底向上的方式将所有任务划分至不同的层次，如图1中层次1～5。对于出口任务而言，其层次值则恒为1。

然后，所有任务依据其层次值可归于任务层次集TLS中，并表示为：

TLS(l)={ti|NL(ti)=l}

(6)

式中，l为整数层次值，且l∈[1,…,NL(tentry)]。

3.2 预算分割

预算分割的主要思想是将用户定义的工作流预算在工作流层次间进行重新分配，并在考虑该层次所分配的可用子预算的前提下将第个任务调度至实例。本文提出两种预算分割的方法，包括：

(1) 区域分割法Area。由于工作流的结构会对调度结果产生实质影响，该方法联合考虑工作流的高度和宽度。Area法重点考虑。①工作流的高度：即每个层次的预算分割正比于所在层次与入口任务间的距离；②工作流的宽度：即每个层次的预算分割正比于所有层次中包含的任务数量。

(2) 漏斗分割法All in。该方法将全部预算赋予工作流入口任务，减去相应调度费用后，依漏斗模式依次将剩余预算传递至下一层次。

3.3 任务选择

工作流基于约束关键路径CCP选择执行任务。为了搜索工作流中所有的约束关键路径，利用文献[4]中的介绍的升秩排序upward rank和降秩排序downward rank方法，并分别对两种方法作如下改进：

改进升秩排序

(7)

改进降秩排序

(8)

式中，AETi和ACTi分别为任务ti的平均执行时间和平均通信时间。

改进的升秩和降秩排序方法整合了任务前驱或后继的通信时间，替代原始方法仅选择最大值的做法。在改进方法中，拥有越高出度或入度的任务，将拥有更高的优先级，具有更大概率被优先执行，而在下一约束关键路径上的更多任务也将被考虑为就绪任务。WTSBC算法根据Mrankup(ti)+Mrankdown(ti)定义任务优先级，所有任务首先根据该值进行排序，拥有最高值的任务被选择为第一个关键路径。关键路径搜索算法如下：

算法1关键路径搜索

1. procedure FindCP(DAG G)

2. For all taskti∈G do//遍历工作流的所有任务

3. calculate rankup, rankdownand ranksum//计算各个任务的升秩和降低值及其和

4. end for

5. CPlist←∅//初始化关键路径列表为空

6. while there is an univisited task in G do//寻找未访问任务

7.ti←biggest ranksum//寻找最大秩值和

8. CP←∅//置关键路径为空

9. whiletiis not null do

10. addtito CP//添加任务ti至关键路径

11.ti←maxtj∈pred(ti)(ranksumtj)//寻找最大父任务秩值和

12. end while

13. add CP to CPlist//添加关键路径至CP列表

14. end while

15. end procedure

3.4 实例选择

实例选择阶段的目标是选择最合适的实例执行CCPs。由于CCP上所有任务执行于同一实例上，可以避免任务间的通信代价。该阶段首先根据以下公式计算每个任务在每个实例类型上的执行时间和执行代价，并形成两个集合Cost和Time：

(9)

(10)

式中，Cbest为在所有实例上执行当前CCP的最小代价。

在实例pj上执行当前CCP的代价为C(CCPi,pj)。式(10)中，subBudgetCCPi为对于一个CCP中在不同层次上所有任务所分配的子预算subBudget之和，定义为

(11)

在Time集合中，在实例pj上执行当前CCP需要的时间为ECT(CCPi,pj)的函数(式(11))。ECT为一个CCP在单个实例上完成执行的最早时间(单个任务的ECT定义为式(2))。在所有实例上执行CCPi的最大与最小时间分别为ECT(max)和ECT(min)。

为了寻找最佳实例，算法利用如下式的Time-Cost调整因子：

(12)

拥有最高TCAF值的实例将作为执行当前CCP的最佳实例侯选。当分配于层次l的总预算已经花费完(即subBudgetCCPi=0时)但仍然有未调度任务时，对于式(9)，有：

(13)

因此，由于没有预算盈余，无法开户一个新的实例。此时，式(12)也等于0。并且，如果式(10)变为负值，则表明在所选实例上的执行代价高于可用子预算subBudgetCCPi。

实例提供后，用户需要支付整个帐单周期的费用，即使任务在周期结束前完成。一种降低任务执行代价的方法是继续利用已支付实例的剩余能力执行任务，如此，这类任务的执行代价即为0。WTSBC算法将利用这类已支付的剩余能力执行就绪任务，以零代价方式降低任务执行时间。

将单个CCP分配至一个实例后(代价为C(CCPi,pj))，需要更新每个层次的剩余预算。在工作流为最早任务分配更高的预算通常可以得到更小的执行跨度。算法2给出了预算的更新过程。

算法2更新剩余预算

1. procedure UPDATE BUDGET(CCP,cost)

2. while |CCP| and cost>0 do

3.ti←last task in CCP

4. removetifrom CCP

5. LB←subBudget(l)ti∈TLS(l)

6. if LB>cost then

7. LB←LB-cost

8. cost←0

9. end if

10. end while

11. end procedure

WTSBC算法的一个重要步骤是将未使用的剩余预算传递至下一层次继续使用。定义剩余层次预算SLB为层次l的所有任务调度后剩余的费用预算，表示为：

(14)

剩余预算将传递至下一层次l+1。

3.5 预算分割算例

本节以一个实例展示预算在不同层次的分割情况。图1所示为一个包括10个任务的工作流结构图。图中左栏信息为通过式(5)计算的层次值，右栏信息为以出口任务为起始点在每个层次中包含的任务编号。该算例中，最大层次数Nmax=5，预算为165。

(1) 高度。每个层次分配一个相对其工作流高度的加权预算值，计算为

预算因子BF计算为

图1 工作流示例

举例层次4包含任务B和C，分配的预算值为

4×BF=4×11=44

(2) 宽度。每个层次依据对应层次中任务数量得到其预算分配：

举例包含两个任务的层次4分配的预算为

2×BF=4×16.5=33

(3) 区域。该方法中，每个层次的预算分配为高度和宽度方法之和，计算为

预算因子BF计算为

预算根据图1中右栏数字之和进行分配。

举例层次3的预算分配为

(4+5+6+7)×BF=22×3=66

(4) 漏斗分配Allin。总预算分配至层次5，调度该层次的所有任务后，剩余预算传递至下一层次。

表1是图1所示工作流所有层次的预算分配。

表1 不同分割方法的层次预算

4 仿真实验

4.1 实验配置

云可以不同的价格提供不同能力的CPU、内存、存储和网络带宽实例。本文利用Amazon弹性计算云的资源模型，其实例可按需提供。价格模型利用即付即用的最小帐单周期模型。该价格模型下，如果实例仅被利用1 min，用户同样支付1 h的帐单费用。该实例的代价和类型如表2所示。

表2 实例类型

仿真场景为包含6个不同实例类型构建的一个数据中心模型，实例特征基于Amazon EC2(见表2)。实例间的平均带宽固定设置为20 MB/s。EC2单元处理能力以每秒进行的百万浮点运算次数MFLOPS衡量。理想云环境中，资源提供不存在延时，但是，某些因素可能导致时间上的延时，如：操作系统、实例类型、数据中心的区域地点和同时请求的资源数量等因素，均可能导致资源启动时间上的延时。因此，仿真为了贴近实际云场景，基于EC2中的测试数量设置97sec的实例启动时间。

利用3种常见的数据密集型科学工作流应用：CyberShake、Montage和LIGO，真实负载状况评估算法性能。实验中将预算由松至紧进行设置，同时统计调度成本和成功率情况。另外，令最快调度FS为基准调度方案，基准调度为忽略代价得到的最快可能执行时间，计算为

(15)

定义预算为最快调度的函数，表示为

budget=α×FS, 1<α<6

(16)

预算因子α的取值从1开始(考虑为最紧约束，对应于最快调度)，递增至6(考虑为最松约束)。

Amazon EC2实例在提供时间内按1 h的帐单周期支付费用。同时，为了比较不同规模工作流下的性能，为工作流分别配置50、100、200、500和1 000个任务。利用Pegasus工作流发生器创建前文的三种科学工作流结构，并利用CloudSim实现调度算法，完成算法仿真。

4.2 结果分析

本节实现了预算分割方法分别为Area和All in时的任务调度算法，分别命名为WTSBC-Area和WTSBC-All in。并且选择预算约束异构最早完成时间算法BHEFT[10]和基于关键任务的贪婪算法(Modified Critical Tasks Scheduling,MED-CC)[15]作为比较算法，两种算法均是考虑预算约束的众多代表性云工作流调度算法之一。图2和图3分别为不同算法在3种数据密集型工作流中的得到的执行跨度makespan和调度成功率。预算和执行跨度是评估算法性能的最重要基准。增加预算允许调度系统释放出拥有更好CPU、内存和网络带宽性能的更高性能实例，因此，全局工作流执行时间随着预算的增加而降低是显而易见的。

对于执行跨度，WTSBC-All in算法在所有测试工作流中均有最好的性能。BHEFT算法以逐个任务的方式进行剩余预算的分布，未考虑任务间的相关性，这样势必会增加个体任务的执行时间，因此其执行跨度是最差的。MED-CC算法试图以重调度的方法进行任务的重新分配，直到满足预算约束，这种做法会增加算法的时间复杂度。WTSBC算法以任务和预算层次间分割的方式可以最大化任务的并行执行程度，降低全局工作流任务的执行跨度。

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

同时，当预算极其受限时(预算因子相比更小)，BHEFT算法拥有最差的性能。例如：在3种工作流类型的前两个预算因子中，BHEFT算法的执行跨度几乎是其他算法的3倍。利用Area和Allin方法进行预算分割的WTSBC算法均拥有比MED-CC和BHEFT更低的执行跨度，且多数情况下，两种预算分割方法间的差异并不大。总体来说，WTSBC算法在执行跨度性能上全面优于MED-CC和BHEFT算法。

调度成功率可以反应算法是否能够在满足预算约束的情况下完成工作流调度。可以看出，宽松下的预算可以增加调度成功率，这是由于预算越多，算法得到的调度方案满足预算的概率将越高。WTSBC-Area算法在Montage工作流的第1个预算因子中拥有100%失效率，表明该算法此时无法得到调度方案。搜索合理调度方案的最差性能发生在LIGO工作流中，此时MED-CC算法在前3个预算因子中拥有20%～30%的失效率。

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

5 结 语

为了解决关联式云工作流任务的调度优化问题，本文提出了一种基于预算约束的调度算法。算法以一种四阶段的方式求解了工作流任务与实例间的调度映射解，包括：工作流层次划分、预算分割、任务选择及实例选择。重点在预算分割方法考虑了工作流的结构特征，任务选择中则使用了改进的升秩排序与降秩排序之和的任务优先级定义，实例选择中则考虑将约束关键路径的任务调度至同一实例以降低通信代价。通过3种工作流类型下的仿真实验测试，结果表明，所提算法在多数测试数据中，其执行效率和调度成功率均高于同类型算法。