基于遗传算法的GPU集群多作业调度方法

摘要

本发明公开基于遗传算法的GPU集群多作业调度方法。通过遗传算法降低寻找最优解的时间复杂度，基于最小化多作业完成时间的资源分配方式为多作业分配GPU资源，复用作业调度过程中可能出现的空闲资源，最终得到一个完成时间最小，资源利用率较高的多作业调度方案。与现有技术相比，本发明有效解决了GPU集群上的多作业调度完成时间久、资源利用率低等问题，深度学习有关的工作者在调度方案的指导下，能够快速完成对模型不同参数架构的质量验证，得到反馈结果，进而对模型进行改良，以便快速投入到下一次的实验或生产当中。

说明书

技术领域

本发明涉及一种GPU集群上的深度学习作业调度方法，特别是一种基于遗传算法并结合最小化时间的资源分配、复用的GPU集群多作业调度方法。

背景技术

深度学习已经广泛应用于人工智能的众多领域，如图像分类、动作识别、语音识别、自然语言处理等。深度学习的成功依赖于从训练数据集中学习表达复杂特征的能力。另外，为了提高学习精度和模型即深度神经网络的性能，增加训练数据集大小和扩大模型规模已被证明是非常有效的。然而，大规模的深度神经网络模型也显著延长了训练时间。使用单个GPU训练复杂的大规模深度神经网络模型将花费大量的时间，比如数天、数周甚至是数月。

因此，大多数科研实力领先的企业、研究所和大学更偏向于在拥有数十或数百个GPU的集群上采用分布式训练的方式来加快模型训练。目前，已有许多支持在GPU集群上进行分布式训练的系统和框架，在调度深度学习作业时具有显著的性能表现。例如：TensorFlow和PyTorch是两个现有的最先进的机器学习框架，它们通过数据并行和模型并行的方式支持分布式深度神经网络模型的训练。

现有关于分布式深度神经网络模型训练的研究大多数集中在减少单个模型的完成时间上。但研究者和学者往往需要在GPU集群当中运行多个训练作业(即同时训练多个模型)。例如，为了搜索模型达到满意精度的最优参数，研究者和学者通常尝试多种参数配置，从而形成批量的训练作业，并采用反馈驱动的方式来排除低精度的参数配置。此外，当设计一个新的人工智能算法时，应该进行结果和性能验证，以便与一些最新的研究进行比较。以动作识别的研究过程为例，为了探索提出的权重共享约束对时空特征编码的可行性，这一思想应该在现有的经典模型(如C3D、ARTNet、STC、I3D等)和多个数据集(如ResNet、SoundNet、TSN-Flow、COSt等)上进行测试和验证。这些都是研究者和学者所面临的典型场景。

然而，仅有少量的研究工作考虑了多作业的调度，且集中于减少集群能耗以及提高资源利用率上，这也直接影响了多作业共同训练的完成时间。

发明内容

本发明的一个目的是针对目前技术的不足，提出了一种基于遗传算法并结合最小化时间的资源分配、复用的GPU集群多作业调度方法，它将给出多作业的一套调度方案，该方案可有效减少多作业的完成时间，并提高集群资源利用率。

本发明通过遗传算法降低寻找最优解的时间复杂度，基于多作业完成时间最小的资源分配方式为多作业分配GPU资源，复用作业调度过程中可能出现的空闲资源，最终得到一个完成时间最小，资源利用率较高的多作业调度方案。

本发明方法包括以下步骤：

步骤(1)资源-时间建模，收集深度学习作业在不同GPU数量下的完成时间。

步骤(2)根据遗传算法的思想建立个体和种群，每个个体信息当中将包含多作业的一种执行顺序方案。

步骤(3)为多作业进行资源分配，分配的前提是使得多作业的完成时间最小，得到多作业的初始资源分配方案。

步骤(4)改进多作业初始资源分配方案，复用调度过程中可能出现的空闲资源，进一步减小完成时间并提高资源利用率。

步骤(5)计算个体适应度，进行个体选择，筛选出最终个体，其所包含的调度方案即是多作业的最终调度方案。

本发明的另一个目的是一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行上述的方法。

本发明的又一个目的是一种计算设备，包括存储器和处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现上述的方法。

本发明的有益效果：

1)引入遗传算法降低搜索最优解的时间复杂度。

2)通过两类最小化多作业完成时间的资源分配方案为多作业进行资源分配。

3)复用空闲资源，进一步减少多作业完成时间并提高集群资源利用率。

与现有技术相比，本发明有效解决了GPU集群上的多作业调度完成时间久、资源利用率低等问题，深度学习有关的工作者在调度方案的指导下，能够快速完成对模型不同参数架构的质量验证，得到反馈结果，进而对模型进行改良，以便快速投入到下一次的实验或生产当中。

相关概念定义及符号说明

J

M：表示种群规模；

m：表示GPU资源总数；

附图说明

图1：本发明的基本流程示意图。

图2：个体编码单点交叉过程示意图。

图3：个体编码变异过程示意图。

图4：基于最小化作业最大时间思想得到的多作业资源分配示意图。

图5：基于最短作业序列时间思想得到的多作业资源分配示意图。

图6：经由资源复用改进前后的调度方案示意图，其中(a)为未资源复用改进,(b)为经过资源复用改进。

具体实施方式

下面结合附图对本发明做进一步的分析。

如图1，本发明基于遗传算法的GPU集群多作业调度方法包括以下步骤：

步骤(1)、资源-时间建模：

(1.1)为当前多作业中的每个深度学习作业从1个GPU开始到所有GPU下分别运行若干次迭代，根据公式(1)计算得到不同GPU数目下作业运行一次迭代所需要的时间

其中

(1.2)根据公式(2)得到一个作业在特定数目的GPU下训练完成所需的总时间；

其中

步骤(2)、根据遗传算法的思想为多作业建立个体和种群，并为每个个体应当包含的信息进行描述，具体如下：

(2.1)设计个体编码规则，用于表示个体之间的不同，每个个体的编码对应一个多作业执行顺序序列：

假设多作业所包含的作业集合表示为J＝[J

(2.2)建立多作业J的初始种群，此时种群当中的每个个体仅包含个体编码：

设定种群规模为M，M越大越可能找到最优解，相应的算法运行时间也就越长。生成M个个体组成初始种群，其中每个个体I

由于随机过程使得作业执行顺序不一定具有连续性，此处规定仍按照顺序从小到大的方式确定每个作业的执行先后顺序；

(2.3)个体编码交叉使得种群中的个体可以探索未知的解空间，采用经典的单点交叉对不同个体之间的编码进行交叉操作，见图2：

首先需进行配对操作，种群中的每个个体随机选择除自身以外的个体进行配对，然后为配对个体之间进行编码交叉操作。具体操作是获取配对个体I

(2.4)对编码交叉步骤后的个体编码进行变异操作，见图3。变异可以提高遗传算法的适应度，防止遗传算法过早收敛：

首先从[1,n]中随机得到编码变异位置，再随机从[1,n]中得到与该变异位置执行顺序不同的执行顺序

(2.5)经由步骤(2.3)、(2.4)，初始种群中的个体发生演化，我们将演化后的种群称为演化种群，并保留初始种群；

步骤(3)、在步骤(2)的基础上为多作业进行初始资源分配，即在多个个体拥有多作业不同作业执行顺序的基础上，增加作业资源分配方案作为个体信息之一，形成多作业的初始调度方案，其过程如下：

(3.1)将原始种群和演化种群中所有个体编码各自按照作业执行顺序进行分组，即将每个个体中相同执行顺序的作业分为一组，每个个体得到若干作业分组

由于资源分配的目标是多作业的最短完成时间，经过作业分组可将其拆解为子问题，即最小化每个作业分组的最大完成时间

多作业资源分配的目标方程定义如下所示：

(3.2)判断分组G

(3.3)为分组内的作业进行资源分配，并获取各分组完成时间：

(3.3.1)逐步为分组内完成时间最大的作业分配资源以便最小化每个分组的

①为每个作业J

②将作业按照

③分配一个剩余GPU给到第一个作业，作业相应的

④重复步骤②③直至没有剩余GPU可分配；

(3.3.2)假设同一个分组的作业以并行的方式运行，根据公式(3)得到分组最大完成时间

其中

该资源分配方案演示可参考图4。

(3.4)将分组内作业划分为多个作业序列后进行资源分配，并获取各分组完成时间：

由于作业数量超过GPU总数，在此处将分组内的多个作业分为m个作业序列，每个序列中的作业都将在1个GPU上训练，此时分组的最大完成时间将取决于作业时间之和最大的作业序列，因此资源分配的方式是安排每个作业到作业时间之和最小的作业序列以便最小化每个分组的

①为m个GPU资源映射m个作业序列job_list

②定义作业序列的时间为

其中

其中

③将分组G

④重复步骤③，直至分组G

该资源分配方案演示可参考图5。

步骤(4)、在步骤(3)的基础上为多作业的调度方案根据资源复用的理念对调度方案进行改进，进一步减少多作业调度方案的完成时间，其过程如下：

(4.1)遍历每个作业分组中的作业或作业序列，计算作业时间

(4.2)将当前分组中的资源空闲时间T

判断后续分组作业是否被组织成作业序列，若否则将后续分组中的作业按照时间

①获取资源空闲时间T

其中

②由于预训练消耗了后续作业的部分迭代次数，因此需要重新计算后续作业在原资源分配方案下的训练完成时间，由公式(7)(8)计算获得。

其中

经过资源复用改进过后的调度方案示意图可参考图6；

步骤(5)、计算个体适应度，执行种群选择流程，确定最优个体即最终多作业调度方案，具体过程如下：

(5.1)将步骤(2)当中的原始种群和演化种群经由步骤(3)、(4)后，每个个体都包含了多作业的一种调度方案，依据公式(9)计算个体所包含的调度方案总时间，它等于作业分组中的分组时间

(5.2)计算个体的适应度

(5.3)按照

(5.4)从当前原始种群中选择个体适应度最大的个体，其所包含的调度方案即是多作业最终的调度方案。