论文：Optimus5秒内调度1.6万个节点中的10万个任务 面向深度学习集群的高效动态资源调度程序

这是另一篇承诺现在有望缩短深度学习训练时间的论文。香港大学和北京字节跳动公司的研究人员共同开发了Optimus，它不是改进编程模型及/或数据流引擎，而是改进集群内作业的调度。

你可以在Kubernetes的上面运行它；论文作者声称，与如今使用最广泛的调度程序相比，Optimus将完工时间（makespan）缩短了1.6倍。

深度学习集群

我们在使用更庞大的模型，数据量不断增加。一般来说，这提高了学习的准确性，但也延长了训练时间。最常用的方法是使用机器学习集群的并行训练。一个模型通常在多台参数服务器之间划分，训练数据分布在多个worker节点上。worker计算参数更新，并将其推送到相应的参数服务器。

训练是一个迭代过程，数据集分成多个块，每个块进一步分成小批量数据（mini-batch）。训练步骤处理一个小批量数据，并更新梯度（参数值）。我们还可以在每个小批量数据结束时计算训练性能指标。所有小批量数据都处理完毕后，这就完成了一个迭代（epoch）。通常，一个模型针对好多迭代（几十个到几百个）加以训练，直到它收敛（性能指标趋于稳定）。

下图显示了示例性能指标及其在迭代上的进展情况：

训练可能是同步的（每个训练步骤结束时有一个障碍），也可能是异步的。

…...与实验模型不同，生产级模型是成熟的，而且通常很好地收敛到全局/局部最优，因为所有的超参数（比如学习速率即DNN调整自己的速度有多快和小批量数据大小）都已经在实验阶段经过了精心调整。在这项工作中，我们专注于这类生产级模型，利用它们的收敛属性来估计训练作业在趋向收敛方面的进展。

尤其是，Optimus使用训练损耗的收敛。

集群调度程序用于为参数服务器和worker节点分配资源。每个作业一提交，现有的调度程序（比如Borg和YARN）就为作业分配固定数量的资源，在作业运行时并不改变资源。被分配的worker节点和参数服务器的数量影响训练速度。假设我们有20个容器的预算，就可以在参数服务器和worker节点之间进行分配，只要觉得合适。下图显示了对于ResNet-50模型而言，最大训练速度借助8个worker节点和12台参数服务器来获得：

另外，如果我们将参数服务器与worker节点的比率固定于1：1，并在保持该比例的同时增加可用容器的数量，就会得到如下图表：

请注意，一旦超出某个数值，增加更多资源会开始减慢训练速度！整体训练时间可能短则几分钟，长则几星期，这取决于具体的模型和数据。

Optimus的大体设计

在生产级集群中，作业训练速度进一步受到许多运行时因素的影响，比如当时的可用带宽。因此，一提交作业，就配置固定数量的worker节点/参数服务器是不可取的。在Optimus中，我们通过调整worker节点和参数服务器的数量和布置，最大限度地利用可用性不一的运行时资源，旨在每次寻求最佳的资源效率和训练速度。

为了做出正确的决策，Optimus需要了解资源配置与训练作业实现收敛所需的时间之间的关系。Optimus构建并拟合性能模型，以估计一个作业需要多少步骤/迭伐才能达到收敛，以及不同组合的资源和参数服务器如何影响训练速度。大约需要10个样本才能了解足够好的初始近似值。

…...我们为资源配置不一样的几个步骤运行作业，使用从这些步骤收集的数据来学习了解训练速度与资源配置有关，然后继续调整我们的模型。

使用从这些模型获得的预测，Optimus使用一种基于估计边际收益的贪婪算法，将资源分配给worker节点和参数服务器。然后使用尽可能少的服务器来分配任务，遵循下面这个约束条件：每台服务器运行p台参数服务器和w个worker节点（即p和w的值在所有服务器上都一样）。

为深度学习作业建模

第一个模型用于估计作业完成所需要的步骤/迭代的数量。在步骤数给定的情况下，SGD以O（1 / k）的速率收敛。所以我们可以使用下列模型来得出近似的训练损耗曲线：

其中l是训练损耗，β0、β1和β2是训练系数。这些是针对不同深度学习作业的实际训练损耗曲线的几个例子：

随着我们在每个步骤后获得更多的数据点，模型拟合（预测误差）得到了改善，如下所示：

以下是训练Seq2Seq模型时模型拟合的示例：

第二个模型用于根据不同参数服务器和worker节点配置的计算和通信模式来估计训练速度。不妨从异步训练入手，worker节点按自己的步伐处理小批量数据。假设有w个worker节点和p台参数服务器，训练速度函数f（p，w）近似于如下：

就同步训练而言，我们的进度取决于数据集大小M，这意味着每个worker节点都被分配了m = M/w个小批量。训练速度函数近似于如下：

想学习了解θ参数的值，每个模型在针对几个步骤的训练数据小样本集上加以训练，拥有p和w的多个组合。每次运行用时几十秒。非负最小二乘（NNLS）解算器用来找到最佳的拟合参数。下面是模型拟合的几个示例：

动态调度

作业以联机方式到达，并且在每一步，Optimus将资源分配给新提交的作业，并调整现有作业的资源分配。该调度程序旨在使这些作业的平均完成时间最小化。由于了解剩余训练步骤的估计数量，以及训练速度如何受资源影响的模型，这成为了约束求解问题。论文作者引入了边际收益（marginal gain）作为导致有效近似值的启发式方法这个概念。让集群中的主导资源（dominant resource）成为最备受争夺的资源类型（至少这是我的解读，实际论文称“主导资源是指集群总容量中拥有最大份额的那种资源”，我不是百分之百确信作者所说的主导资源是什么意思）。边际收益是当一个worker节点（或参数服务器）被添加到作业后作业完成时间的估计缩短值，除以worker节点（参数服务器）占据的主导资源的数量。

最初每个作业被分配一个worker节点和一台参数服务器。然后我们迭代，将worker节点（参数服务器）贪婪地添加到每次迭代中边际收益最大的那个作业。集群资源耗尽，或边际收益全部为负时，迭代停止。

现在我们为每个作业分配了worker节点和参数服务器，下一个阶段是将它们放置到服务器上。

考虑到同步训练作业中的worker节点和参数服务器的数量，在同构服务器集群中，为作业达到最大训练速度的最佳worker节点/参数服务器的放置原则就是，使用最少数量的服务器来托管运行作业，以便在其中每一台服务器上部署同样数量的参数服务器和同样数量的worker节点。

检测零星的worker节点并通过启动新的worker节点来替换它们也很重要。

最后一个难题是通过仔细划分模型参数来确保参数服务器之间的工作负载均衡得当。因篇幅所限，我不在此赘述，不过你可以在论文（https://dl.acm.org/citation.cfm?id=3190517）的第5.3节找到相关介绍。

评估

使用许多现有系统中所用的主导资源公平（DRF）算法，将Optimus与基于公平的调度程序进行一番比较，并使用Tetris算法进行了比较，该算法将资源优先分配给持续时间短或资源消耗少的作业。与基于DRF的调度程序相比，Optimus将平均完成时间和完工时间分别缩短了2.39倍和1.63倍。

资源分配算法是实现这种性能提升的最主要因素。Optimus可以在约5秒钟内调度16000个节点上的100000个任务。

我们在Kubernetes集群上进行了实验，结果表明Optimus的性能显著优于颇有代表性的集群调度程序。

论文全文：