云计算环境中面向DAG任务的多目标调度算法研究

刘军宁

（江苏省委党校图书馆 江苏省南京市 210009）

在科学领域内进行实验时通常将需要完成的任务定义成为工作流的形式，实验任务以数据流以及计算相关性作为基础，并形成链式状态的结构。当在应用密集型的计算工作流和数据流的过程中需要对大量的数据和信息展开计算，因此必要保证计算环境性能的优越性，才能够提高运行的效率。云计算环境的出现能够确保工作流拥有一个稳定的执行环境，使得工作流能够获得强大的技术职称。云在提供计算资源的过程中主要以虚拟机( virtual machines, VM)的形式，在工作流中实验任务和云提供的计算资源之间所反应的关系就是工作流在调度过程中的关系和问题。云在进行工作流的调度工作中主要含有2 个层面，第一个层面所指的是实验任务和虚拟机之间的映射，第二个层面是指在单独一个虚拟机上的任务执行顺序。本文选择Amazon EC2 为云环境，并在此基础之上提出了有效的策略来解决对多个目标工作流实施调度过程中存在的问题。

1 Amazon EC2云环境

Amazon EC2 云环境的全称为Amazon 弹性计算云EC2，实际上属于IaaS ( infrastructure as a service，基础设施即服务)云服务，能够针对用户开放Amazon 的相关计算设施。为了能够保证云计算对各种资源实现有效的利用，并且能够在所给定的相关约束性条件之下仍然及时完成计算任务，就必须要对调度进行优化。调度会影响到云计算的实际运行效率，也就是说调度的优化效果决定了云计算的效率。调度的目标在于最大限度的提高计算资源利用效率、减少在处理任务过程中所需要使用的时间，在保证计算质量的基础上也能够具有较高的工作效率。如图1 所示，即为云计算环境的动态调度示意图。Amazon EC2 云环境可以一共展示3 种不同类型的实例，第一种实例属于预留型，即可以允许一个用户对多个不同主机中的资源进行较长时间的预定；第二种实例属于按需型，所指的是用户可以按照自己请求的资源类型和时间按照每小时对资源付费；第三种实例属于Spot 实例，如果用户拥有没有使用的Amazon 的资源，可以对该资源展开投标，并且用户还能够对某一资源进行指定性的出价格。Spot 价格是根据资源的实际需求量进行制定的，如果所出的价格要比这一价格高，那么用户就能够获得实例，如果所处的价格小于这一价格，那么由Amazon EC2 云环境将Spot 实例，进行回收。

2 模型描述

2.1 DAG任务以及任务模型

图1：云计算环境的动态调度示意图

图2：DAG 图

DAG（directed a cycling graph，有向无环图）是一个没有环、有方向的图，可以对某一个工作流程的开展过程进行仔细的描述，是应用范围较为广泛的工具之一[1]。如图2 所示，即为DAG 图。DAG 模型能够将并行程序进行精准的刻画。虽然无法利用DAG 图将某一个实际程序的循环最为直观的表示出来，但是能够把处于循环之中不同数据流的并行计算进行分解，将其分解成为其他的任务，这种任务的容量会变得更小。之后会对小任务进行模型刻画，则能够通过DAG 图进行展示。在一般情况下，通常会选择DAG图来描述需要进行处理的各个任务，在描述完毕之后能够更加直观的观察到不同任务之间存在的顺序关系以及先后关系，同时还可以展现出在各个任务之间具体的、所传递的信息量。DAG 图可以让我们更加快速的寻找到一条最为关键的路径或者多条具有关键性的路径，在对这些关键性的路径实施判断和评估的时候能够得到最快的运行速度，即所需要的最短的运行时间。本次研究过程中即使用DAG 图对工作流进行定义，被定义为W=（A，D），A 所代表的n 多个任务的总集，即任务集，D 所代表的是不同任务之间的控制流以及数据流之间存在的关系。

2.2 资源模型

此时对云平台的构成进行假设，设定其是通过m 个为异构类型的资源集共同组合而形成的，将其设定为R，之后Amazon EC2云环境进行云资源的提供，例如包括m1．large、m1．xlarge、c1．medium 及c1．xlarge 等。对于给定的资源进行分析和类型确定，在确定类型之后选择CFLOP 对其展开测量，分析在每一秒内可以执行的浮点运算情况。在本次研究过程中，设定工作流任务在Amazon EC2 云环境中能够做到并行执行，并按照这种形式持续运行，每一个小时进行进行一次收费。最后可以发现用户所需要付出的费用会受到多种因素的影响，不单单只是资源如何使用，例如数据存储和虚拟机各个实例之间数据的传输情况也会影响到用户最后所需要支付的费用。DAG 图如图2 所示。

2.3 对问题进行定义

本文所研究的问题简单来讲所指得是把原有的工作流任务通过有效的、科学的调度方式传输到Amazon EC2 云环境进行计算和运行，这样可以在减少用户支付费用的情况下能够减少执行时所需要使用的时间。因此之后需要对执行时间makespan 以及经济代价这两个优化的具体目标进行定义。

3 展开多目标优化

多目标优化其实上是在数学规划过程中所存在的重要分支，对在一个以上的目标函数进行研究，并在函数的给定区域之上对其进行最优化。简单来讲，可以将多目标优化认为是寻找到能够让矢量函数变成最小化形态的所有解，用函数可以表示为f(x) =[f1(x), f2(x) , …, fo(x)]，其中o 所代表的是具体的目标函数数量。本次研究中的目标函数数量为2，第一个目标函数为执行时间makespan，第二个目标函数为经济代价。上文所提到的在解决工作流调度这一问题时所得出的最优解中每一个都另外含有两个不同的矢量。其一包括多个不确定数量的元素矢量，其数量确定需要取决于工作流的实际腾武数量。其二为大小程度为n 的排列情况，随代表的是不同任务在执行过程中所需要严格遵循的顺序。其实，要求同时寻找到一个可以让执行时间makespan 最短，同时也让所需要付出经济代价最少的解是很难的，或者说在工作流调度的问题中是无法完成的。为了能够真正的解决这一问题，本次研究应用了Pareto 最优这一概念，来对两个目标函数的最优解进行评估和判断。设定两个解分别为y 和z，如果前者在两项目标函数上都要比后者小，那么可以将其称之为解 y 占优解z。如果前者的执行时间makespan 最短，后者需要付出经济代价最少，两个解分别占据一个优势，那么前者和后者均被称之为非占优解。

4 设计多目标工作流调度算法

本次研究过程中选择两种算法进行优化，分别为HEFT 算法以及MOHEFT 算法，通过对两种算法优化之后可以在Amazon EC2 云环境中展开应用，这种方式打破了以往传统情况下的异构计算环境特点。在之前的系统中可以明确的了解到资源的实际数量以及资源的类型分布情况，然而在Amazon EC2 云环境中却只能拥有有限资源总量。但是Amazon EC2 云环境的优势在于可以按照用户的需向用户动态化的提供资源，云计算的计算能力以及云环境中的资源可用性都是处于动态的变化过程的。为了能够保证本次研究中优化后的算法可以在Amazon EC2 云环境中进行合理的使用，选择将资源的实际输入量设定为m=N×I。其中I 所代表的是云资源提供角色所供给的实例数量以及实例的各种类型，经过这种设定之后，能够保证当资源处于总量最大的时候，任何组合都具有一定的可能性。共选择两种算法，第一种属于CHEFT 算法，第二种属于CMOHEFT 算法。

5 实验配置

本次研究所选择的仿真平台为WorkFlowSim。首先，先给定出能够对算法的实际性能进行评估的重要指标，之后分析了工作流的实际类型以及云环境中的具体配置。另外，除了上述提到的两种算法，同时还利用了应用极其广泛的POSH 算法，将该种算法作为性能对比的对照组。POSH 算法也属于常用的一种针对多个目标函数求出最优解的算法，并且在进行算法运行的过程中也考虑到了如何求除均衡解的这一个问题。

6 实验结果评估

合成三种工作流的类型分别为Type-1 工作流、Type-2 工作流以及Type-3 工作流。Type-1 工作流是对比CMOHEFT 算法与 POSH 算法，其中前者解的质量性能要明显优于POSH 算法，、Type-2 工作流中得出的结果Type-1 工作流相同，且最优性要明显于第一组。Type-3 工作流是对上两个工作流结果的印证，也更加明确了CMOHEFT 算法的最优解，能够在于Amazon EC2 云环境中针对多个目标函数完成最优的调度。

现实工作流包括WIEN2k 工作流以及POV-Ray 工作流，两个最后的执行结果相差的程度较小，均表现了CMOHEFT 算法的优越性。WIEN2k 工作流中两种算法之间的对比差距增加，这是由于现实工作流在进行求解的过程中复杂程度会有所增加。POSH 的应用性能仍然低于 CMOHEFT 算法。资源量的增加会导致前者的调度时间缩短，并且代价也会上调[2]。

7 结束语

综上所述，本文基于Amazon EC2 云环境中提出了面向DAG任务的多目标调动算法，该种算法的名称为CMOHEFT 算法。此次算法设计的目标在于可以保障工作流任务的执行跨度能够和工作流任务的执行所产生的经济代价处于同步的状态，并利用了启发式的手段使得多个目标之间形成了均衡的状态，成为了最优解的结合。同时利用了Pareto 边界的手段以及hypervo- lume 值的手段共同对均衡解展开了分析，判断是否均衡解具有一定的有效性。利用人工的方式一共合成了三种工作流，以及两种现实工作流的相关测试。最后对整体过程和最终结果进行分析，可以明显发现为CMOHEFT算法的应用效果最好，优于CHEFT 算法和POSH 算法，在多数的工作流任务中都可以减少执行跨度以及执行所产生的经济代价，可以进行应用。