基于改进高斯过程回归的云工作流调度算法

钟积海 ，崔得龙 ，2

（1.广东石油化工学院计算机与电子信息学院，广东茂名525000；2.广东省云机器人（石油化工）工程技术研究中心广东茂名525000）

云工作流（科学工作流、多层Web服务工作流、MapReduce工作流和Dryad工作流等）是工作流在云计算环境下的一种新应用模式[1]，其在共享异构分布式资源（公有云、私有云或混合云等）下的调度问题近年来引起了科研工作者们的广泛关注，并已在执行时间最小化、公平性最大化、吞吐量最大化以及资源优化分配等方面取得了重要进展。

但目前云工作流调度研究通常建模为多约束条件下的单/多目标优化问题，该问题或侧重于固定虚拟化资源下的工作流任务分配[2]，或侧重于工作流负载变化下的弹性资源供给，或侧重于如何将现有的工作流管理系统融入云平台之中[3，4]，同时当云工作流任务规模变大时，该优化问题变得异常复杂，往往无法及时得到最优任务分配策略，也易陷入局部最优。

1 相关工作

云工作流，尤其是科学工作流具有业务流程复杂、计算任务耗时和数据量大等特征，工作流任务之间的依赖约束关通常采用有向无环图（DAG）进行描述。

Shojafar等人[5]提出一种基于模糊理论和遗传算法的混合优化任务调度算法，在完成时间和租用费用的约束下优化虚拟机间负载均衡。Abrishami等人[6]在其网格工作流调度的研究基础上，分别设计了基于IaaS云的单向IC-PCP和带截止时间约束的双向IC-PCP任务分配算法，并指出两种算法的时间复杂度都仅为多项式时间。清华大学张范等人[7]设计了一种基于扩展序优化多目标多任务调度算法，大幅度降低了时间开销，并证明了该算法具有次优性。大连理工大学郭禾等人[8]提出带通信开销的工作流费用优化模型，并在模型的基础上提出了分层调度算法。Szabo等人[9]针对数据密集型科学工作流应用，考虑了网络传输和执行时间的约束，设计了一种基于进化方法的任务动态分配算法。Chen等人[10]针对多工作流任务公平分配问题，设计了一种优先级约束下的动态任务重排和调度算法。东南大学李小平团队在动态任务调度方面进行了大量的研究，近期发表了一种带准备时间和截止期约束的云服务工作流费用优化算法[11]。该算法建立了相应的整数规划数学模型，引入个体向全局最优解学习的策略提高算法的全局搜索和局部优化能力。安徽大学李学俊等人[12]针对传统数据布局方法的不足并结合混合云中数据布局的特点，设计一种基于数据依赖破坏度的矩阵划分模型，提出一种面向数据中心的工作流任务布局方法，将依赖度高的工作流任务尽量放在同一数据中心，从而减少数据集跨数据中心的传输时间。针对不同时间提交的不同QoS需求的多工作流调度问题，设计了一种基于强化学习和DAG关键路径的混合任务公平调度算法[13]，算法采用状态聚类大幅度降低了状态空间的维度，提高了算法的收敛速度。通过分析工作流任务在云平台的执行过程，设计了一种多目标优化任务调度算法[14]。针对计算密集型和数据密集型混合任务，综合采用多agent并行学习、知识复用和迁移等技术加速最优策略的搜索[15]。Fard等人针对异构云计算环境设计了一种多目标优化算法。算法将全局任务分配问题划分为多个子分配问题，每个子问题分别采用元启发式算法求解[16]。谢国琪等人在多工作流混合调度领域进行了长期深入的研究，近期针对云计算环境中多工作流的可靠调度问题，提出一种考虑虚拟机之间链路通信竞争的动态多DAG调度策略[17]，有效解决了当多个DAG中任务的权值相差较大时的公平调度问题。田国忠等人首先提出了衡量DAG期限紧急水平的“相对严格程度”指标，能够合理处理多个DAG之间调度的紧急水平关系，从而达到DAG吞吐量最大化调度目标[18]。

综述所述，目前大部分工作是网格工作流任务分配策略在计算资源“按需付费”特性上的扩展，忽略了云计算环境最根本的“弹性资源供给”特征，因此缺乏新颖性和通用性，也不符合真实的云计算应用场景。同时，该问题通常建模为多约束条件下的单/多目标优化问题，但当任务规模变大时，该优化问题变得异常复杂，往往无法及时得到最优任务分配策略，也易陷入局部最优。

2 在线自适应高斯过程建模

2.1 高斯过程回归

式（1）和式（2）中，y=[y1,y2,...,yn]T为训练样本输出构成的向量；k(x*)=[C(xi,x*)]n×1为测试输入和训练样本输入间的协方差向量；K=[C(xi,xj)]n×n为训练样本输入间的n×n协方差矩阵；C(xi,xj)为测试输入与其自身的协方差。

径向基函数是最常用的协方差函数，其正定表达式如下：

式（3）所示的协方差函数由2部分的和组成，前一部分表示相邻输入有着高度相关的输出，且对于每一个输入，参数wt允许使用不同的距离测度，参数vij用于控制局部相关性的程度；后一部分表示数据中的噪声，其中vi表示噪声的方差。协方差函数中的超参数通常使用贝叶斯法、最大似然法或交叉验证法等进行迭代优化。当采用最大最大似然法求超参数，GPR的似然函数可表示为：

2.2 在线自适应GPR模型

直接利用式（4）求解GPR的超参数，CN矩阵会随着数据集的不断加入变得异常庞大，因此必须在迭代过程中进行数据的更新替换，以确保数据集的大小和计算的速度。本文利用Adaptive Nature Gradient（ANG）的迭代运算求解超参数的最优值，ANG可表示为：

式（4）对超参数求导，得：

G的迭代估计式[19]如下：

3 云工作流调度算法

云工作流系统是建立在云计算平台上的工作流系统，其功能需求仍满足云计算模式的特点.它的功能组件包括了一般工作流系统组件和与工作流系统相协调云计算平台。此外，云计算平台的管理非常复杂和庞大，如何高效提高服务质量QoS（Quality of Serivice）的管理和任务部署是一个极大的挑战.因此，云工作流系统同样面临同样的问题。为了在云环境中如何高效调度任务及数据。本文提出了一个云工作流系统模型如图1所示。

图1 云工作流系统模型

3.1 云工作流模型组件介绍

云工作流接口：云工作流通过这个接口导入到云工作流系统中，这个组件提供了对科学工作流，电子商务等的接口，以便后续组件根据其工作流的主要特点进行分类处理。

云工作流解析器：这个组件对工作流整体进行解析，生成工作流的任务集，任务之间的约束关系，以及任务之间的数据和传输路径。

云工作流引擎：获取了云工作流解析器生成工作流任务集，任务之间的约束关系，以及任务之间的数据和传输路径。云工作流引擎的主要作用在于根据任务间的约束关系，确保当前任务在父任务成功完成或数据到达当前任务时，当前任务才可以执行。这个组件只提交未处理的任务给云工作流调度器。

云工作流调度器：这个组件是整个系统的核心，主要的任务调度算法是通过这个组件实现，首先云工作流调度器通过加载上一层组件生成的云工作流，生成一个全局队列，其次在作业分配器中根据调度算法对任务进行分配，生成作业的调度的子队列，然后从子队列中按照先来先服务的顺序把任务分配给虚拟机进行处理，最后输出执行结果。

3.2 云工作流调度算法

根据图1云平台模型和经典队列理论，在每个调度时刻系统状态转移满足马尔科夫性，则基于强化学习的云作业调度相关概念可描述如下：

状态空间：用五元组S=(WR,RA,AW,IM,PJ)表示状态空间，其中WR表示待调度任务的工作量；RA表示资源可用时间；AW表示等待队列中的总工作量；IM表示空闲容器资源数；PJ表示队列中各用户提交任务的比例。

动作空间：用三元组J=(TJ,WS,ET)表示动作空间，其中TJ表示任务类型；WS表示用户标识符；ET表示任务执行时间。

奖赏函数:本文采用式（9）作为多工作流公平分配的奖赏函数：

式（4）中，λs∈[0,1]为控制系数；W为工作流任务响应率；F为公平性指标。

任务vi响应率Wvi定义为：

任务vi公平性指标Fvi定义为：

算法伪代码如算法1所示。

算法1改进的云工作流调度算法

4 实验验证与分析

4.1 云工作流仿真器WorkflowSim

WorkflowSim是由南加州大学的Pegasus WMS组开发的一套开源工作流仿真软件，其工作原理是在暨有的CloudSim仿真软件基础上，提供workflow层次的仿真。WorkflowSim可用于验证图算法（Graph algorithm）、分布式研究（distributed computing）、工作流调度算法（scheduling）、资源调度算法（resource provisioning）等问题的研究。

4.2 实验验证

本文实验模拟平台Workflowsim的参数设置如表1所示。

选用基本强化学习和文献[20]进行比较，实验结果如图2和图3所示。

图2所示为基本强化学习和本文设计算法下Q值表收敛情况比较。从图2的实验结果可见，基本强化学习下图2（a）由于部分状态访问次数较少，导致Q值表更新较慢，对比算法1图2（b）采用了高斯过程回归，有效提高了Q值表的收敛速度，但本文算法图2（c）在速度和精度上，都优于基本强化学习和对比算法1。

表1 实验模拟平台的参数

图2 Q值表收敛比较

图3 累计回报比较

图3所示为完成相同工作流任务下的累计回报比较情况，实验结果表明本文算法优于基本强化学习和对比算法1。

5 结束语

文中设计了一种基于改进Q-learning的云资源调度算法，针对原始Q-learning算法存在的不足，结合高斯过程回归加速最优策略的收敛，实验结果证明本文算法的有效性。今后的工作将在高斯过程回归的参数优化，预测更新步长等方面展开。