AI Systems
Gavel: Heterogeneity-Aware Cluster Scheduling (OSDI'20)
约 5 分钟阅读
Gavel: Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads
- 会议: OSDI 2020
- 作者: Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee, Matei Zaharia (Stanford & Microsoft Research)
- 链接: Paper PDF | GitHub
一句话总结
Gavel 是一个异构感知的集群调度器，通过将调度策略统一表达为优化问题，并引入 effective throughput 抽象，使异构加速器集群（GPU、TPU 等）的 makespan 和平均 JCT 分别提升 1.4x 和 3.5x。
问题与动机
现代 DL 训练集群中混合部署了多种加速器（V100、P100、K80、TPU 等），但现有调度器存在三个关键问题：
- 性能异构性被忽略: 不同模型在不同加速器上的训练吞吐量差异巨大（如 ResNet-50 在 V100 上比 P100 快 2.6x，但 Transformer 只快 1.4x），现有调度器将所有 GPU 视为等价资源，导致分配次优
- 策略通用性不足: Allox、Gandiva 等调度器只针对单一调度目标优化，而实际集群需要支持多种策略（公平性、makespan、SJF 等）
- 协同优化缺失: Space sharing（多任务共享 GPU）和 placement（任务放置）等优化在异构环境下效果不同，需要统一考虑
核心设计
Effective Throughput 抽象
Gavel 的核心抽象。对于每个 job，定义其在不同加速器类型上的 effective throughput：
- 构建吞吐量矩阵 T：
T[job][accelerator_type]= 该 job 在该加速器上的训练吞吐量 - 分配矩阵 X：
X[job][accelerator_type]= 该 job 在该加速器类型上分配的时间比例 - Effective throughput = 加权吞吐量之和，归一化后用于各种调度策略
调度策略统一为优化问题
Gavel 将多种经典调度策略转化为异构感知的优化问题：
| 策略 | 目标 | 来源 |
|---|---|---|
| Max-Min Fairness (LAS) | 最大化最小 effective throughput | Tiresias |
| Finish Time Fairness | 最小化完成时间不公平性 | Themis |
| Minimize Makespan | 最小化所有任务完成时间 | - |
| FIFO | 先到先服务 | - |
| SJF | 最短任务优先 | - |
| Minimize Cost | 最小化公有云实例成本 | - |
| Hierarchical | 多级策略组合 | - |
关键洞察：所有策略都可以用 effective throughput 替换原始吞吐量，自动获得异构感知能力。
Round-Based 调度机制
将时间划分为固定长度的 round（默认 6 分钟），在每个 round 内：
- 求解优化问题得到最优分配矩阵 X
- 按优先级分配 job 到加速器
- 优先级 = 目标分配比例 / 已获得的 round 数（确保长期收敛到最优分配）
吞吐量估计器
- 对少量 job 进行短时间 profiling（几分钟）
- 利用模型架构相似性进行外推
- 支持 space sharing 场景下的吞吐量预测
评估结果
在物理集群（V100 + P100 + K80）和模拟器上的实验：
- 平均 JCT: 异构感知策略比无感知策略提升最高 3.5x
- Makespan: 提升 1.4x
- 集群承载能力: 异构感知策略使集群能承受更高的任务到达率
- 调度开销: 优化求解在秒级完成，round-based 机制开销可忽略
- 吞吐量估计: 预测误差在 10% 以内
与相关工作对比
| 系统 | 异构感知 | 多策略支持 | Space Sharing |
|---|---|---|---|
| Gandiva (OSDI’18) | ✗ | ✗ | ✓ |
| Tiresias (NSDI’19) | ✗ | ✗ (仅 LAS) | ✗ |
| Themis (NSDI’20) | ✗ | ✗ (仅 Fairness) | ✗ |
| Allox (EuroSys’20) | 部分 | ✗ | ✗ |
| Gavel | ✓ | ✓ | ✓ |
局限性
- 假设 job 的资源需求（GPU 数量）由用户指定，不自动调整
- 不处理抢占开销（假设 checkpoint/restore 成本可忽略）
- 吞吐量估计依赖 profiling，新模型架构需要额外 profiling
关键 Takeaway
- 异构性在 DL 集群中普遍存在且影响显著，调度器必须感知
- 将调度策略表达为优化问题是实现通用异构感知的优雅方式
- Effective throughput 是一个简洁有力的抽象，可以将任意同构策略转化为异构感知版本
- Round-based 调度机制在实践中能很好地逼近最优分配