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