分布式训练异构任务调度算法研究

杨坚伟，孟 敏，黄家乐，武继刚

(广东工业大学计算机学院，广东 广州510006)

1 引言

近年来，随着深度学习领域研究的快速发展以及移动终端的大规模普及，资源与计算密集型的深度学习应用越来越多地被部署在移动终端设备上，如车联网中的道路识别应用和远程医疗应用等。然而，由于深度学习网络结构日趋复杂且产生了大型数据集，终端设备往往难以承担深度学习应用所需的巨大训练成本。通过将训练任务分配给多个边缘服务器ES(Edge Server)进行协同训练，分布式训练与边缘计算的结合使得这一问题的解决成为可能。目前一般采用参数服务器PS(Parameter Server)架构执行分布式训练过程，由多个边缘服务器作为工作结点(Worker)计算本地数据的梯度，并与PS(在本文中指云服务器)之间进行参数共享，实现对模型损失函数的优化。

然而，作为分布式训练中的工作结点，ES在训练过程中经常需要同时处理大量异构任务。以车联网中道路识别的分布式训练任务为例，车载辅助驾驶设备可能需要ES(如路旁基站等)在执行训练任务的同时提供实时的多媒体语音、视频等服务。在实际应用中，异构任务发布者可能预购了与训练结果相关的服务，同时异构任务在不同的ES上执行所需的工作能耗、通信要求不同。因此，研究如何合理调度异构任务，从而能够在保障异构任务服务质量的同时，尽可能最大化ES集群的分布式训练性能，具有十分重要的现实意义。

2 研究现状

2.1 众包感知模型与任务调度

随着无线传感器的广泛使用，由传感器节点承担大型感知项目的部分子任务成为可能，因此人们提出了众包感知模型这一概念，即具有传感器的计算结点可以向众包任务发布者上传其感知并处理的数据，常见于人群计数、目标检测等相关任务中[1]。在众包感知模型中，如何基于有限的价格预算、算力和设备能耗等资源约束，实现高效的任务分配，一直以来都是人们研究的重点。Zhang等[2]提出了一种新的参与者选择框架，能够在基于节能原则的众包感知模型上选择合适的参与者，实现激励报酬最小化；文献[3,4]通过在线问卷或来自社交网络的真实数据了解用户偏好，推断决策过程，并提出一种用户贡献依赖于其所得到的激励大小的概率模型，在有限的任务预算下将其应用于用户选择过程，实现用户总贡献的期望最大化。

然而现有的此类研究很少从一类特殊的计算任务——分布式训练任务的执行效率角度研究相应的众包感知模型。在该模型中，众包感知任务发布者在满足资源约束的同时将任务分配给不同的ES。但是，与上述模型不同的是，ES集群也在执行分布式训练任务。由于不确定异构任务在其执行时间内的资源消耗，为尽可能满足终端用户的实时任务请求，PS在进行全局模型的更新时，将会把执行异构任务的ES视为离群结点，不再使用其局部训练结果。基于这一前提，在保证异构任务执行效率的条件下，还需实现该集群的分布式训练性能最大化。

2.2 分布式训练与任务调度

由于分布式训练的兴起，将任务调度与分布式训练相结合也成为近年来的研究热点之一。文献[5]研究了分布式训练中任务卸载与资源分配协同优化策略，在满足服务质量的前提下将其形式化定义为混合非线性整型优化问题，最大化系统吞吐量；文献[6]研究了分布式训练中计算任务的分配问题，提出了2种最小化任务完成时间的调度方案；Bao等[7]基于强化学习策略，以最小化同位干扰与最大化训练性能为目标，设计能够高效放置训练任务的机器学习集群调度器。此外，国内学者也从不同角度针对分布式训练中的资源调度过程进行过大量研究[8 - 11]。上述研究对象大都是单一任务类型，但在实际训练过程中，Worker集群可能需要以牺牲训练任务执行效率为代价处理实时的异构任务请求，而上述研究大都没有考虑异构任务调度策略对训练性能的影响。

近年来也出现了不少针对训练性能这一指标进行量化所展开的研究。Chen等[12]在保证分布式训练性能最优的条件下，通过联合优化通信资源分配策略与工作结点选择策略最小化训练时间，并进一步引入人工神经网络估计模型参数，提高收敛速度；此外，Chen等[13]进一步考虑数据包传输的影响，在联合优化资源分配策略与工作结点选择策略的同时，通过找到最优通信功率建立训练性能与包错误之间的关系，最大化训练性能。受文献[12,13]对收敛性能分析方法的影响，本文建立了异构任务调度与分布式训练性能之间的关系，将其创新性地转化为多维多选择背包问题MMKP(Multidimensional Multiple-choice Knapsack Problem)进行求解，在优化异构任务调度策略的同时,最大化分布式训练的性能。

3 系统模型

本文在无线环境下采用文献[12]所使用的分布式训练框架，结点传输时采用的协议是正交频分复用OFDMA(Orthogonal Frequency Division Multiple Access)。图1搭建了一个由ES集群与异构任务发布者所组成的任务调度系统。本文假设云服务器为分布式训练任务中的PS，ES集群为N={1,2,…,n}，并将第i(i∈N)个ES结点表示为Ni。PS在ES集群N中分发训练任务。由于训练任务具有一定时延要求，本文以二值变量ci表示最终分发结果，其中，ci=1表示Ni在延迟约束条件下成功接收到训练任务，反之ci=0。对于Ni，将其本地训练样本数量表示为si，则其训练所得到的权重向量可表示为wi=[wi,1,…,wi,zi,…,wi,si]。

Figure 1 System model图1 系统模型

训练过程中，假设ES集群需要处理另一个到访的异构任务集合Q={Q1,…,Qj,…,Qq}，其中，q为任务数量且q

(1)

因此，本文关于异构任务调度策略aj的分布式训练性能优化目标初步可以写为：

(2)

wi,1=…=wi,zi=…=wi,si,∀i∈N

(3)

3.1 通信模型

对于第i个ES节点Ni，其与PS之间的传输速率如式(4)所示：

(4)

其中，Bi是Ni与PS之间的通信带宽，ω是背景噪声，αi与pi分别为Ni与PS之间的信道增益与通信功率。由于各ES从PS下载的训练模型大小相同，因此通信速率将成为ES能否在一定时间内成功下载模型的主要瓶颈。考虑用oi表示Ni成功接收训练任务的概率，则有：

(5)

oi(vi)=1-exp[-m(vi+ω)]

(6)

其中，oi满足与vi相关的指数分布，m为瀑布阈值[14]。

对于Qj，假设由Ni执行，则其任务发布者与Ni之间的传输速率如式(7)所示：

(7)

(8)

因此，在上述前提下，分配给Ni的最小带宽资源为：

(9)

在实际应用中，分配给执行异构任务的ES的带宽资源之和不能超过当前可用的最大系统带宽。假设当前可用的最大系统带宽为B，则有：

(10)

3.2 能耗模型

对于第j个异构任务Qj，假设ES的有效电容系数为γ，CPU频率为δ，η0为计算能耗惩罚因子，则Qj的计算能耗为：

(11)

假设Qj由Ni执行，ηi为Qj与Ni之间的传输能耗惩罚因子，则最大传输能耗为：

(12)

在实际应用中，执行异构任务的过程需满足其产生的传输与计算能耗之和不超过ES集群所能承担的最大能耗。假设系统可承担的最大能耗开销为Emax，则有：

(13)

4 收敛分析

(14)

(15)

其中，

(16)

设全局模型收敛后的权重为W*，本文使用下列收敛分析中常用的定义与假设[15 - 18]：

(17)

假设2F(W)满足强凸性(μ为正常数)，即：

F(Wt+1)≥F(Wt)+

(18)

假设3F(W)二次连续可微，基于上述假设则可推导出关于F(W)的二阶偏导数被关于‖Wt+1-Wt‖的三次函数上下逼近：

(19)

以上假设均可被一般的机器学习损失函数所满足。

定理1在上述已知条件与假设成立的情况下，有：

ΓtE(F(W0)-F(W*))

(20)

其中，

(21)

证明由式(17)可求得F(Wt+1)的二阶泰勒展开式：

(22)

给定学习率λ=1/L，则有：

(23)

结合式(16)推导其数学期望，则有：

(24)

(25)

因此：

(26)

由式(18)可以推导出：

(27)

(28)

将式(26)代入式(24)，两边同减去F(W*)，递归调用后，则有：

E(F(Wt+1)-F(W*))≤

Γt(F(W0)-F(W*))

(29)

证明完毕。

□

显然，当Γ≥1时模型将无法收敛，因此本文只在Γ<1的情况下讨论训练性能。而当t足够大时，有Γt=0。则不等式(29)右侧的第1项可重写为：

(30)

(31)

(32)

(33)

aj,i∈{0,1},∀i∈N,∀j∈Q

(34)

式(10)和式(13)

(35)

5 异构任务调度算法

定理2式(31)可转化为多维多选择背包问题。

证明多维多选择背包问题MMKP可用式(36)描述：

xi,j∈{0,1},i=1,2,…,K;j=1,2,…,M

(36)

□

由于MMKP问题为非确定性多项式难题，不难得知式(31)也属于非确定性多项式难题。作为一种可以快速求得此类问题次优解的解法，启发式解法通常从较优的初始可行解出发，经过多次迭代调整后得到更优的可行解。为在保证服务质量的同时满足分布式训练性能最大化，本文采用基于贪心策略的禁忌搜索算法对式(31)进行求解。本文所使用的禁忌搜索算法是一种改进的局部邻域搜索算法(又称爬山启发式算法)。在本文中，该算法通过引入一个高效灵活的存储结构——禁忌表，以及设计相应的禁忌准则与藐视准则，能够保证对不同搜索路径的有效探索；此外，贪心策略能够基于最大系统效用值实现对异构任务调度策略初始解的优化[19]。禁忌搜索算法已经成功地应用到许多优化问题，如旅行推销员问题、生产调度问题等。

5.1 基于最大系统效用的贪心策略求初始解

步骤1计算异构任务集合Q在边缘服务器集合N上的预期效用值，得到预期效用矩阵。

步骤2置空异构任务调度状态转移矩阵flag，令当前背包容量为sum(k)=0，k=1,2。

步骤3从没有分配到任何边缘服务器的异构任务中随机选择一个任务Qj，转步骤4；若异构任务全部分配完成，转步骤7。

步骤4在预期效用矩阵中找到其效用值最高且未被分配的边缘服务器Ni。

步骤5计算将Qj分配给Ni后所产生的k个背包权重并将其与对应的当前背包容量sum(k)相加，若sum(k)小于或等于其可容忍的最大容量，则flag(i,j)=flag(i,j)+1。

步骤6若flag(i,j)=2，则更新sum(k)，将Qj分配给Ni，转步骤3；否则，转步骤4。

步骤7算法执行完毕，得到异构任务调度策略的初始解sol0。

5.2 禁忌搜索算法

在利用贪心策略求得异构任务调度策略的初始解的基础上，本文提出了基于禁忌搜索的异构任务调度算法，其基本步骤(续5.1节)如下所示：

步骤8给定禁忌搜索算法相关参数，置空边缘服务器集合N所对应的n×n禁忌矩阵tabu，即允许所有边缘服务器被交换。

步骤9初始化时当前最佳解为solbest=sol0，该解为n×q的任务调度矩阵，矩阵元素值为0或1。

步骤10令当前最佳解所对应的评价值BestL为solbest所对应的系统效用值，并令当前解solnow=solbest。

步骤11在当前解的邻域内使用交换操作产生r个候选解(本文取r=50)，即交换当前解中任意2行作为当前解的一个邻域候选解，计算候选解的系统效用值，并选择前25个满足条件的最佳候选解，按照系统效用值从大到小进行排序。

步骤12判断第1个最佳候选解的系统效用值是否大于BestL，如果是，则更新solbest，同时更新BestL的值为该候选解的系统效用值，并将候选解所对应的2个边缘服务器置入禁忌表，转向步骤13；否则，转向步骤12。

步骤13判断候选解集合中各对象的禁忌属性，从中选择不属于禁忌表的最优解更新当前解solnow，然后将solnow所对应的2个边缘服务器置入禁忌表。

步骤14判断算法是否达到最大迭代次数，若是，算法停止迭代并输出最终结果；否则，转步骤10。

5.3 时间复杂度分析

定理3基于禁忌搜索与贪心策略的异构任务调度混合算法的总时间复杂度为O(n2)。

证明本文假设异构任务数量为q，对应可供分配的边缘服务器数为n，且实际应用中任务调度测试基准满足n>q，分析异构任务调度算法的时间复杂度应从以下两部分进行：

(1)初始解求解部分：步骤1，对q个异构任务进行遍历，计算每个任务在n个边缘服务器上的效用值，时间复杂度为O(nq)；初始化异构任务调度状态转移矩阵flag，时间复杂度为O(nq)；步骤3，遍历异构任务集合，将任务分配给满足资源约束的具有最大效用值的边缘服务器，时间复杂度为O(nq)。因此，初始解求解部分的时间复杂度为O(nq)。

(2)初始解优化部分：步骤8，初始化大小为n×n的禁忌矩阵，时间复杂度为O(n2)；步骤11，基于禁忌搜索算法选择效用值大的边缘服务器对进行交换，其交换次数不大于n2，时间复杂度为O(n2)。因此，初始解优化部分的时间复杂度为O(n2)。

由于实际情况下一般n>q，因此，基于禁忌搜索与贪心策略的异构任务调度混合算法的总时间复杂度为O(n2)。定理3得证。

□

6 仿真对比实验与结果分析

为了验证本文所提异构任务调度算法对分布式训练性能的影响，采用Matlab平台进行仿真并分析所提算法的性能。本文算法的相关实验均在同一实验环境中进行，其中：CPU主频为2.80 GHz，内存为8 GB，操作系统为64位Windows 10。本文假设边缘服务器数量n=80，并采用3种基准算法作为对比算法进行对比分析，具体如下所示：

(1)模拟退火算法。通过模拟固体高温退火过程，将温度升高所对应的物体内能模拟为该算法中的目标函数值，相应温度模拟为算法控制参数，得到随机寻优的模拟退火算法。模拟退火算法能够有效避免陷入局部最优的情况，且该算法执行效率与初始解的好坏无关。

(2)贪心算法。即本文算法中求解异构任务调度策略初始解时所用算法。相对于为求得最优解所需要的大量穷举操作，该算法更加简单高效。

(3)随机调度算法。在满足资源约束的前提下对异构任务进行随机调度。该算法能够显著降低算法复杂度。

图2为系统最大带宽B为10 MHz，30 MHz，50 MHz,80 MHz时，本文算法中异构任务数量与系统效用值(即分布式训练性能)之间的关系。由于异构任务所需消耗的计算资源是固定的，因此系统总能耗开销主要依赖于通信能耗开销。随着可用系统带宽的增大，各边缘服务器所能支配的带宽资源与所能容忍的通信能耗开销也随之增大，因此能够在满足约束条件的前提下求得系统效用值更大的近似最优解。而在系统带宽B为10 MHz时，边缘服务器数量超过某一阈值后，系统效用值变化较小，其原因在于大部分边缘服务器无法满足与异构任务调度策略相关的带宽与能耗约束，系统效用值基本趋于平稳。

Figure 2 Relationship between total numbers of heterogeneous tasks and system utility under different bandwidths图2 不同带宽下异构任务数量与系统效用之间的关系

图3描绘了4种不同算法中系统效用值随异构任务数量的变化曲线。与图2的仿真分析结果相似，固定其他参数不变的情况下，同一种算法中系统效用值均随异构任务数量的增大而减少，但能够直观看出的是，由于本文所提算法基于贪心策略得到了一个较优的初始解，能够灵活跳出局部最优的陷阱，因此性能明显优于其他3种基准算法。从图3中可以看出，随机调度算法作为一种概率算法，其求解得到的系统效用值具有较高的不稳定性；贪心算法虽然能够快速地求得局部最优解，但难以保证全局最优；而模拟退火算法与禁忌搜索算法的区别之一是，模拟退火算法主要基于随机寻优策略寻找邻域解，因此较容易错过更优的解。当异构任务数量较少时，4种算法所对应的系统效用值基本一致；而当异构任务数量增多时，本文所提算法明显优于其他算法。

Figure 3 Relationship between total numbers of heterogeneous tasks and system utility of different algorithms图3 不同算法中异构任务数量与系统效用之间的关系

7 结束语

本文对分布式训练中的异构任务调度问题进行了研究，充分考虑了异构任务调度策略与分布式训练性能之间的关系，在保证收敛的前提下对训练性能的影响因素进行理论分析，从而建立了最大化分布式训练性能的优化目标；并将其转化为多维多选择背包问题，在考虑系统带宽与能耗开销的需求下，利用基于贪心策略的禁忌搜索算法为各个边缘服务器进行合理的异构任务调度，最终得到了近似最优的任务调度策略，有效地提升了分布式训练性能。