Page 174 - 《软件学报》2025年第4期

1580 软件学报 2025 年第 36 卷第 4 期

的调度效果.

3.2 优化任务排序
表 6 展示了利用性能建模来优化任务排序的调度方法. 这类调度方法主要针对任务多样性挑战进行解决. 面
对多样化的任务时, 通过对任务执行时间与资源需求进行精确感知, 可设计出更优化的任务执行顺序, 从而权衡不
同类型任务需求, 有效解决挑战. 这类方法采取以上思路, 借助性能建模, 设计了基于优先级、线性规划、图匹配
的算法来优化任务排序, 进而提升调度效果. 具体而言, 有以下方法.

表 6 基于性能建模优化任务排序的调度方法

性能建模需求 实验设置
性能建模
成果 调度目标 性能建模方法 执行 吞吐 收敛 利用方式 效果
时间 率 效率 集群规模 任务规模
假设 降低平均JCT
[27]
Tiresias 完成效率 √ － － 设计优先级算法 60 480
已知 (比Apache Yarn [59] 降低78%)
实测 提升FTF公平性
Themis [60] 公平性 √ － － 设计优先级算法 256 15 000+
GPU
剖析 (比Tiresias [27] 提升2.25倍)
实测 降低平均JCT
Allox [30] 完成效率 √ √ － 设计图匹配算法 40 10 000+
剖析 (比SRTF降低95%)
实测 提升截止时间满足率
Chronus [20] 截止时间 √ － － 设计线性规划算法 120/96 30 000+
剖析 (比EDF [61] 提高75%)

一些方法通过利用性能建模设计优先级算法的方式, 优化任务排序. 如: (1) Tiresias [27] . 该方法假设任务执行
时间是已知的, 随后根据任务执行时间设计了服务时间 (service time) 指标, 该指标由任务占用 GPU 数量乘以其
剩余执行时间进行计算. 相比于直接使用任务执行时间排序, 服务时间能够同时捕获到执行时间与资源占用量
的因素. Tiresias 通过优先调度剩余服务时间短的任务, 能够有效在时空资源需求差异大的任务之间进行权衡. 这
种调度策略, 即 SRSF (shortest-remaining-service-first), 成为后续面向深度学习训练调度方法的常见基准方法.
[60]
(2) Themis 针对公平性问题提出. 该方法针对同构、非弹性场景, 因此采取简单的实测剖析法获取执行时间. 随
后, Themis 设计了适用于深度学习训练任务的公平性指标: FTF (finish-time-fairness). 该指标使用独占资源时的执
行时间除以共享资源时的执行时间 (由建模得出) 计算. 该指标适配放置拓扑敏感、执行时间较长的特性, 使调度
器倾向于优先执行那些在较长时间内获得服务较少的任务. 随后 Themis 设计了基于投标拍卖的优先级算法, 以在
集群层面达到较高的 FTF 指标. FTF 指标成为后续面向公平性调度方法的常用指标. 相比于 DRF [62] 等传统的性能
无感公平性调度, 基于 FTF 指标的调度能够有效捕获深度学习训练任务在不同放置方式下的性能差异, 更准确地
描绘资源分配的公平程度. 以上方法, 通过利用性能建模设计排序标准进行排序. 虽然它们具有较高的任务排序效
率, 然而这种排序过程未考察任务在全局的排序可能性, 因此仅能取得次优排序结果.
Allox [30] 通过利用性能建模设计最优图匹配算法, 对任务排序进行优化. 该方法将单 GPU 任务排序问题映射
为最小成本二部图匹配问题. 其中, 性能建模得到的任务执行时间被映射为二部图匹配的“边”成本, 因此性能建模
成为该调度算法设计的必要前提. 由于仅关注单 训练任务, 因此实测剖析法产生的开销较低, 适用于该场景.
这类图匹配的方法能够在多项式时间内取得理论最优的任务排序, 然而目前的图匹配算法不能将分布式任务纳入
问题的映射, 因此适用场景有限.
Chronus [20] 通过性能建模设计了线性规划算法进行优先级求解. 该方法针对截止时间目标进行优化. 该方法面
向同构 GPU、任务资源配置固定的场景, 因此可使用实测剖析法以较低开销准确建模任务执行时间. 获得执行时
间建模后, Chronus 可据此判断任务的截止时间可满足性, 并可将不可满足的任务延迟调度, 避免队头阻塞. 该方
法将最小化截止时间违约率的优先级排序转化为带执行时间约束的混合整数线性规划问题, 利用求解器快速获得
最优任务排序. 相比于 EDF [61] 等传统的性能无感算法, Chronus 能有效避免截止时间无法满足的任务抢占集群资
源. 然而, Chronus 的线性规划建模要求任务支持抢占式调度, 这引入了一定的抢占开销, 对任务完成效率具有一