基于深度强化学习改进的任务调度算法

叶芳泽，沈 炜

(浙江理工大学信息学院，浙江 杭州 310018)

0 引言

近年来，云计算和大数据中心迅猛发展，全球数据量正呈爆炸式增长，数据成为当今社会增长最快的资源之一[1]。面对增长迅速又十分复杂的数据资源，传统单台高性能服务器的处理能力已经不能满足大部分网络服务和数据密集型应用的需求，取而代之的是商业服务器集群[2]。

目前主流的分布式集群计算框架通常使用简单通用的启发式调度算法。但是这类算法通常忽略了系统中作业之间的负载特性，放弃了潜在的性能优化[3]。如果想在分布式集群上使用启发式调度算法去实现高效地调度，通常需要针对特定的应用场景设计一个简化的调度模型，并在实验中精心调整并测试出较好的性能。一旦应用场景发生改变，算法就必须重新设计与测试。

近年来机器学习被成功应用于一些非常具有挑战性的决策控制领域其中就包括调度算法[4]，而机器学习中的深度强化学习既能利用深度学习捕获环境的特征，也能利用强化学习适应复制多变的调度场景[5]，越来越多的文献和实验也表明深度强化学习在调度领域有着巨大的潜力。

随着系统调度任务不断增多，调度过程也变得复杂，传统强化学习算法中的状态空间与动作空间呈指数式增长，在训练过程中通常会出现训练时间长，学习效率低，结果不易收敛等问题。针对上诉问题，本文提出一种基于动作分支架构[6]改进的深度强化学习调度算法：利用分支策略网络分解动作空间，并用全局的评论家网络评估联合动作的优劣。实验表明改进的算法在仿真的Spark 调度系统中，有着更好的调度性能。

1 深度强化学习

1.1 深度强化学习简介

深度强化学习的基础是强化学习，其本质是通过智能体与环境的不断交互，并在观察其行为的结果后根据环境的变化得到相应的奖励，以此调整自身的动作策略[7]。利用这种方式，可以学习如何改变自己的行为，以得到更大的奖励，其数学模型可由马尔可夫决策过程进行表示，具体形式可以用五元组表示为。其中，S表示智能体的状态空间；A表示智能体的可选动作空间；P(s＇|s,a)表示当前状态st下执行动作at后，转移到下一状态st+1的状态转移概率密度函数；r(st,at,st+1)表示当前状态st执行动作at后转移到下一状态st+1的瞬时奖赏；γ(0 ＜γ＜1)，表示未来奖赏折扣因子，决策过程如图1 所示。而深度强化学习是在强化学习的基础上引入了深度学习中的神经网络，利用其强大的感知能力为复杂系统的决策问题提供强有力的技术支持。

图1 强化学习示意图

1.2 A3C算法

A3C 是一种基于策略的深度强化学习算法，结合了policy gradient 和动态规划的优势，当系统给定一个初始的环境状态s1，算法根据策略θ 输出动作a1的概率为pθ(a1|s1)，通过执行动作a1环境状态变为s2，并得到奖励r1，此时状态转移概率为p(s2|s1,a1)。重复上诉步骤直到任务结束，将一次调度过程记为τ=s1,a1,s2,a2,s3,a3…sT,aT。可以求出该调度过程发生的概率为：pθ(τ)=并得到累计奖励：，将两式相乘得到更新策略的目标公式：。最后根据策略梯度公式(1)最大化我们得到的奖励：

在训练过程中A3C 算法引入异步方法，利用CPU多线程机制同时执行多个智能体。在学习模型训练的任意时刻，并行的智能体会根据不同的学习策略与环境状态进行交互，有效去除了样本间的关联性。

2 基于动作分支架构改进的深度强化学习调度算法

2.1 基于Spark的集群任务调度模型

本文通过模拟ApacheSpark 的调度过程来验证算法的有效性[8]。Spark 为每个输入系统中的作业(job)构建了一个有向无环图(DAG)，如图2 所示。DAG 中的每个节点(node)代表该作业的一个执行阶段(stage)，是一个或多个父节点的输出，当所有的父节点完成时，该节点才会被激活，并参与下次的调度计划；每个节点内有数个可并行计算的任务(task)，任务是Spark执行计算的最小单元，一个任务代表一个本地计算，不可拆分，且只能在一个执行器(executor)上执行计算过程，通常一个阶段的任务比执行器多，因此任务分几个批次运行；调度程序(Scheduler)负责维护任务队列，每次执行器空闲时，它都会从中分配任务。执行器是由Spark 根据用户请求指派的，默认情况下，他们会一直运行直到系统中没有作业。

图2 spark系统作业示意图

Spark 任务调度模块主要包含两大部分：DAGScheduler 和TaskScheduler。其中DAGScheduler 主要负责分析用户提交的应用，并根据计算任务的依赖关系建立DAG，然后将DAG 划分为不同的stage，并以TaskSet 的形式把Stage 提交给TaskScheduler。TaskScheduler负责TaskSet中task的管理调度工作，这些task的执行逻辑完全相同，只是作用于不同的数据。调度过程如图3所示。

图3 调度示意图[3]

2.2 算法设计

2.2.1 基于图嵌入的状态空间预处理

图嵌入算法可以在保留DAG 节点信息的同时将图的结构信息一并映射到低维稠密的特征向量中。首先提取DAG 中每个节点的特征信息并将其表示成节点特征矩阵X，然后与邻接矩阵A作为图神经网络的输入，模型架构如图4所示。

图4 多层GCN图嵌入模型[9]

在嵌入算法中使用多层GCN 层间传播[10]，传播公式如下：

2.2.2 基于动作分支的深度强化学习调度算法

基于动作分支架构的思想，本文将传统的单策略网络分解为两个动作分支网络：①执行阶段策略网络，确定待调度的执行阶段；②执行器策略网络，确定上诉阶段应该分配的执行器数量。最后使用一个共享的评论家网络调整调度策略，整体架构如图5所示。为了确保执行器动作网络的输出有效性，本文规定：执行器动作网络最少输出一个执行器，最多输出空闲执行器的数量；当该执行阶段内的剩余任务数量少于分配的执行器数量时，多余的执行器将继续激活系统调度程序，直到系统中没有可剩余可运行的任务。

图5 基于动作分支架构的调度算法模型

当系统出现以下几种情况：①一个阶段用完任务(即不再需要更多的执行器)；②一个阶段完成，解锁它的一个或多个子阶段的任务；③一个新的作业到达系统。系统便会激活调度程序开始新的调度过程，调度程序通过将上文计算得到的图嵌入特征向量分别输入执行阶段策略网络、执行器策略网络和评论家网络，并输出待调度的节点、每个节点应该分配的执行器数量和期望奖励值。每完成一次执行器分配，系统会根据任务的到达时间、完成时间等数据计算此次调度得到的奖励。每当完成一轮完整的调度，系统根据公式⑵更新策略网络。

损失函数选择是非常关键的，它是深度强化学习的核心部分之一，网络模型在训练过程中使用TDerror 作为损失函数,可以有效地找到最佳调度策略,Critic损失函数如下：

Actor损失函数如公式⑹所示：

3 实验分析

3.1 实验环境

本次实验采取ubuntu 下的TensorFlow 深度学习框架，使用Pycharm 软件进行程序编写，实验平台的配置如下：CPU 为Intel(R) Pentium(R) CPU G3260 @3.30 GHz，GPU为NVIDIA GTX 6G，1 TB硬盘。

3.2 训练

为了评估算法的有效性，我们使用文献[3]提供的TPC-H 查询数据，从六个不同数据量(2,5,10,20,50,100SF)的全部22 个TPC-H 查询中随机抽样，输入Spark 调度系统。系统初始状态为一个查询作业，15个任务执行器。训练开始时每间隔一段随机时间从数据集中获取20 个查询作业组成一个批次输入系统等待调度，共计100个批次，为了模拟系统在高负载下的调度性能，要求这100 个作业批次在规定时间内按泊松分布全部推送至系统，共计训练5000轮。

3.3 评估方法

本文选取了以下四个经典的调度算法与第二章提出的算法（下文简称B-A3C）进行对比。

⑴FIFO：Spark 默认的调度算法，它以作业到达的先后顺序进行分配执行器，并根据用户请求为每个作业授予相同数量的执行器。

⑵SJF-CP：根据作业的总工作量，优先调度短作业，并在每个作业中优先选择关键路径上的节点。

⑶Tetris*：基于Teris 算法，平衡短期作业偏好和资源利用率得到一个综合评分，以此分配执行器。

⑷A3C：仅使用一个策略网络，在相同的训练时间内比较算法的优劣。

3.4 结果与分析

表1 展示了在不同的执行器数量下，各个算法的平均作业完成时间。从表1 中的数据得知，随着执行器数量的增加，平均作业完成时间逐渐减少。其中当执行器数量较少时，两种深度强化学习算法的平均作业完成时间明显低于其他算法。当执行器数量达到29 及以上时Tetris*算法的性能优于A3C 算法。由此可以推测在只训练5000轮的情况下，A3C 算法不能合理分配空闲的执行器，而B-A3C算法得益于分支动作架构的存在，可以在较短的时间内习得更为高效的调度策略。

表1 平均任务完成时间(单位：秒)

4 结论

针对强化学习传统的单策略网络在复杂的调度系统中无法快速、高效地探索动作空间的问题，本文提出了一种基于动作分支架构的强化学习算法模型，通过将一个完整的调度动作分解为两个分支动作，有效地减小了各个分支的动作空间，提高了探索效率。最后通过实验证明在仿真的Spark 调度模型中，相较于传统的调度算法、启发式算法和单策略网络的强化学习，该算法能有效的提升系统的调度性能。