Shockwave: Fair and Efficient Cluster Scheduling for Dynamic Adaptation in Machine Learning

摘要

• 动态自适应已经成为加速分布式机器学习(ML)训练的关键技术

  • 最近的研究表明，动态调整模型结构(例如，彩票假设[16])或超参数(例如，批量大小[1])可以显着加快训练而不牺牲准确性
  • 然而，现有的机器学习集群调度器并不是为处理动态适应而设计的

• 我们发现，当训练吞吐量在动态适应下随时间变化时，现有的方案不能提供公平性，降低系统效率

• Shockwave，一个基于两个关键思想的具有未来规划的调度器。

  • 首先，Shockwave 将经典市场理论从静态设置扩展到动态设置，从而实现效率和公平的协同优化
  • 第二，Shockwave利用随机动态规划来处理动态变化

• 我们建立了一个Shockwave系统，并通过跟踪驱动仿真和聚类实验对其性能进行了验证

  • 结果表明，与现有的公平调度方案相比，对于具有动态自适应的 ML 作业跟踪
    • Shockwave 方案的完成时间提高了1.3倍
    • 公平性提高了2倍

引言

• GPU 驱动的深度神经网络(DNN)训练正迅速成为数据中心的核心工作负载。

  • 由于训练数据量庞大，模型规模不断增大，许多 DNN 模型无法在单个 GPU 设备上进行训练，分布式多 GPU 训练已成为常态。
  • 对 GPU 设备日益增长的需求促使企业整合硬件资源，并在共享的 GPU 集群中运行工作负载。
  • 因此，建立能够公平地仲裁 GPU 资源竞争任务之间的调度机制，并有效地为高集群利用率调度这些任务是非常重要的。

• 虽然在为 DNN 工作负载设计调度程序方面有大量的工作，但是他们并没有使用严格的方法来协同优化系统的效率和公平性。

  • 像 Gandiva [41]和 Tiresias [21]这样的系统使用诸如动态缩放、时间分片和超额订阅等技术优化完成时间和平均 JCT (作业完成时间) ，但不考虑公平性。
  • 基于处理器共享的方法，如 DRF [17]和 Gavel (加权极大极小公平)[33]在每个调度周期中提供(主导)资源的即时公平共享，但这可能会显着损害效率[20,35]。
  • 基于 Stride [39]的调度方法，如 Gandiva-Fair [10]要求集群运营商明确指定单个作业的份额(例如，A20% 和 B80% 的 GPU) ，手动指定的固定份额可能违反机器学习作业的长期公平性[29]。
  • 最后，AlloX [28]和 Themis [29]旨在通过采用基于过滤器的方法来提供长期的公平性，其中在每一轮中，距离公平份额最远的作业子集被过滤，并且在过滤的作业中，最大效率的作业由调度器选择。然而，过滤器值需要繁重的手工调整; 此外，即使仔细调整，使用固定的过滤器可能导致次优效率和公平性(2)。

• 我们设计了 Shockwave，一个利用市场理论的调度器，以一种系统的和有原则的方式，共同优化机器学习训练工作的效率和公平性。

  • 我们制定了一个费舍尔市场[5] ，其中每个工作收到一个平等的预算购买资源的中央仲裁人。
  • 仲裁者然后计算价格，使市场达到一个均衡; 也就是说，每个工作的预算都被用于最大化其性能(例如，训练产量) ，所有的资源都被完全出售。
  • 运用市场理论制定资源配置方案是有力的，因为实现市场均衡既保证了公平，又保证了效率。
    • 每项工作在获取资源方面具有同等的购买力，确保了公平性。
    • 此外，市场清算均衡确保了工作的节约和每个工作的表现是最大限度地给予其预算。

• 虽然经济理论是许多先前系统的基础(例如 DRF [17]、 Themis [29]和 REF [43]) ，

  • 但它们都假设作业具有已知的静态资源请求。这个假设对于弹性机器学习训练工作来说不再正确
    • 其资源需求随时间动态变化
    • 进一步，资源需求的变化依赖于模型更新模式，因此它们是未知的先验
      • 例如，训练作业可以通过计算梯度噪声标度(GNS)来动态调整它们的批量大小[30,31]。
        • OpenAI 使用批量大小缩放(从32到32M)将 GPT-3训练加速500倍[7] ，
        • 同样，BERTLarge 训练使用动态批量大小(256到4096)来实现2.5倍的加速[37]。
  • 本文将市场理论推广到具有弹性资源需求的机器学习作业调度问题

• 现有的调度器要么是不可知的，要么是对动态变化作出反应

  • 它们不能保证公平性或显著降低效率。

    • 关键原因是，当前的最优时间表或权重分配在未来可能是次优的，被动地重新排列工作的优先级可能为时已晚，无法弥补早期阶段的优先级不足

  • 最先进的调度器可以适应动态性

    • 例如，Pollux 可以代表作业自动调度，例如，可以自动调整批量大小。
    • 我们发现这会影响训练的准确性

  • 我们的目标是让用户根据算法的需要执行弹性变化。

    • 在动态条件下实现公平分配而不需要对动态进行任何控制是具有挑战性的
    • 现有的研究也没有对此进行研究。

• 为了支持资源需求随时间的动态变化，我们扩展了经典的静态费舍尔市场，并提出了一个新的离散的动态市场，可以确保长期的效率和公平性。

  • 使用离散时间可以帮助我们捕捉多轮重复运行市场的效果，而动态市场可以帮助我们捕捉作业的时变效用。
    • 例如，考虑一个场景，其中我们为一个作业运行20轮调度。
    • 如果一个作业的 perGPU的batchsize在10轮后由于 GNS （梯度噪声规模）扩展而翻倍，那么在10轮后，他在某个GPU上的利用率分配也会翻倍（$u_1$ = 2 $u_0$)。
    • 一个静态市场将假设利用率随时间不变, 20轮的累计利用率率为20$u_0$;
    • 一个动态市场可以捕捉的变化效用的工作随着时间的推移，20轮的累计效用将是30$u_0$
  • 准确计算效用可以使动态市场随着时间的推移优化公平和效率。
    • 我们证明了我们的动态市场公式(4.2)保证了长期的效率和公平性，例如
      • 随时间推移的纳什社会福利最大化，
      • 随时间推移的帕累托最优最大化，
      • 以及共享激励。

• 在实际系统中实施动态市场公式具有挑战性，主要原因有两个。

  • 首先，市场公式需要知道未来的效用值来计算市场均衡。
    • 作业中的动态适应是不确定性触发的，因为它们依赖于不同模型和数据集的梯度值，这使得预测未来的效用是很有挑战性的。
  • 第二，在(无限)长的时间范围内求解动态市场均衡是困难的和不切实际的。
    • 它在计算上是不可行的，并且需要预测每个作业未来的性能特征
  • 此外，当作业到达并在线完成时，我们需要周期性地解决市场均衡问题，同时保持较低的调度开销。

• 为了弥合理论与系统之间的鸿沟，Shockwave 解决了这些挑战，实现了一个动态适应预测器和一个近似动态市场。

  • 首先，我们观察到现实世界中机器学习工作负载的动态适应遵循一些模式，这些模式可以用贝叶斯统计来预测。
  • 然后，我们发展方法，以整合这些预测到我们的动态市场公式。
  • 其次，在执行基于循环的调度时，我们发现为(无限)长的时间范围规划一个调度可能会引入大量的开销。
    • 为了保持较低的计划开销，Shockwave 只计划有限长度的时间窗(例如，30-60分钟)
    • 我们设计的估计器可以捕捉到短期计划对长期公平性和长期效率的影响
    • 这种设计帮助我们在不牺牲长期目标的情况下平衡系统开销

• 我们在32-GPU 集群试验台上评估了Shockwave，并使用模拟器研究了大规模的 GPU 集群。

  • 使用来自以前的现实世界系统的多个工作负载[33,36]
    • 我们发现与现有的公平的 DNN 集群调度器(包括 Themis [29] ，Gavel [33] ，AlloX [28]等)相比，Shockwave 提高了1.3倍的完成时间和2倍的公平性
  • 我们进一步评估不同大小的集群上的Shockwave。使用与物理集群相同的调度器构建的模拟器
    • 我们发现 Shockwave 可以在256个 GPU 上调度900个活动 DNN 训练作业，并且与现有的调度器相比，保持了最大完成时间(1.26-1.37 ×)和公平性(2.5-3.1 ×)的优势
    • 我们的解决方案开销仍然很低，不到两分钟循环周期的12.5%
  • Shockwave是开源的 https://github.com/uw-mad-dash/Shockwave。

动机