1 摘要
作者提出一种在矢量装箱问题下的，基于深度强化学习的，资源调度算法（原文称作业调度），该算法可自动获得合适的计算方法，该方法将最小化完成时间（最大化吞吐量），本文从trace-driven的仿真演示了DeepJS的收敛和泛化性以及DeepJS学习的本质，同时实验表明DeepJS优于启发式的调度算法
2 Introduction
- 什么是好的调度策略？ ①减少碎片 ②增加吞吐量
- 资源管理依赖于对①工作负载和②集群状态的理解
- 资源调度应用的启发式算法 Fair scheduling（公平调度） First Fit Simple Packing Strategies（简单打包策略）等
- 为什么强化学习可以处理资源调度问题？ 实际调度过程中，集群的工作负载或调度的目标会发生变化，启发式算法无法应对环境的变化，而强化学习可以直接从经验中学习策略 自适应动态变化的环境，因此适合处理更实际的资源调度问题
- 需要考虑物理机数量的变化问题，如果将物理机作为神经网络的输入，则由于神经网络输入层的固定需要物理机数量是不变的，而现实中物理机会由于软件故障而脱机
3 Motivation
考虑到资源的多维度，资源调度问题类似矢量装箱问题，这是一个APX-Hard问题。 由于计算复杂度高，解决装箱问题通常需要使用启发式算法，例如First Fit和Best Fit，这些算法虽然很快，但通常没有最佳解决方案。
而通过强化学习，我们只需要设计一个合适奖励函数即可。强化学习模型可以针对特定的工作负载自学习适应度计算方法
4 算法设计
云计算资源类型通常包括CPU、内存、硬盘和带宽等，这里令用户的第 i个需求向量为 ri=(ri1,ri2,...,rid)T 例如对于三维装箱问题为 ri=(riCPU,ri内存,ri带宽)T 同理，对于集群中第 j个物理机的资源向量为aj=(aj1,aj2,...,ajd)T 在将某个需求分配到物理机时需保证物理机有足够的资源ajk≥rik
4.1 状态空间
维护一个可变长的<任务, 物理机>二元组列表近似集群状态，在每次调度前，需先获取当前最新的集群状态，再进行调度，集群状态在调度发生后或某个任务结束后产生变化。
例如，有6个任务（T1,T2,T3,T4,T5,T6），3个物理机（M1,M2,M3），则某时刻可能的集群状态为
序号 | 二元组 |
|---|---|
1 | <T1, M2> |
2 | <T2, M2> |
3 | <T4, M2> |
4 | <T3, M1> |
5 | <T5, M3> |
6 | <T6, M3> |
以上二元组列表长度为6，当某个物理机中的任务结束，则长度会自动减少
4.2 动作空间
假设目前，有N个待处理任务和M个集群中的物理机，则当前批处理调度的动作空间大小为N×M个，如果不是批处理而是像队列一样，来一个任务处理一个，那动作空间就为M个，动作即为第 i个任务分配最合适的第 j个物理机
4.3 Reward
为了最小化任务完成时间，可以在每次调度后给出-1作为奖励，直到完成所有工作为止。智能体目标是最大化累积奖赏，从而实现最小化总完成时间目标
4.4 智能体设计
既然集群状态列表是可变长的，且神经网络的输入层个数是固定的，本文索性没有将整个集群状态列表作为输入。而是拆分成一个一个<任务, 物理机>二元组，作为输入，因为每个二元组是等长的 ，如下图所示
那么全连接神经网络输出的就是某个任务和某个机器的相关性，也就是适应性（fitness）
训练算法时，每时刻有批量任务到达，需要调度，未来训练出一个泛化调度策略，文中生成了一系列到达序列并在每个序列上迭代数次从而训练模型。其中，假设L表示调度的总次数，则有以下一条tarjectory[s1,a1,r1,...,sL,aL,rL] 具体算法如下
文中对于长度不同的tarjectory的累计奖励，在后期取0处理
具体实验中，文中取神经网络输入层个数为6，具体表示为<物理机CPU,物理机内存,任务所需CPU,任务所需内存,任务持续时间,任务实例个数> 具体神经网络设置如下表所示
5 收敛性和泛化性
我们将这5216个作业划分为多个块，每个块在时间轴上具有10个连续的作业，如图3所示。DeepJS将在每个块上从左到右进行训练，并且每个块仅生成120条轨迹。 如算法2所述，这120条轨迹来自10次迭代，每迭代12条轨迹。在训练每个块之前，将记录DeepJS给出的对该块的调度解决方案的有效期。 这样可以确保每个记录的制造期都在DeepJS从未见过的工作块上。 我们在前100个工作块上以这种滑动方式对DeepJS进行了培训。 值得注意的是，每个作业块包含不同数量的任务，并且每个任务的任务实例数也不一致。 即，工作量随时间变化。
我们将构建时间差定义为其他算法的构建时间减去DeepJS的构建时间，这对应于构建时间的减少。 图4显示了不同算法之间的有效期差异。随着DeepJS沿时间轴向右滑动，它看到的作业块数量在增加，并且训练迭代次数也得以累积。 DeepJS提供的调度解决方案正逐渐优于其他算法。 在图4中的虚线之后，除了虚线圆圈中的作业块之外，DeepJS在其他作业块上的解决方案优于其他算法。 证明了DeepJS的收敛性和推广性。 请注意所有调度算法在其上具有相等生成时间的作业块，即生成时间是某个常数。 这是因为有效期大致取决于该作业块中最后几个作业的到达时间。 因此，makepan没有优化的余地。
6 学习的本质
设计DeepJS时，主要考虑因素是使DeepJS通过强化学习获得适应度计算方法。 正是这种考虑使DeepJS的决策过程更加透明和可解释。 如果DeepJS的设计有效，则很明显，在不同条件下进行训练时，通过不同DeepJS代理在同一拟合机器任务对上计算出的适应度值应该是相关的。 也就是说，DeepJS代理认为机器和任务是很好的匹配，因此另一个DeepJS代理也应该这么认为。 因此，使用滑动方式训练了具有不同机器数量的两个集群中的两个DeepJS代理。 DeepJS代理A所在的群集具有5台64核CPU和1个单元内存的计算机，DeepJS代理B所在的群集具有10个具有64核CPU和1个内存单元的计算机。 两名特工分别接受培训。 训练完成后，我们在DeepJS代理A任意生成的轨迹中选择一些适合的机器任务对，然后每个代理为每个适合的机器任务对计算适合度。 两种代理计算的适应度之间的相关性如图5（a）所示。 相关系数为0.74，
