云计算中一种带任务重复机制的任务划分策略

摘  要： 提出了一种带任务重复的任务划分策略算法D-ITPS（Improved task partitioning Strategy with duplication），该算法首先将DAG图中的一些满足归并条件的任务进行归并，然后将所有的任务按照划分策略划分为一个个包，将包按照Max-Min策略整体调度到处理器上执行，在完成基本的映射后，检测每个染色体是否可以通过任务重复来减少通信时间，若可以则在处理器的空闲时间隙重复任务以减少总调度长度。

关键词： 云计算;复杂DAG图;调度算法;任务重复;调度长度

中图分类号： TP30    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.12.002

本文著录格式：张银娟. 云计算中一种带任务重复机制的任务划分策略[J]. 软件，2019，40（12）：0612

A Task Partitioning Strategy With Task Repetition Mechanism in

Cloud Computing Environments

ZHANG Yin-juan

（Guangling College of Yangzhou University， YangZhou， Jiangsu， 225000）

【Abstract】： We presented an improved task partitioning strategy with duplication D-ITPS， the algorithm firstly merge tasks in DAG which meet merging conditions， then all of the tasks are divided into small packages， which are scheduled to processors according to Max-Min algorithm. After the completion of basic mapping， detecting whether each chromosome can reduce communication time by duplicating tasks， if possible， duplicate this task in the idle gap of processor to reduce the total schedule length.

【Key words】： Cloud computing; Complex DAG; Task scheduling; Task duplication; Makespan

0  引言

云計算[1-3]环境下工作流的调度研究是一个NP完全问题，针对此问题提出许多算法，至今也有一些基于元启发式的算法用来解决NP问题，如：粒子群算法（PSO）[4]、禁忌搜索（TS）[5]，模拟退火（SA）[6]，遗传算法（GA）[7]等。相较之下，GA被认为是优化领域的一种好的方法且通过运用进化的原则在多项式时间内从大量搜索空间和并行搜索中获得高质量的解决方案。它提供一些方法来估算有效参数。

本文主要借助于遗传算法来求得调度的最优解，现有的一些基于遗传算法（GA）的算法，如文献[8-10]提出了应用于工作流调度的算法，但是它们均没有考虑到云计算中异构组件的特点，且并不适合云系统这样的异构分布式计算系统。基于GA的算法，有的通过随机选择来选择初始种群，有的在工作流的同一阶段用优化方法将任务排序，比如最先完成的任务，最小依赖的任务，最大依赖的任务，其中一些用具有至多两个输出节点的简单图来表示。文献[11]中考虑到云环境下异构的特性，但是该论文提出的算法中使用的是简单DAG图，而云环境下的工作流任务间的关系复杂，转换为DAG图后任务间的分层不明显，且每个任务的大小和其前后继任务都各不相同，显然简单的DAG图不能适用于云环境中。文献[12]提出了异构启发式算法（HSGA），它考虑到了异构环境下任务的复杂程度，采用复杂的DAG图对任务进行描述和调度，但是其交叉率和变异率均固定，易造成“早熟”的现象。通过以上对国内外研究现状的综述，可以看出针对云计算环境下的调度问题，目前学术界提出的方法策略非常多[13-14]，大多数从优化调度长度来考虑，也有从节能和负载平衡方面来考虑的。大部分学者将云计算环境中的工作流转化成简单的DAG图来考虑，从云计算任务复杂的程度来看，简单DAG图显然是不适用于云环境中的。本文通过对云环境下工作流进行处理，将其转化为复杂的DAG图并对其进行调度，同时考虑负载和计算资源性能的基础上，尽可能减少调度长度。

1  D-ITPS算法

1.1  D-ITPS的简单抽象模型

图1给出了本文提出算法的简单抽象模型。

图1  任务抽象模型

Fig.1  Task abstract model

用户提交的作业转为DAG图后，对DAG图中的一些满足归并条件的任务进行归并，归并完成后使用任务划分策略将任务有效地划分并分配到处理器上形成一个染色体。再根据 任务重复策略利用处理器上的空闲时间隙进行重复特定的父任务以减少总完成时间。任务重复策略结束后形成新的染色体，取一定数量的染色体进行随机交叉、变异，得到一个最优的调度方案，将该调度方案提交到云环境下进行计算调度长度、通信开销等，最后对结果进行分析。

1.2  编码及算法

1.2.1  编码

在遗传算法中，每个染色体用来表示问题的一个解，染色体的编码方式有很多，采用何种方式进行编码则有当前问题的需求来决定。该算法中采用如图2的编码方式。

V1 V3 V4 V2 V5 ···· V9

P2 P9 P3 P1 P8 ···· P25

图2  单个染色体的简单编码

Fig.2  Simple coding of a single chromosome

1.2.2  任務归并阶段

本文提出的算法首先对DAG图中的一些任务进行归并，归并后将归并的任务看成一个大任务，其归并后的大任务的计算时间和存储空间均采用归并的小任务的计算时间和存储空间求和方式来计算。如公式（1）（2）所示。

若任务与任务满足任务归并条件，其中任务在各个处理器上的计算开销为 ，存储开销为，任务在各个处理器上的计算开销为，存储开销为，任务合并后形成新任务，其计算开销及存储开销为：

（1）

（2）

任务归并后其实质还是两个任务，仅仅是将两个任务绑定，调度时调度到同一个处理器上。那如何才可以将任务进行归并？需同时满足如下两个条件：

（1）当前任务有且仅有一个直接父任务并且该父任务也有且仅有一个直接子任务，即是该任务;

（2）该任务与其直接父任务间的通信开销大于等于其在不同的处理器上的最大计算开销。

满足上述条，将子任务归并到父任务，将其看成一个大的任务，调度时调度到同一处理器上。

归并算法如算法1.1所示。

算法1.1  归并算法

Step 1： for DAG图中所有任务do

Step 2：    if（（当前任务有且仅有一个父任务，即 ）&&（是父节点的唯一子任务，即））then

Step 3：             if then

Step 4：                   将任务归并到父任务，归并后的任务为

end if

end if

end for

1.2.3  任务划分策略

任务划分主要目的在于最小化云计算环境中所有参与任务的总完成时间。任务的有效划分对于最小化完成时间是有必要的。DAG图调度中将任务映射到处理器上的时候要求要保有任务间的约束关系，这是一个NP问题。有效地分析任务之间的互斥关系有助于资源共享。在本算法中，将归并后的任务划分为一个个任务包的形式，再将任务包调度到处理器上执行。

任务划分策略主要根据任务的通信时间及任务间的约束关系进行划分初步的任务包。首先将任务按照其通信时间的大小降序排列形成队列，将排列在一起且满足拓扑顺序的任务划分为一个包。划分算法如算法1.2所示，首先将队列中符合拓扑顺序的通信时间小的任务划分到通信时间大的任务包中，通信时间用任务输出数据的大小除以资源间的带宽，对于出口节点，该值为0。如公式（3）所示。

（3）

表示任务向任务输出数据的大小，表示任务与任务所在处理器之间的带宽。

算法1.2  划分策略

Step 1：计算所有任务的通信开销值comm_cost

Step 2： 按照comm_cost值将任务降序排列形成队列

Step 3：for队列中的每个任务do

Step 4：   if（（ ）&&（与有约束关系） then

Step 5：        合并任务

end if

end for

任务分为包后，定义包的几个参数：

定义1.1  将DAG图中的任务分为包后，在每个包中，类比于DAG图中的任务将包定义为四元组形式：

（1）表示任务节点的集合;

（2）是边的集合;

（3）与表示不同的两个包。

定义1.2  任务包与任务包之间有多条边相连，包间的通信开销为其所有在包中节点间的通信时间的均值，计算公式如下：

（4）

表示连接包边的权值之和，即所有在包中任务间的通信时间之和，表示连接两包的边的个数。

定义1.3  任务包在处理器上的执行时间取所有任务执行时间和的平均值。

（5）

表示任务包中任务的个数，表示包中所有任务在处理器上的平均执行时间之和，表示所有处理器的个数。

使用算法1.2后任务大致分为几个包，对未被分配到包中的任务，采用算法1.3将任务划分到各个包中。其基本思想是先按照所有包中任务的个数对包进行升序排列形成队列，对于未被分到包中的任务，查找队列中第一个包中的主要任务，即通信时间最大的任务。若主要任务是任务的父任务，则将归入包中，更新包的相关参数。否则将查找任务的主要父任务MIIP所在的包，将归入到包中。

算法1.3  后续划分策略

Step 1： 计算当前所有包中任务的个数，按照升序进行排列

Step 2：while所有未被分包的任务do

Step 3：      取包中任务

Step 4：      取包队列中的第一个包，找出通信开销最大的任务

Step 5：      if  then

Step 6：          标记

Step 7：          更新包的參数

Step 8：       else

Step 9：         查找的MIIP任务

Step 10：         if 已在包中 then

Step 11：            标记

Step 12：            更新包的参数

Step 13：          else

Step 14：             标记

Step 15：             更新包的参数

end if

end if

Step 16：    按照包中任务个数进行升序排序

end while

在分包的过程中，要注意并行性及通信开销的平衡，如定理1.1。不能因为顾及通信开销将大量的任务放到同一包中，这样包中的任务会急剧增多，最坏的情况是所有任务集中到一个处理器上执行，这样就不能体现多处理器的优点，即不能兼具并行性的优点。当然由于处理器个数的有限性，不能将任务尽可能分为多个包，导致每个包中的任务数量极少，这样会造成资源的浪费。

定理1.1  设是DAG图中的任务，表示任务间的通信开销，用边上权值表示。最优的调度策略是根据Max-Min（最大并行性，最小通信时间）权衡。

证明：根据Babb[15]“由谁来处理大任务包取决于所在系统结构的不同。”总之，大粒度任务包意味着在执行过程中要处理的底层人物的数量较多[16]。任务包用于减少通信时间的开销，同时在任务处理器数量一定的情况下减少了处理器的负载。任务包的顺序执行降低系统的并行性。任务包的大小由其包含的任务的大小决定。如果任务包的过小则由于包间上下文交换会加重处理器的负载，反之若包的颗粒过大，则并行性降低。并行性与通信开销的大小要采用Max-Min权衡来控制。

综上，为权衡并行性与包的颗粒大小，定义两个阈值与来控制包中任务的个数，若包中任务个数小于，则优先向该包中添加任务，若包中任务个数大于，则在分配未分配的任务时，将该包从包队列中移除。在本文中与的取值为：

（6）

（7）

在按照任务划分策略将任务划分为包后，将包分配到资源上使用Max-Min算法[17]来实现。Max-Min算法首先计算任务包在每个处理器上的完成时间，按照各个包的完成时间将包进行降序排列，将虚拟机列表按照计算能力进行降序排列，然后按照包的排列顺序及虚拟机列表的排列顺序将各个包分配到处理器上。算法实现如算法1.4所示：

算法1.4  Max-Min算法

Step 1：判断任务包队列是否为空，不为空，执行Step2，否则执行Step 7

Step 2：对于任务包队列中所有包，求出映射到所有处理器上的最早完成时间

Step 3：找出有最大最早完成时间的任务包并找出对应的处理器

Step 4：将任务包映射到该处理器，更新任务包列表

Step 5：更新处理器的预期就绪时间

Step 6：更新其余包在处理器上的最早完成时间，返回Step1

Step 7：按照图2中的编码方式输出调度序列

在将任务按照图2的编码方式编码后，继续执行算法1.5直至求出最优的调度方案。

1.2.4  任务重复阶段

本阶段中任务对算法1.4中输出的调度序列进行处理，在调度过程中，如果存在空闲时间隙，将利用这些空闲时间隙来执行重复任务和候选节点，以期将任务总完成时间提前。

当一个任务调度到处理器上时，通常将此时间定义为任务的到达时间。但是任务的实际开始时间并不是任务的到达时间，还需考虑处理器是否空闲以及其所有前驱任务的数据均传输到处理器上。在准备执行任务前需等待其所有直接前驱任务将数据传达以此来遵守DAG图优先关系约束。

DAG图中优先级和通信延迟的约束使得处理器上产生空闲时间隙，无法实现数据提前传达。如何判断是否存在合适的空闲时间隙定义1.4给出了方法描述：

定义1.4  [18]给出一组任务将其调度到处理器上，存在空闲时间隙（在任务和之间）满足如下条件即可容纳任务，

（8）

其中，和分别表示时间隙的开始时间和结束时间。表示任务在当前处理器上的执行时间。表示任务在处理器上的开始执行时间。假设没有合适的空闲时间隙，任务调度到处理器上，其开始时间决定于处理器的空闲时间，如图3所示。

定义1.5  （MIIP[19]，Most  Important immediate parent）任务的所有直接父任务中最晚到达的任务称为最重要的直接父任务，用符号表示，因为它阻碍了任务的开始时间。

所有任务的MIIP任务数据到达时间计算公式如下：

（9）

表示任务前驱任务的集合， 表示前驱任务与当期那任务在同一处理器上执行，则此时的为0。表示前驱任务与子任务不在同一处理器上执行，则计算如公式（10）所示。

（10）

图3  空闲时间隙与重复任务

Fig.3  Idel gap and repetitive tasks

由于受父任務的数据到达时间影响，任务的开始时间受到一定限制。前驱任务的数据到达子任务所在处理器有两种途径：

（1）在合适的空闲时间隙重复重要直接前驱任务，减少任务之间数据的传输开销;

（2）将子任务尽可能调度到直接父任务所在的处理器，从而避免通信开销。

第二种方法显然会导致同一处理器上的任务过多，负载过重，从而处理器的计算能力下降，导致任务的总完成时间并不能提前。

任务重复算法主要从在空闲时间隙重复任务着手，主要按照两种规则重复任务，如下：

（1）优先重复直接父节点中出度最大的任务。重复出度最大的父任务是因为父任务的出度大，它影响最多的子任务的开始时间，将出度最大的父任务重复执行，则不仅仅可以提前当前子任务的开始时间，其余的该父任务的子任务的开始时间也会相应的提前。

（2）重复直接父节点中的MIIP任务。重复MIIP任务是因为MIIP任务的完成时间限制当前任务的开始时间，将其在子任务所在的处理器上重复执行，则当前任务的开始时间提前。

为避免冗余重复，只重复有重要数据输出的父节点。在每次重复任务后，任务的总完成时间重新更新，若重复该任务，总完成时间不改变则删除该重复任务，处理器一直重复此操作直至无MIIP任务或出度最大的父任务，或者无空闲时间隙。所有处理器均执行检查时间隙，重复任务，计算完成时间的操作，直至所有任务均被检查和调度完成。

当前处理器上任务执行完成时间和其直接前驱的数据到达时间，计算公式如（11）：

（11）

表示第一个可容纳执行任务的空闲时间隙，表示处理器空闲时间。

任务的完成时间计算公式如下：

（12）

算法的总完成时间为：

（13）

查找并重复任务的算法表示如算法1.5所示。

算法1.5

Begin

Repeat

{

Step 1：   ←查找任务在处理器上的开始时间

Step 2：

Step 3：  ←任务所有任务中出度最大的父任务节点，存在几个以上相同出度，比较完成时间，完成时间最大的任务

Step 4： ←任务的MIIP任务

Step 5： if（和均不存在或均已调度到当前处理器上）

返回值

else if（处理器上存在适合执行或的空闲时间隙）{

←计算任务在处理器上的完成时间

←计算任务在处理器上的完成时间

if

在处理器上重复任务

else if

在处理器上重复任务

else

返回

}

else

返回

}

End

表1  参数表

Tab.1  Parameters

类型 参数 取值范围

资源参数 资源个数 30

资源速度 500-1000（MIPS）

资源间带宽 10-100（mps）

CCR值 0.25

任务参数 任务个数 30-100

任务长度 12-72（× MI）

任务失败率 -

算法参数 种群大小 20

交叉率 0.5

变异率 0.5

精英选择率 0.75

任务迭代次数 20

2  D-ITPS算法仿真实验

2.1  仿真环境

本文中提出了一种改进的带任务重复机制的划分策略D-ITPS算法，为验证该算法的有效性，将其与HEFT[20]算法和OTPSD算法[21]进行比较。

2.2  仿真结果与分析

图4对比三种算法，NSL参数中总完成时间作为其中的一个变化因子，本文中提出的D-ITPS算法的总完成时间最少且NSL性能最优，但随着CCR值的增大，即任务间的通信量变多，通信时间延长。在划分包的时候虽然会减少一定的通信时间，但是由于并行性和负载均衡的限制，以及包粒度的定义和划分策略的局限性，总完成时间会有所增大，但总体相较于HEFT算法和OTPSD算法有所提升。

图4  任务的NSL性能分析

Fig.4  NSL performance analysis of tasks

图5中随着任务数量的增长，平均NSL值会有所变化。在任务数在150-300时，提出的算法的平均NSL值小于另两种算法。

随着任务通信时间的延长，D-ITPS算法的性能高于其余两种算法的性能。在本算法中任务处理器个数一定，在多处理上执行的时间越短，Efficiency值越大，性能越优。

图5  任务的平均NSL性能分析

Fig.5  Average NSL performance analysis of tasks

图6  任务的Efficiency性能分析

Fig.6  Efficiency performance analysis of tasks

3  总结与展望

本文提出了任务划分的策略及任务重复机制，采用另一种方式将任务进行预处理。首先将DAG图中的任务进行归并，归并后按照划分策略將任务划分到包，将包整体调度到处理器上，划分包的主要目的在于减少任务间的通信时间。再利用处理器的空闲时间隙重复关键父任务进一步减少通信时间，优化总完成时间。

实验证明本文中提出的算法在总完成时间的优化上有一定的效果，同时在资源负载以及任务失败率上有一定的成效。

然而，在算法中仍存在一些不足：

（1）算法中均提出了任务的调度模型，但是与真实的云计算模型相比仍过于简单，存在一定的差距。

（2）D-ITPS算法中规定了重复的任务，主要重复最晚完成时间的父任务和最大出度的父任务，固定地重复任务并不一定能很好地利用时间隙，重复的任务有可能是对总完成时间没有影响的。

（3）任务划分策略中，划分任务包时并行性与颗粒大小的衡量采用阈值来定义，阈值的大小取值并不能保证最好地权衡并行性与包的粒度大小。

针对以上问题未来将进一步研究

（1）对算法中提出的任务调度模型进一步完善，对任务及虚拟机进行建模，在调度任务时，按照实际情况考虑将任务调度到不同性能不同状态的虚拟机上，且虚拟机的个数能够进行动态调整。

（2）D-ITPS算法中可以根据当前调度到处理器上的任务与以后要调度到处理器上的任务决定要重复任务，不需要在重复任务后查找删除对总完成时间无影响的重复任务。

（3）任务划分策略中根据处理器的性能与任务的参数进行并行性与任务包粒度的权衡，而任务的个数仅为其中的参数而不是唯一决定的参数。

参考文献

[1]甘云志. 并行计算的一体化研究现状与发展趋势[J]. 电子技术与软件工程， 2019（7）： 134.

[2]卜晓波. 试论大数据云计算环境下的数据安全[J]. 软件， 2018， 39（2）： 197-199.

[3]丁顺， 陈世平. 云计算中基于包簇映射的多目标蚁群资源分配算法[J]. 软件， 2018， 39（11）： 01-06.

[4]Pandey， S. Scheduling and management of data intensive application workflows in grid and cloud computing environments[J]. Doctoral thesis， Department of Computer Science and Software Engineering， the University ofMelbourne， Australia， 2010， 42（8）： 386-474.

[5]Porto， S.， Ribeiro， C. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints[J]. International Journal of High Speed Computing， 1995， 7（1）： 45-71.

[6]Kalashnikov A V， Kostenko V A. A parallel algorithm of simulated annealing for multiprocessor scheduling[J]. Journal of Computer & Systems Sciences International， 2008， 47（3）： 455-463.

[7]K. Zhu， H. Song， L. Liu， et al. Hybrid Genetic Algorithm for Cloud Computing Applications[C]// Services Computing Con ference. IEEE， 2014：182-187.

[8]Yoo M. Real-time task scheduling by multiobjective genetic algorithm[J]. Journal of Systems & Software， 2009， 82（4）： 619-628.

[9]Omara F A， Arafa M M. Genetic Algorithms for Task Scheduling Problem[J]. Journal of Parallel & Distributed Computing， 2010， 70（1）： 13-22.

[10]Yu J， Buyya R， Ramamohanarao K. Workflow Scheduling Algorithms for Grid Computing[M]// Metaheuristics for Scheduling in Distributed Computing Environments[M]. Springer Berlin Heidelberg， 2008.

[11]李静梅， 孙冬微， 吴艳霞. 一种全局较优的静态任务调度算法[J]. 计算机应用研究， 2014， 31（4）： 1027-1030.

[12]Delavar A G， Aryan Y. HSGA： a hybrid heuristic algorithm for workflow scheduling in cloud systems[J]. Cluster Computing， 2014， 17（1）： 129-137.

[13]武濤. 基于云计算的并行动态路径搜索算法研究[J]. 软件， 2015， 36（4）： 128-132.

[14]赵辰吟， 姚文斌. 基于一种改进免疫算法的云计算任务调度策略研究[J]. 软件， 2015， 36（12）： 149-153.

[15]Babb R G I. Parallel Processing with Large-Grain Data Flow Techniques[J]. Computer， 1984， 17（7）： 55-61.

[16]Kruatrachue B， Lewis T. Grain Size Determination for Parallel Processing[J]. IEEE Software， 1988， 5（1）： 23-32.

[17]Mckellips A L， Verdu? S. Maximin Performance of Binary- Input Channels with Uncertain Noise Distributions[J]. Information Theory IEEE Transactions on， 1998， 44（3）： 947-972.

[18]Bansal S， Kumar P， Singh K. Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs[J]. Journal of Parallel & Distributed Computing， 2005， 65（4）： 479-491.

[19]Agarwal N， Gupta C， Khare A. Task scheduling through limited duplication with processor utilization in grid computing system[C]// IEEE International Conference on Parallel Distributed and Grid Computing. 2012： 921-926.

[20]Tang X， Li K， Liao G， et al. List scheduling with duplication for heterogeneous computing systems[J]. Journal of Parallel & Distributed Computing， 2010， 70（4）： 323-329.

[21]Ali J. Optimal task partitioning strategy with duplication （OTPSD） in parallel computing environments[J]. International Journal of Computers & Distributed Systems， 2013， 4（1）： 7-15.