Resource Heterogeneity-Aware and Utilization-Enhanced Scheduling for Deep Learning Clusters

本文提出了名为 Hadar 及其增强版 HadarE 的新型深度学习集群调度系统，通过任务级异构感知优化框架及作业分叉并发策略，在显著提升资源利用率的同时大幅缩短了模型训练时间并改善了模型推理质量。

要点

这篇论文介绍了一种名为 Hadar（及其升级版 HadarE）的“超级调度员”，专门用来管理深度学习（AI 训练）集群中的 GPU 资源。

为了让你更容易理解，我们可以把深度学习训练集群想象成一个巨大的、繁忙的“烹饪厨房”。

1. 背景：混乱的厨房

• 场景：这个厨房里有各种各样的炉灶（GPU 显卡），有的非常高级（像 V100，火力猛、速度快），有的比较老旧（像 K80，火力小、速度慢）。
• 任务：有很多不同的厨师（AI 模型训练任务）要在这里做饭。有的菜需要大火快炒（ResNet-50），有的菜需要小火慢炖（A3C）。
• 问题：
  • 以前的调度员（比如 Gavel）有点“死板”。如果一个厨师需要 4 个高级炉灶，但厨房里只有 3 个高级炉灶和 3 个旧炉灶，调度员就会说：“不行，炉灶不够，厨师你等着吧！”哪怕旧炉灶闲着，它也不让厨师用，导致很多炉灶闲置，做饭效率很低。
  • 这就好比：明明有 3 个旧炉灶能帮忙，却非要等 4 个新炉灶凑齐，结果大家都饿肚子。

2. 主角登场：Hadar（精明的调度员）

Hadar 是一个更聪明的调度员，它有两个核心绝招：

• 绝招一：看人下菜碟（任务级异构感知）

  • 以前的调度员只看“厨师”本身，Hadar 则看“厨师”在“不同炉灶”上的表现。
  • 它知道：虽然旧炉灶慢，但用来炒这道菜可能只慢一点点；而新炉灶炒那道菜可能快 10 倍。
  • 比喻：Hadar 会灵活安排。如果高级炉灶满了，它会让厨师把一部分任务分给旧炉灶。就像让一个厨师同时用大火灶炒主菜，用小灶炖汤，只要能把菜做出来，就不让任何炉灶闲着。
  • 效果：厨房利用率提高了，所有菜做完的总时间缩短了。

• 绝招二：数学优化（原对偶框架）

  • 它不是拍脑袋决定谁用哪个炉灶，而是用一套复杂的数学公式（原对偶算法）来算出“最优解”。
  • 比喻：这就像是一个超级计算器，瞬间算出怎么分配炉灶，能让所有厨师在最短的时间内把饭做完，而且让炉灶的“性价比”最高。

3. 升级版：HadarE（分身术大师）

虽然 Hadar 已经很聪明了，但它还有一个限制：它通常把一个厨师限制在一个区域（一台机器）里工作。如果厨房里还有空炉灶，这个厨师也不能分身去用。

HadarE 给 Hadar 加了一个“分身术”功能：

• 核心逻辑：如果一个厨师要炒一大锅菜，HadarE 会把这个厨师复制成 5 个分身。
• 操作：这 5 个分身可以同时在厨房里的 5 个不同炉灶上工作。
  • 分身 A 在高级炉灶上炒。
  • 分身 B、C 在旧炉灶上炒。
  • 分身 D、E 在另一个机器的炉灶上炒。
• 收尾：每个分身炒完一部分后，会把结果汇总（就像把分开的汤倒回一个大锅里搅拌均匀），最后合成一道完美的菜。
• 比喻：以前是“一个人守着一个灶台”，现在是“一个人同时指挥 5 个灶台”。只要厨房里有空灶，分身就去用，彻底杜绝了炉灶闲置。

4. 实验结果：真的快吗？

作者真的在真实的“厨房”（AWS 云集群和实验室集群）里测试了：

• 效率提升：
  • 相比以前的“死板调度员”（Gavel），Hadar 让厨房利用率提高了 20% 左右。
  • 用了“分身术”的 HadarE，利用率更是提高了 45% 甚至更多！
• 速度提升：
  • 做完所有菜（训练完所有模型）的总时间，HadarE 比 Gavel 快了 50% 到 80%。这意味着以前要等 10 小时的训练，现在 2-5 小时就搞定了。
• 菜的味道（模型质量）：
  • 最神奇的是，虽然分身在不同的炉灶上干活，但最后合成的菜（训练好的 AI 模型）味道更好（推理准确率更高）。
  • 原因：可能是因为不同的炉灶（硬件）让模型学到了不同的特征，最后汇总起来更聪明。

5. 总结

这篇论文的核心思想就是：
不要死板地等待资源凑齐，也不要让资源闲置。

• Hadar 教会我们：根据任务特性，灵活地把任务拆分到不同性能的硬件上。
• HadarE 教会我们：如果一个任务太大，就把它“分身”成多个副本，同时利用所有可用的硬件资源。

这就好比在高峰期点外卖，以前是“等 4 个骑手都到齐了才发车”，现在变成了“谁有空谁先送，送一部分算一部分，最后汇总”，结果就是大家都吃得更快，外卖员也不闲着。

技术摘要

这是一份关于论文《Resource Heterogeneity-Aware and Utilization-Enhanced Scheduling for Deep Learning Clusters》（面向深度学习集群的资源异构感知与利用率增强调度）的详细技术总结。

1. 研究背景与问题 (Problem)

随着深度学习（DL）应用的普及，企业构建了包含多种加速器（如不同型号的 GPU、TPU）的强大集群来训练模型。然而，现有的集群调度器在应对资源异构性和资源利用率方面存在显著不足：

• 细粒度异构感知缺失：现有的先进调度器（如 Gavel）虽然感知到不同加速器对同一任务的性能差异，但通常仅在**作业级（Job-level）进行调度。如果一个作业需要 4 张 V100 GPU，而集群中只有 3 张 V100 和 3 张 K80，Gavel 会拒绝调度该作业，导致资源闲置。它未能利用任务级（Task-level）**的异构性，即允许一个作业的任务分散在不同类型的 GPU 上并行执行。
• 资源利用率低：由于上述限制，当集群中存在空闲节点但无法满足特定作业的完整资源需求时，这些节点会被闲置，导致整体集群资源利用率（CRU）低下。
• 训练时间长：低效的资源分配直接导致了总训练时间（Total Time Duration, TTD）和平均作业完成时间（JCT）的增加。

2. 方法论 (Methodology)

论文提出了两个核心组件：Hadar（基础调度器）和 HadarE（增强版调度器）。

A. Hadar：细粒度异构感知调度器

Hadar 旨在通过优化框架解决任务级的资源分配问题，同时考虑时间和空间维度。

• 优化模型：将调度问题建模为一个最大化所有作业效用（Utility）的优化问题。效用函数通常与作业完成时间成反比。
  • 约束条件包括：总迭代次数完成、任务瓶颈吞吐量（由最慢设备决定）、机器容量限制以及作业的资源需求（All-or-Nothing 属性，但在任务级被打破）。
• 求解算法：
  • 由于原问题涉及整数变量和非传统约束，难以直接求解。作者将其转化为整数线性规划（ILP），并基于**原对偶框架（Primal-Dual Framework）**进行求解。
  • 引入对偶子程序（Dual Subroutine）：定义资源价格函数 $k_h^r(t)$，该价格随资源占用率指数增长。高价值作业能获得正收益（Payoff），低价值作业则被过滤。
  • 动态规划（DP）：设计了一个高效的 DP 算法（Algorithm 2）来计算最优调度方案 $s^*$，在多项式时间内做出调度决策。
  • 理论保证：证明了算法具有多项式时间复杂度，并且是 $2\alpha$-竞争的（Competitive），即其解与最优解的差距在常数倍范围内。

B. HadarE：资源利用率增强版

HadarE 在 Hadar 的基础上进行了增强，旨在解决“即使有节点空闲，作业也无法利用”的问题。

• 作业分叉（Forking）：将每个深度学习作业分叉为 $n$ 个副本（$n$ 为集群节点数）。
• 并发执行：允许同一个作业的不同副本在集群中不同的、异构的节点上同时运行。
• 结果聚合与整合：
  • Job Tracker：跟踪所有副本的进度。
  • 聚合（Aggregation）：统计所有副本完成的训练步数（Steps）。
  • 整合（Consolidation）：在每个调度轮次结束时，通过**权重平均（Weight-averaging）**合并所有副本的模型参数，生成统一的模型状态供下一轮使用。
• 初始吞吐量估算：为了解决缺乏先验性能数据的问题，提出了一种基于硬件指标（PMI、PCIe 带宽、Batch Size、模型复杂度等）的吞吐量估算公式，使调度器能在没有详细 Profiling 的情况下立即做出合理决策。

3. 主要贡献 (Key Contributions)

1. 提出 Hadar 调度器：首个在任务级粒度上感知多类型加速器性能异构性的调度器，打破了传统作业级调度的限制。
2. 开发原对偶优化算法：利用原对偶框架和动态规划解决复杂的异构资源分配问题，并证明了其多项式时间复杂度和竞争比界限。
3. 提出 HadarE 增强方案：通过作业分叉技术，使单个作业能利用集群中所有可用节点（包括异构节点），最大化资源利用率。
4. 理论与实验验证：
   • 理论证明了算法的近似最优性。
   • 在 AWS 云集群和本地物理集群上进行了广泛评估，对比了 Hadar、HadarE 与 Gavel、Tiresias、YARN-CS 等主流调度器。

4. 实验结果 (Results)

实验在 AWS 集群（5 节点，含 V100, K80, T4）和本地实验室集群（5 节点，含 Titan RTX, T4, T400, 3090, A2000）上进行。

• 资源利用率 (CRU)：
  • Hadar 相比 Gavel 提升了 1.20 倍 (AWS) / 1.21 倍 (本地)。
  • HadarE 相比 Gavel 提升了 1.56 倍 (AWS) / 1.62 倍 (本地)。HadarE 几乎消除了节点的空闲时间。
• 总训练时间 (TTD)：
  • Hadar 相比 Gavel 缩短了约 1.17 倍 (AWS) / 1.16 倍 (本地)。
  • HadarE 相比 Gavel 缩短了 1.79 倍 (AWS) / 2.12 倍 (本地)。相比 Hadar 也有显著加速。
  • 在特定负载下，HadarE 将总时间减少了 50% (AWS) 到 80% (本地)。
• 平均作业完成时间 (JCT)：
  • HadarE 相比 Gavel 减少了 2.23 倍 (AWS) / 2.76 倍 (本地)。
  • HadarE 的 JCT 分布范围更窄，表明其调度更加稳定和高效。
• 模型推理质量：
  • 令人意外的是，HadarE 训练出的模型在推理质量（准确率 ACC 和均方误差 MSE）上优于 Hadar 和 Gavel。
  • 原因可能是异构节点并行训练使得更强大的 GPU 承担了更多步骤，且权重平均机制增强了模型的泛化能力。

5. 意义与影响 (Significance)

• 突破调度粒度限制：该工作证明了将调度粒度从“作业”细化到“任务/副本”可以显著挖掘异构集群的潜力，解决了传统调度器因资源碎片化导致的闲置问题。
• 提升训练效率与成本效益：通过大幅缩短训练时间和提高资源利用率，直接降低了深度学习训练的计算成本（Time-to-Solution）。
• 模型质量提升：打破了“加速训练通常以牺牲模型质量为代价”的刻板印象，展示了异构并行训练可能带来更好的模型泛化性能。
• 实用性强：提出的初始吞吐量估算方法使得系统无需漫长的预训练 Profiling 即可运行，适合动态变化的生产环境。

综上所述，Hadar 和 HadarE 为深度学习集群提供了一种高效、灵活且理论完备的调度解决方案，特别适用于包含多种异构加速器的现代计算环境。