云环境下基于通信开销的并行任务调度策略

摘要：云环境下，任务的执行效率受限于任务间的通信时间和计算时间，通信时间是由于数据跨数据中心传输产生的，计算时间与任务所在集群的计算能力有关，有效减少任务因等待数据的到来而产生的时间开销可提高任务的执行效率，进而降低用户租赁云资源的费用，提出基于任务复制的调度策略，以提高任务的并行性。经性能分析，该策略在提高任务的执行效率方面有一定的贡獻。

关键词：相关性；通信开销；阈值；任务复制；任务调度

中图分类号：TP301.6 文献标识码：A

文章编号：1009-3044（2019）10-0225-03

开放科学（资源服务）标识码（OSID）：

Parallel Task Scheduling Strategy Based on Communication Overhead in Cloud

DUAN Ju

（Shandong Management University， Jinan 250357， China）

Abstract： In the cloud environment， the execution efficiency of tasks is limited by the communication time and computing time between tasks. Communication time is caused by data transmission across data centers. The computing time is related to the computing power of the cluster where the task is located. Effectively reduce the time overhead incurred by the task waiting for the arrival of data， which can improve the execution efficiency of the task. In turn， it can reduce the cost for users to rent cloud resources. A scheduling strategy based on task replication is proposed to improve the parallelism of tasks. Through performance analysis， this strategy has a certain contribution to improve the efficiency of task execution.

Key words： task correlation； communication overhead； threshold value； task replication； task scheduling

云计算[1]作为新时期的一种新技术发展迅速，其与大数据的研究应用更是关系密切，云计算为大数据提供了无限的存储空间和计算能力，让大数据的研究应用成为可能，而对大数据的处理是根据任务而定，即人们的需求决定了大数据的研究方向，而需求就是由一个个任务完成的，因此，如何提高任务的执行效率对于现实需求具有极大的研究意义。

根据前期的研究[2-4]可知，任务的执行离不开数据，相关任务之间存在数据相关性，任务的执行效率取决于数据到来的快慢，如果相关数据在相同的集群上，那么运行速度相对较快，但考虑到负载均衡[5]，不可能所有的数据都在一个集群上，因此如何使相关性大的数据在同一个集群上至关重要。

任务调度[6]问题是云计算环境下研究课题中的一个重要内容，众多研究学者提出了很多任务调度的算法，算法研究的重点集中在如何减少任务间的时间开销，而时间开销主要是由于不同集群上任务的通信产生的。目前应用最广泛的调度算法是基于启发式的调度算法[7]，其中，由于基于任务复制的调度算法可以消除任务间的通信开销，大大降低任务的等待时间，从而提高任务的执行效率，使得基于任务复制的调度算法得到了广泛的关注。

目前任务复制算法已经有很多，基于复制的异构多核任务调度算法[8]，应用了二路复制方法，在减少任务因复制而导致的冗余量增大方面有极大的改善，从而减小了任务的调度长度； 基于任务复制的动态关键前驱调度算法 [9] 改进了粒度定义，优化了任务调度长度，找到了更优解；OSA[10]算法（Optimal Task Duplication based Scheduling Algorithm）将尽量多的父节点与子节点分配到同一个处理机上，来减少任务间的通信开销，但是没有考虑处理机的负载均衡问题。

随着研究的不断深入，任务复制算法也得到了很多改进。PTSAC算法[4]（Parallel Task Scheduling Algorithm based on Correlation）该算法在任务调度之前根据任务间的通信开销进行队列划分，以提高任务划分的效率；SWFEBC算法[2]（Scientific workflow execution optimization strategy based on Clustering）该算法对工作流中的任务进行静态划分，通过任务复制的方式减少任务簇之间的联系，从而减少任务的等待时间，提高任务的执行效率；文献[11]提出一种TDMCP算法（Task Duplication Multi Critical Path）主要考虑关键路径上的任务对整体任务调度的影响，该方法只复制首任务来影响后续任务的执行，达到提高整体任务调度效率的目的。

任务分配是为了更好的完成任务调度，遗传算法是一种启发式的算法在任务调度中得到了广泛使用，由于自身存在早熟等不足，本文采用改进的遗传算法进行任务调度。为了提高云环境下任务的执行效率降低执行费用，本文提出了一种基于通信开销的并行任务调度策略。

1 问题模型分析

1.1 相关定义

一般来讲，多个任务协作完成一个工作流，任务之间是有相互联系的，这种制约关系可以用DAG图来表示，即G={V，E，M，C}，其中：

V={ti|ti是工作流中的任务，i=1，2，3，…，n}；

E={eij| eij表示ti、tj间的边，ti是tj 的父节点，表明ti、tj间有通信}；

M={mij| mij表示ti与tj间的通信开销，ti是tj的父节点}；

C={ci| ci表示ti的计算开销}。

定义1：通信开销mij表示任务i和任务j在任务调度处理中要进行通信，任务i是任务j的一个前驱，j在执行过程中要用到i的处理结果，M的值越大表示两任务间的通信开销越大即两任务相关性越大；

定义2：计算开销ci表示执行任务i时在处理器中除了通信开销以外的一切开销，计算开销越大说明任务越大越烦琐；

用来描述通信开销与计算开销之间的关系，由M和C的差值来计算，结果有三种情况分别为大于0、等于0、小于0，TSV越大说明通信开销占主导地位即任务间的相关性越大，TSV小于0时的绝对值越大说明计算开销占主导地位即任务本身烦琐与其他任务相关性小，根据这三种情况对任务采取不同的分配策略。

为了更清晰的表述，下面通过举例方式进行说明，系统任务间的关系图可用DAG图来表示，如图1所示。

图中圆圈表示任务顶点，在圆圈中的1到15表示任务T1-T15，每个任务都有计算开销，有的任务间有通信开销；计算开销用C（Ti）来表示，通信开销用M（Ti，Tj）来表示，在图中用二元组（C，M）来表示，即有向线段上的二元组（2，1）表示任务i的计算开销是2，任务i与任务j之间的通信开销是1。

1.2 任务分配

为了减少不同处理机上任务之间的通信开销，在分配任务时相互间通信开销大的任务分配到同一个处理机上以提高任务执行效率。根据二元组中第二个元素的值进行分配。广度优先遍历DAG图，图1中任务1、任务2、任务3都没有前驱，所以把任务分成三个队列{T1}{T2}{T3}，T4的前驱只有T1所以把T4加入队列1{T1，T4}，以此类推，把T7、T11也加入队列1{T1，T4，T7，T11}，当出现两个前驱的时候，则比较二元组中第二个元素M值，加入值大的前驱所在队列，所以T12加入队列1，最终的三个队列分别为{T1，T4，T7，T11，T12，T14}、{T2，T5，T8，T13，T15}、{T3，T6，T9，T10}。如图2所示：

1.3 基于通信开销的任务复制

任务复制主要是把不同队列中通信开销大的任务进行复制。不同的队列分配到不同的处理器上，处理器间的通信开销比同一个处理器上的通信开销要大，为了降低通信开销提高任务执行效率要对不同处理器上的相关性大的任务进行复制，当然不是把所有的有关联的任务都进行复制，相关任务的全部复制不仅会增加计算开销而且会增加空间资源的开销，代价太高。本文采用基于阀值的任务复制方案，该方案能减少因任务全部复制而引起的空间资源浪费同时可以达到降低通信开销的目的。同构的系统上所有处理单元的运算能力相同，所以本文假定所有的系统是同构的。

设置阀值与复制任务的目的就是使得总开销最小，开销包括时间开销与空间开销，时间开销包括通信开销和计算开销。复制相关任务会降低通信时间开销但会增加计算开销和空间开销，是用空间换取时间所以要权衡两者的利弊。

1.4 并行任务调度模型

任务的调度模型如图4所示：

经过任务复制和任务分配操作后，每个处理机上的任务队列基本都是相互独立的，还有少数的有关联但对多个处理机进行并行处理没有太大影响。这样就可以在每个处理机上独立应用任务调度算法，只有在遇到个别任务时才需要与其他处理机进行通信大大降低了通信开销，提高了任务执行效率。本文采用文献[3]中改进的遗传算法进行任务调度。

2 性能分析评价

衡量算法的优劣一般从时间和空间两个方面来评价，本文也采用这两个标准。任务的总执行时间包括通信时间、处理时间以及阀值比较时间和任务复制时间，而通信时间是决定总执行时间的关键因素，通过任务复制可以减少通信时间但会增加处理时间，如果减少的时间不能抵消增加的时间那么任务复制是没有意义的只会增加存储单元的使用，而阀值就是为了避免这种情况的发生并且使用简单的函数来做比较是高效的。这样分配到每个处理机上的任务与其他处理机上的任务基本是独立的只有很少的通信开销，然后可以并行任务调度，可见使用阀值进行任务复制可以提升任务调度的整体性能。任务总执行时间的表示如下：

3 总结

本文提出的任务复制策略是以增加空间资源消耗为代价来消减通信开销，设置阀值是为了尽量减少空间资源的使用，在增加的计算开销和消减的通信开销能够相互抵消或者低于时才进行任务复制，先进行任务分配使得每个处理机上的任务队列基本都是相互独立的，不同处理机间通信很少，这样既能减少因任务全部复制而引起的空间资源浪费同时可以达到降低通信开销的目的，然后在每个处理机上用改进的遗传算法进行任务调度。

参考文献：

[1] CHEN W， ALTINTAS I， WANG J， et al. Enhancing smart re-run of Kepler scientific workflows based on near optimum provenance caching in cloud[C]//Services （SERVICES）， 2014 IEEE World Congress on. IEEE， 2014： 378-384.

[2] 段菊， 陈旺虎， 王润平， et al. 云环境下基于聚簇的科学工作流执行优化策略[J]. 计算机应用， 2015， 35（6）：1580-1584.

[3] 陈旺虎， 段菊， 俞茂义. 允许违反局部时间约束的科学工作流调度策略[J]. 计算机工程与科学， 2016（11）：2165-2171.

[4] 段菊， 于治国. 云环境下基于相关性的并行任务调度策略[J]. 计算机技术与发展， 2018， 28（06）：178-183.

[5] 喻莉， 阮文涛. 负载均衡技术的研究与实现[J]. 计算机技术与发展， 2007， 17（8）：120-122.

[6] 刘少伟， 孔令梅， 任开军，等. 云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J]. 计算机学报， 2011， 34（11）：002121-2130.

[7] 贾丽云， 张向利， 张红梅. 分布式系统下的启发式任务调度算法[J]. 计算机工程与应用， 2017， 53（12）：63-69.

[8] 周超群， 周亦敏. 一种改进的基于复制的异构多核任务调度算法[J]. 电子科技， 2017（06）：63-68.

[9] 何琨， 赵勇， 黄文奇. 基于任务复制的分簇与调度算法[J]. 计算机学报， 2008， 31（5）：733-740.

[10] PARK C I， CHOE T Y. An optimal scheduling algorithm based on task duplication[C]//Parallel and Distributed Systems， 2001. ICPADS 2001. Proceedings. Eighth International Conference on. IEEE， 2001： 9-14.

[11] 李靜梅， 尤晓非， 韩启龙. 基于任务复制的多关键路径任务调度算法[J]. 计算机工程与设计， 2014， 35（5）：1639-1645.

【通联编辑：梁书】