ElasticFlow: An Elastic Serverless Training Platform for Distributed Deep Learning

  • 作者：Diandian Gu, Yihao Zhao, Yinmin Zhong
  • 机构：Peking University,Microsoft Research
  • 时间：30 January 2023
  • 链接：https://dl.acm.org/doi/10.1145/3575693.3575721

ElasticFlow：一种用于分布式深度学习的弹性无服务器训练平台

背景及动机

深度学习（DL）已经在各种应用和服务中带来了革命性的变化，使得DL训练成为数据中心的重要工作负载。早期使用传统的集群管理器（如Kubernetes或YARN）在云中调度DL作业的方法并没有考虑DL工作负载的特定特征，导致性能不佳。近年来，在专门为DL训练作业设计的以服务器为中心的集群调度器方面取得了重大进展。在数据中心中，DL开发人员请求硬件资源，如物理机器、虚拟机或容器来运行他们的训练任务。虽然这种方法推动了DL应用的发展，但它有两个限制。

首先，它要求DL开发人员具备配置硬件资源和系统级设置的低级专业知识。DL开发人员需要明确地请求和配置硬件资源，即使使用容器也是如此。这对于那些主要关注DL算法的人来说可能是具有挑战性的，因为他们可能缺乏系统级配置方面的专业知识。

此外，DL训练作业严重依赖GPU资源，这需要根据优化训练吞吐量来调整批次大小和工作节点的数量。DL开发人员必须在批次大小、工作节点数量、超参数等方面做出决策，进一步增加了工作流程的复杂性。DL和系统问题的紧密耦合对于没有系统专业知识的DL开发人员构成了重大挑战。尽管像Amazon SageMaker这样的托管服务提供了一定程度的抽象，但DL开发人员仍然需要处理DL和系统相关问题。

其次，以服务器为中心的模型缺乏动态扩展资源的灵活性，这妨碍了集群级别资源的最佳利用，并使得难以提供性能保证。

相比之下，无服务器计算，也称为函数即服务（FaaS），提供了一种在云中运行工作负载的不同方法。在无服务器计算中，资源管理完全委托给云服务提供商。用户只需将他们的工作负载编写为函数并提交给无服务器平台即可。这种方法简化了开发过程，并具有低代码开发DL作业的潜力。然而，当前的无服务器计算平台缺乏对GPU等加速器的成熟支持，限制了它们在DL训练中的应用。需要努力在无服务器计算平台上实现对加速器的支持，并扩展它们在DL训练中的适用性。

通过解决这些挑战并推进无服务器计算平台以支持加速器，可以进一步简化DL训练作业的开发和执行，使DL开发人员更多地专注于算法和模型，而不是系统级配置。此外，无服务器计算中动态扩展资源的灵活性可以提高集群级别的资源利用率和性能保证。

本文认为无服务器集群是未来的趋势，并强调了对服务器上深度学习任务的截止日期（DDL）的重要性。

确保深度学习（DL）任务在服务器性能方面具有保证的截止日期非常重要。在生产环境中，模型需要按时训练和部署，以满足定期产品发布的要求，例如，每天使用最新新闻对BERT模型进行微调，以每天更新推荐服务。现有解决方案主要关注优化作业完成时间（JCT），但对于明确的作业截止日期需要更好的性能保证。

解决这一挑战的一种方法是通过弹性资源配置来满足DL作业在指定截止日期之前的完成要求。这需要灵活性，能够动态调整作业资源，以优化整个集群的资源利用率并满足截止日期。然而，以前的尝试在考虑截止日期时采用了以服务器为中心的方法，缺乏所需的灵活性。

总之，在生产环境中，提供性能保证并满足截止日期对于DL任务至关重要。弹性资源配置和意识到截止日期的调度是优化整个集群的资源利用率并确保及时完成DL作业的重要考虑因素。

传统上，最早截止日期优先（EDF）调度对于满足截止日期非常有效。在这种设置中，作业根据其截止日期排序，假设每个作业只有一个工作人员。将EDF应用于DL作业调度涉及将整个集群视为一个逻辑工作人员，其吞吐量是所有机器吞吐量的总和。然而，这种解决方案不适用于深度学习任务。 在使用多个GPU进行分布式训练时，训练吞吐量不会与GPU数量线性增加。这是由于工作节点之间的通信开销随着工作节点（GPU）数量的增加而增加。因此，训练吞吐量的扩展是非线性的，增加更多的GPU可能无法带来成比例的性能提升。如图显示了常见DNN模型的缩放曲线

DL任务的扩展曲线是凹的，这意味着向分布式任务添加更多资源可能会产生递减的回报。由于存在非线性的扩展行为，有效地分配资源以最大化性能变得复杂。如果用前述EDF调度的话就会产生如图所示的后果

解决方案

因此，ElasticFlow通过一种新的资源分配方法来解决这一问题。该方法可以分为两个阶段：准入控制和资源分配。即先为每一作业分配最小满意份额，以保证作业能够在截止时间前完成，再分配剩下的资源，以加快作业资源释放。

准入控制

ElasticFlow提出了最小满意份额的概念，用于捕捉DL作业的最低资源使用量，以满足准入控制的截止日期要求。

DL训练作业的扩展曲线是凹的，因此每个GPU的吞吐量随着GPU数量的增加而下降，使用单个GPU进行训练是最高效的。 将资源使用量定义为GPU数量乘以运行时间，即

$$ resource\ usage = number\ of\ GPUs × running\ time$$

例如，假设有一个训练作业的扩展曲线如图所示。如果使用一个GPU来训练作业需要1个时间单位，那么使用两个GPU需要2/3个时间单位，使用四个GPU需要1/2个时间单位。资源使用量分别为1、4/3和2。使用单个GPU的资源使用量最低。但不能将每个作业都用单个GPU进行训练，因为可能超期。

最小满意份额：即训练作业保证截止时间所需的最少资源数量。 当作业被分配其最小满意份额时，资源使用量最小。

准入控制：只有当ElasticFlow能够保证作业的截止时间时，才能接受作业。具体而言，ElasticFlow计算每个到达作业的最小满意份额。如果系统的资源超过最小满意份额，作业准入，否则丢弃。

  • \(x_i(t)\) 表示 \(t\) 时分配给作业 \(i\) 的GPU数量。
  • \(T_i\left(x_i\right)\) 表示作业 \(i\) 的缩放曲线，即当GPU数量为 \(x_i\) 时作业的吞吐量（单位时间的迭代数）。
  • \(M_i\) 表示最多需要多少迭代数，即训练终止条件。
  • \(D_i\) 表示任务的截止时间。
  • \(G\) 表示GPU总数。

准入控制会检查是否能找到 \(A=\left\{x_i(t)\right\}\) 满足下列两个条件:

$$ \begin{aligned} & \forall i, \quad \sum_{t=0}^{D_i} T_i\left(x_i(t)\right) \geq M_i ; \\ & \forall t, \quad \sum_{i=0}^{n-1} x_i(t) \leq G . \end{aligned} $$

即截止时间前能达到指定迭代数，且每一时刻所有任务的GPU总量不超过可用数。

本文借鉴了渐进填充的方法，提出准入控制算法来计算非线性扩展曲线下的最小满意份额，关键思想是：对作业按截止时间进行排序，并逐步增加每个作业的GPU数量，直到能够满足条件。伪代码如下：

以上图作业C为例，\(D_c=2\)，\(M_c=3\)，得到\(j=4\)

剩余资源分配

为每个作业分配最小满意份额已经可以提供性能保证，但是在为每个作业分配其最小满意份额后，集群可能仍然有空闲的GPU。因此在分配了最小满意份额后，优化剩余资源的分配。

需要解决的问题表述如下。

其中\(\sum_{t=0}^{D_i} x_i(t)\) 是job \(i\) 在\(t\)时间片使用 \(x_i(t)\) 的总GPU 时间（资源使用量）。非线性扩展下，一个作业占用GPU越多，就需要越多的GPU时间才能达到终止条件。其中第三个约束条件确保没有多余的GPU可以分配给任何作业而不降低吞吐量（\(t=0\)表示资源分配完成后的下一时刻，即，确保初始分配足够，哪怕再多一个GPU都会导致吞吐量降低。）

为了解决这一问题，本文提出了一种贪心算法来分配剩下的资源，核心在于每次将GPU分配给会带来最高边际收益的作业，伪代码如下：

\(a_i(t)\)表示当前已经分配的GPU，初值为准入控制的计算结果。即遍历每一作业，尝试增加1个GPU，如果能缩短训练时间，则根据添加前后的GPU时间变化量为优先级加入优先队列。而后根据优先队列逐一分配GPU，分配过的作业放回尝试池。直到所有GPU分配完或队列为空。

作业放置

DL任务的扩展效率受到工作节点位置的影响。位于同一服务器上的工作节点可以利用高带宽的NVLink或PCIe通信通道在GPU之间交换数据。而跨服务器的通信通常具有较低的带宽。这意味着工作节点的选择会影响整体扩展的效率。如图为相同数量GPU不同放置下的吞吐量。

同时，由于分布式训练中参数同步速度由通信带宽决定，因此训练效率不止取决于资源数量，还取决于资源的拓扑。由于作业放置会影响扩展曲线，而前面提到的准入控制和资源分配都依赖于扩展曲线。这使资源分配问题更加复杂，如果准入控制使用的扩展曲线与实际不符，可能导致资源浪费或作业超期完成。因此调度程序需要考虑一组扩展曲线，而非单个扩展曲线。

本文提出一种拓扑感知的作业放置策略。使用多层级树结构表示GPU的拓扑，叶节点为GPU，非叶节点以不同带宽不同链路连接。如图为4层分层结构的服务器示例。

放置作业时，需要找到一个包含足够的空闲GPU来容纳该作业的子树。这是一个装箱问题，有多种启发式算法可供选择。本文使用最佳适应（Best-Fit）算法，选择空闲GPU数量最接近所需数量的子树，得到最高带宽。此外，如果作业可以迁移，并且工作线程的数量限制在2的幂，则可以通过迁移来消除碎片。即，只要空闲GPU数量足够，一定能找到一组在拓扑中彼此“接近”的GPU，从而将作业放置与准入控制和资源分配相分离（扩展曲线唯一）。

ElasticFlow

整体结构

ElasticFlow的整体结构如下图所示：

ElasticFlow的整体架构

  1. 深度学习开发人员提交深度学习训练作业。
  2. ElasticFlow使用准入控制模块决定接受或丢弃该作业。准入控制模块从监视模块获取当前集群状态，并计算作业的最小满意份额。
  3. 资源分配模块调度已准入的作业，以有效利用资源并满足其截止时间。在每个调度事件（如作业到达或完成）时，资源分配模块可以通过弹性扩展来更新一些作业的资源分配，即根据已接受作业的截止时间和可用GPU数量调整分配给作业的GPU数量。该模块还为给定作业计算本地批次大小（即全局批次大小除以GPU数量）。
  4. 作业放置模块根据拓扑结构从集群中为每个作业选择GPU。
  5. 确定放置后，模块将作业发送到弹性训练执行器，这是一个可由任何弹性深度学习框架替换的插件组件。弹性训练执行器确保每台机器正确执行深度学习作业。

ElasticFlow接口

ElasticFlow训练作业的函数包括以下参数： - DNN模型，即要训练的DNN模型 - 超参数，即训练超参数，如全局batch size、学习率等 - 终止条件，即指示作业完成的条件，只需要指定最大迭代数即可，也可添加其他条件如达到准确率 - 截止时间，即开发者期望完成作业的时间点 - 其他训练组件（数据集、优化器等）

这一无服务器接口与当前以服务器为中心的接口相比具有两个特点： 1. 深度学习开发者只需要提交训练函数，由平台负责资源管理，开发者可视为单机训练，并且只需要指定全局batch size和其他超参数，基于GPU内存决定本地batch size和worker数量等系统级问题由ElasticFlow处理。 2. 深度学习开发者只指定每个作业的截止时间，而不需要控制合适终止分配的机器资源。同时具有灵活性，可以根据作业截止时间和终止条件对分配的资源进行动态调整。

此外，ElasticFlow可以扩展支持无截止时间的作业，在保证截止时间的同时尽量减少无截止时间作业的JCT。它将该类作业的截止时间设置为无限，并在分配了最小满意份额资源后为其分配资源。对于软截止时间（即就算超期也有意义，仍需完成）也进行类似的扩展。ElasticFlow还考虑了恶意用户和节点故障等情况。

实现

  • 接口：python实现，集成在PyTorch1.10.0上，使用PyTorchDDP进行分布式训练，NCCL在worker间通信，给RPC在调度器和worker间交换控制信息。
  • 弹性伸缩：支持多机多卡环境下不停机弹性扩展。弹性前根据决策发送参数给worker，重启，调整本地batch size。弹性前不会删除GPU上的CUDA上下文，并保持NCCL进程组活跃。
  • 吞吐量分析：ElasticFlow基于模拟未来的作业事件来进行调度决策，需要计算每个作业在每个作业事件上可以完成的迭代次数。为了精确计算，首先对每个作业进行预运行，以不同数量的GPU对其吞吐量进行分析。然后作业执行期间继续分析并调整调度决策。

实验评估

  • 测试集群由16台使用ND A100 v4系列虚拟机的服务器组成，共128个40GB的NVIDIA A100 GPU。
  • 此外本文还根据真实A100 GPU的分析信息开发了一个模拟器，误差率不超过3%。
  • 本文中使用两个月的真实世界跟踪数据来评估ElasticFlow。测试集群使用其中一个集群的跟踪数据，模拟器使用全部数据。每个作业都包括提交时间、GPU数量和持续时间等信息，由于不含截止时间，将作业的截止日期设置为其提交后的𝜆 𝑑𝑢𝑟𝑎𝑡𝑖𝑜𝑛时间，其中𝜆从0.5到1.5均匀分布，表示截止日期的紧迫程度。对于每个作业，从下列代表性设置池中随机选一个batch size的DNN模型。
  • 具体设置可以看原文
  • baseline：
    • 最早截止时间优先（EDF）：经典的截止时间调度策略。
    • Gandiva：是一个使用内省调度来持续改进调度决策的DL调度器。不是弹性的（即使用作业跟踪中指定的GPU数量），不感知截止时间。
    • Tiresias：为DL作业定制的二维调度算法。不是弹性的，不感知截止时间。
    • Themis：为DL作业提供完成时间公平性。不感知截止时间。
    • Chronus：最大化可以满足截止日期的作业数量，并最小化尽力而为作业的平均JCT。具备截止日期感知能力，但不是弹性的。
    • Pollux：一种用于DL作业的最先进的调度器。它通过自适应地共同优化统计效率和系统吞吐量来改善JCT。它具备弹性，但不感知截止时间。
  • 评价指标：ElasticFlow的设计目标是满足DL训练作业的截止日期。因此，评估指标是能够满足其截止日期的作业比率。我们还评估集群效率（CE），它衡量集群中资源的利用效率。设\(M\)为集群中的GPU数量，\(tpt\)表示吞吐量，则
    $$ C E:=\frac{1}{M} \sum_{i=1}^M \frac{\text { Current tpt of the job on } G P U_i}{\text { tpt of the job on } G P U_i \text { with } 1 G P U} $$
    该方程通过将每个GPU的相对吞吐量（在特定GPU上的实际处理速度）与作业在该GPU上只有一个GPU时的吞吐量（独占访问GPU时的处理速度）进行比较，然后取平均值来计算集群效率。（不用JCT因为准入控制会丢作业，但扩展为支持无截止时间作业时会比较其JCT）

端到端结果

上图(a)显示了真实测试平台上ElasticFlow与所有baseline的比较结果，可见ElasticFlow提高了能够满足截止日期的作业数量。图(b)为更大规模，同样可见ElasticFlow提高了能够满足截止日期的作业数量。

上图为在测试平台上执行过程中分配的GPU数量以及提交和接受的作业数量。从图中我们可以观察到，当提交到集群的作业较少时，集群中的资源争用较低。ElasticFlow可以充分利用空闲的GPU资源，从而使接受的作业能够更早地完成。而像Gandiva和Tiresias这样的调度器不具备弹性，因此无法利用空闲的GPU。当作业提交突然增加时（例如第13个小时），为了保证接受的作业的截止日期，一些作业会被丢弃。

上图为模拟结果，在更多跟踪数据和更大规模上比较，ElasticFlow始终优于baseline。

提升的来源

准入控制和弹性扩展是ElasticFlow的两个关键组件，为了显示这两个组件的重要性，我们在EDF的基础上开发了两个变种，分别是EDF + 准入控制和EDF + 弹性扩展。

我们改变集群规模并保持相同的负载。上图显示了准入控制和弹性扩展对ElasticFlow改进的贡献，准入控制可以丢弃无法满足截止日期的作业，而弹性扩展可以根据集群状态和作业截止日期及时调整资源分配。只添加其中一个组件到EDF的性能比ElasticFlow差。其次，我们观察到当集群规模增大时，EDF + 弹性扩展和ElasticFlow之间的差距减小。这是因为在保持负载相同的情况下，使用更多的GPU可以接受大多数作业，而弹性扩展对改进至关重要。另一方面，当集群规模较小时，准入控制对于避免在无法满足截止日期的作业上浪费资源是重要的。

资源利用率的改进。我们评估ElasticFlow如何充分利用集群资源。我们模拟了在一个具有16个节点和每个节点有8个GPU的集群上执行100个作业的过程。如果ElasticFlow拒绝了跟踪数据中的任何作业，与基准方法进行比较就不公平。因此，我们将截止日期设置得足够宽松以接受所有作业（1.5倍于作业的持续时间）。这确保了所有解决方案运行相同的作业集。上图显示，在前100个小时内，ElasticFlow实现了比基准方法更高的资源利用率，为后续作业节省了更多的GPU资源。这是因为资源分配模块以高效的方式分配集群中的空闲GPU资源。当完成所有作业时，ElasticFlow还实现了最小的完成时间。

无截止时间作业的处理

ElasticFlow可以调度SLO作业和尽力而为作业。我们改变尽力而为作业的百分比，并测量SLO作业的截止日期满意比率以及尽力而为作业的平均JCT。由于在EDF下的平均JCT与其他解决方案相比过大，为了说明问题，我们将每个解决方案的平均JCT归一化为Gandiva的平均JCT。如上图所示，ElasticFlow在具有截止日期要求的作业中实现了最高的截止日期满意比率。对于有10%尽力而为作业的跟踪数据，ElasticFlow实现了最小的尽力而为作业平均JCT。在其他跟踪数据中，ElasticFlow为具有截止日期要求的作业保留了更多的GPU资源，并按预期在截止日期满意比率上牺牲了JCT。

系统开销

性能分析开销。图(a)展示了不同DL模型的性能分析开销。ElasticFlow通过不同数量的GPU和不同的批次大小来分析每个新的DL模型的吞吐量。ElasticFlow记录了每个作业GPU内存可以容纳的最大本地批次大小，并记录了每个作业的最大和最小GPU数量，以避免性能不佳或内存溢出。如果为具有特定批次大小的作业添加更多的GPU不能增加给定作业的吞吐量，ElasticFlow将停止该批次大小的性能分析过程。由于DL训练通常需要几小时、几天甚至几周，性能分析开销很小。不需要对已知/重复的作业进行性能分析。 扩展和迁移开销。扩展和迁移开销是“暂停作业”和“在新的GPU集上重新启动作业”的时间间隔。图(b)展示了不同DL模型在五种情况下的扩展和迁移开销。前四种情况改变了作业的GPU数量，第五种情况改变了GPU集合（即迁移到另一台机器上的八个GPU）。我们目前的原型使用了PyTorch中可用的简单检查点/恢复功能来进行扩展和迁移。当GPU数量较多时，PyTorch中检查点/恢复的内部实现开销占主导地位。当我们从单个GPU进行扩展或缩减时，ElasticFlow的开销就会显现出来。因此，不同情况下的开销相似；方差主要来自PyTorch中检查点/恢复的内部实现。如果GPU设备在扩展事件后将训练相同的DL模型，可以通过将模型权重保留在内存中进一步优化这种实现。我们在一个生产系统中收集的真实跟踪数据中，ElasticFlow的平均调度间隔约为23分钟。与调度间隔相比，扩展和迁移开销很小。

结论

本文提出了ElasticFlow，一种用于分布式训练的弹性无服务器计算平台。ElasticFlow基于最小满意份额进行准入控制，以保证作业在截止时间前完成。并开发了一种调度算法，根据递减收益原则动态分配资源给已准入的作业。ElasticFlow应用了伙伴分配算法来进行作业放置，以消除拓扑结构的影响。评估结果显示，相比现有解决方案，ElasticFlow能够增加满足截止日期的作业数量1.46到7.65倍。