Papers

待读论文 · 自包含完整解释

AutoSched: An Adaptive Self-configured Framework for Scheduling Deep Learning Training Workloads

未来 workload 预测、因果配置搜索和在线参数更新

论文：ICS 2024 PDF

本文目录 · 18 节
  1. AutoSched 放在调度器的哪一层
  2. 问题背景
  3. 核心设计与调度流程
  4. 关键机制
  5. 1. Global Generator 抓周期，Local Predictor 抓当前未完成负载
  6. 2. Causal Tuner 不只预测最终 JCT，还解释配置通过什么中间量起作用
  7. 3. Trace Aggregator 保留 service load，而不是简单丢 job
  8. 4. 以旁路服务接入现成 scheduler
  9. 实验设置与准确数字
  10. 方法贡献
  11. 局限与适用边界
  12. 与其他绿色论文的技术关系
  13. 调度器自配置的前置背景
  14. 未来 trace 生成的完整算法
  15. 因果搜索六步与聚合公式
  16. 端到端例子与系统数据流
  17. 实验逐 scheduler 解释
  18. 局限、复现与上线判据

AutoSched 放在调度器的哪一层

AutoSched 是现有 DLT scheduler 旁边的自动配置服务。它预测下一时段仍在运行和即将到达的作业，用模拟器、因果模型和 trace aggregation 搜索配置，再在线更新 Tiresias、Themis、Lucid 等调度器的参数。

问题背景

GPU scheduler 的性能不只由算法名称决定，还高度依赖 queue 数量、priority、starvation threshold、lease term、placement threshold、profiler capacity、packing knob 等配置。生产实践通常用一段历史 trace 找一次“最佳参数”，部署后长期不动。但 GPU workload 的提交密度、资源需求和运行时长都在变，固定参数很快过时。

论文在 Helios 上展示，同一天里的 cluster utilization 和每 5 分钟提交量明显变化（PDF p.2，Fig. 1）。三条生产 trace 的作业持续时间从秒到数十天；Helios 的提交周期约为 23 小时；PAI 中约 60% 作业会以同一 task semantic 重复超过 10 次（PDF pp.2-3，Fig. 2）。这些现象带来两个困难：刚收集完的“上一小时 trace”仍可能漏掉长期未完成作业和下一小时到达；而在庞大的混合离散/连续配置空间里逐个仿真也来不及。

动机实验中，固定配置的 average JCT 最坏可达按上一小时动态调参的 3.8 倍；但后者使用过时历史 trace，相比知道真实未来 workload 的 oracle 又会慢到 1.4 倍（PDF p.4，Fig. 4b-c）。因此 AutoSched 同时解决“拿什么 workload 调”和“怎样在时限内调完”两个问题。

核心设计与调度流程

离线阶段，operator 提供配置空间、参数依赖约束、优化目标和中间性能指标。系统从历史 workload 训练 Local Predictor，并用模拟器样本学习配置、中间指标和最终目标之间的因果图。

在线阶段每轮先由 Generation Engine 生成未来窗口：Global Generator 预测 future-arrival jobs，Local Predictor 补上 existing-unfinished jobs。Search Controller 对这段合成 trace 搜配置：BlueFin 采样，约束投影修正非法组合，因果模型淘汰明显差的候选并缩小下一轮搜索范围，Trace Aggregator 则减少模拟器需要处理的 job 数。找到配置后，Scheduler Controller 调用现有 scheduler 的 API 更新参数，并持续把新状态写回 workload repository（PDF pp.4-5，Fig. 5-6）。

默认每小时更新一次配置，最大搜索轮数为 40；后台 causal tuner 可每 5 分钟运行，只有候选目标比当前配置好到预设阈值时才切换，论文示例阈值为 1.1（PDF p.7，Sec. 4.2）。

关键机制

1. Global Generator 抓周期，Local Predictor 抓当前未完成负载

Global Generator 先按每 5 分钟提交数形成时间序列，用 FFT 提取周期成分。在线时取最近一小时的 12 个点作为 reference，在 repository 中找最相似的历史片段并复制其后续作业，作为 future-arrival trace（PDF p.5，Sec. 3.2.1）。它不是训练重型生成模型，而是明确利用“每天相似时段会重复”的可解释假设。

Bursty arrival 无法靠周期预测，于是 Local Predictor 估计当前运行中 job 的剩余时长范围。输入包括最近到达、最近完成以及查询 job 的 arrival time、已运行时间和 GPU request；XGBoost 把 duration 分到 [0,5min)、[5min,30min)、[30min,1h)、[1h,2h)、[2h,4h)、[4h,inf) 六个范围，再从该范围的历史分布采样具体时长（PDF pp.5,7，Table 2 与 Sec. 4.1）。模型每天用新数据重训一次。

2. Causal Tuner 不只预测最终 JCT，还解释配置通过什么中间量起作用

因果图有三层：配置、中间指标、目标。例如 Tiresias 中，queue、threshold、starve limit、pack limit 和 priority 先影响 queuing delay、preemption overhead、speed slowdown，再影响 JCT（PDF p.6，Fig. 7）。operator 只需指定中间指标和不允许的边，FCI 从模拟样本中学习其余结构。

每轮搜索包含 sampling、constraint projection、causal rejection、simulation measurement、model update 和 what-if scope 六步（PDF p.6，Algorithm 1）。候选预测收益低于当前最佳值的 0.95 倍时可被跳过，同时保留探索概率，防止模型早期错误把整个区域封死。What-if analysis 再固定那些不可能改善目标的配置，缩小后续 BlueFin 搜索空间。

3. Trace Aggregator 保留 service load，而不是简单丢 job

模拟开销与 trace 中作业数近似成正比。Aggregator 按 arrival time、duration、GPU request 合并相似作业；对 existing-unfinished job 使用 remaining duration。合并后的 arrival time 取平均、GPU request 求和，并重新校准 duration，使总 GPU-time service 保持一致；排队时间、运行时间等 time attribute 取平均，attained service 等 service attribute 求和（PDF p.6，Sec. 3.3.2）。因此它压缩的是重复结构，不是随便下采样。

4. 以旁路服务接入现成 scheduler

AutoSched 没有重写 Tiresias、Themis 或 Lucid 的核心 policy。约 8,000 行 Python 的 trace simulator 负责快速评估配置，Generation Engine 由容器和 gRPC 触发，Scheduler Controller 只暴露更新配置与收集状态的接口（PDF p.7，Sec. 4）。这种边界使它可复用，但也意味着 simulator fidelity、参数可热更新性和 operator 提供的中间指标会直接决定效果。

实验设置与准确数字

评测使用三段各两周的生产 trace：Philly 为 2017-09-22 至 2017-10-06，Helios 为 2020-07-26 至 2020-08-09，PAI 为第 84-98 天。模拟容量分别设为 100、70、100 台八卡服务器，即 800、560、800 GPUs（PDF p.7，Sec. 5.1）。目标 scheduler 为 Tiresias、Themis、Lucid；基线是全程固定参数的 Fixed、按历史 trace 动态调参的 SelfTune，以及直接知道真实未来 workload 的不可实现 Optimal。

Local Predictor 的 XGBoost 分类准确率在 Philly、Helios、PAI 上分别为 88.21%、90.41%、82.68%，每 1,000 样本推理和 fine-tuning 延迟分别为 0.0331 秒和 0.3291 秒（PDF p.7，Table 3）。去掉 user information 后，Helios 和 PAI 的准确率分别下降 3.77% 和 7.18%（PDF p.8，Sec. 5.2）。因果性能模型在三条 trace 上的平均相对误差为 14.23%、11.17%、15.16%，每 1,000 样本推理 0.0927 秒、在线 fine-tuning 1.4731 秒（PDF p.7，Table 4）。

端到端结果需要按 scheduler 分开看：

方法贡献

AutoSched 将未来 workload 构造与配置搜索分开，并针对 DLT 作业的时间尺度设计控制路径。Global/Local 两路预测区分“尚未到达”和“已经占着 GPU 但不会在 trace 窗口内结束”的负载；因果图按参数依赖与 trade-off 剪枝，trace aggregation 则压低单次评估成本。组合后的重配置周期可以缩短到小时乃至分钟级，每个模块也能单独校准并在失效时回退。

局限与适用边界

与其他绿色论文的技术关系

调度器自配置的前置背景

深度学习调度器不只有算法名称，还有大量运行参数。Tiresias 的队列数量、升降级阈值、starvation limit 和 packing limit 决定短作业优先与饿死；Themis 的 lease 与公平阈值决定多久重算资源；Lucid 的 profiler 容量、packing threshold 决定共置。相同 policy 在不同作业到达密度、时长和 GPU request 分布下，最佳参数不同。生产常用一段历史 trace 离线调一次后长期固定，工作负载漂移后配置就过时。

Helios 一天内 cluster utilization 与每五分钟提交数显著变化，三条生产 trace 的 duration 从秒到数十天；Helios 提交周期约二十三小时，PAI 约百分之六十作业以相同 task semantic 重复超过十次。固定配置的 average JCT 最坏可到用上一小时动态调参的三点八倍；但上一小时仍是过时历史，相对知道真实未来到达的 oracle 又慢到一点四倍。AutoSched 要同时解决 future workload 怎么构造，以及庞大混合参数空间如何在下一轮前搜完。

它不替换 scheduler，而是旁路 control loop。Operator 离线提供配置空间、参数依赖、优化目标和中间指标；系统训练 workload predictor、trace simulator 与因果性能模型。在线每轮生成未来窗口，快速搜索合法候选，预测更好时通过 Scheduler Controller 热更新现有 Tiresias、Themis 或 Lucid。默认每小时更新，最大四十轮搜索；后台 causal tuner 可每五分钟运行，候选目标相对当前好到示例阈值一点一才切换，避免小波动造成配置震荡。

未来 trace 生成的完整算法

Global Generator 预测尚未到达的作业。它把每五分钟 arrival count 形成时间序列，用 FFT 找周期；在线取最近一小时十二个点作为 reference，在 repository 搜最相似历史片段，复制其后续作业属性作为 future-arrival trace。它不是生成神经网络，而是利用日周期与任务复现。若当天是节假日、发布峰值或首次新业务，没有相似片段，预测会失真，后续五分钟 tuner 只能在观察到偏差后纠正。

Local Predictor 补当前已经运行但未来窗口内仍未完成的 existing jobs。XGBoost 输入最近到达/完成作业，以及查询作业 arrival time、已运行时间、GPU request，把剩余 duration 分到零到五分钟、五到三十分钟、三十分钟到一小时、一到二小时、二到四小时、四小时以上六档，再从对应历史分布采具体值。模型每天用新数据重训。Philly、Helios、PAI 分类准确率为百分之八十八点二一、九十点四一、八十二点六八；每千样本推理零点零三三一秒、fine-tune 零点三二九一秒。

Global 与 Local 缺一不可。只复制未来到达会忘记一个已运行数天的大作业仍占 GPU；只预测当前剩余又看不到下一小时 burst。假设未来一小时历史相似段含十个新作业，而当前有两个八卡作业预计剩九十分钟，Generation Engine 应同时放入十个 arrival 和两个 existing-unfinished 的剩余 service。Simulator 从当前集群状态开始运行，不把后者当重新到达，也不重复计算已获得 service。

因果搜索六步与聚合公式

因果图分配置、中间指标、最终目标三层。Tiresias 中 queue、threshold、starve limit、pack limit、priority 先改变 queuing delay、preemption overhead、speed slowdown，再影响 JCT。Operator 指定可观测中间量和禁止边，FCI 从 simulator 样本学其余结构。性能模型三 trace 平均相对误差为百分之十四点二三、十一点一七、十五点一六；每千样本推理零点零九二七秒、在线 fine-tune 一点四七三一秒。

每轮 Causal Tuner 执行六步：BlueFin 采样配置；constraint projection 把非法组合投影到合法空间；因果模型预测并拒绝明显差候选；simulator 实测保留候选；用新样本更新模型；what-if analysis 固定不可能改善目标的参数、缩小下一轮 scope。候选预测收益低于当前最佳的零点九五倍可跳过，但保留探索概率，防止早期模型误差永久封锁好区域。它不是直接用预测值替代仿真，而是用因果关系减少昂贵测量。

Trace Aggregator 按 arrival time、duration、GPU request 合并相似作业。合并后 arrival 取平均，GPU request 求和，duration 重新校准，使总 GPU-time service 近似保持；排队、运行等 time attribute 取平均，attained service 等累计量求和。对正在运行 job 使用 remaining duration。若两个四卡十分钟作业合并成八卡作业，duration 不能仍简单相加二十分钟，否则 service 从八十 GPU-minute 变成一百六十；应保持合并前总 service。这个约束让压缩 trace 仍能近似资源压力。

端到端例子与系统数据流

假设每小时配置轮开始，Global 找到昨日日周期相似段，预测四十个新 job；Local 判定当前六个 running 中四个会跨越窗口。Aggregator 将重复小作业压成若干代表，Search Controller 对 Tiresias 的队列阈值、饿死阈值与 packing limit 采样。因果模型发现某候选虽减少排队，却大幅增加 preemption，预测 JCT 不优，跳过 simulator；另一个候选合法且可能更好，跑完整 trace 仿真。四十轮内找到目标比当前改善超过一点一的配置，Controller 调 scheduler API 更新，repository 继续收真实状态。

若真实 burst 与预测不同，配置可能在本小时次优，但后台每五分钟 causal tuner 可用新状态重搜。切换本身不能回滚已经完成的调度动作，参数是否可热更新由底层 scheduler 决定；AutoSched 只负责旁路生成、搜索和 API。实现约八千行 Python trace simulator，Generation Engine 由容器和 gRPC 触发。这个边界带来复用，也使 simulator fidelity、控制延迟和 scheduler 参数接口成为正确性条件。

Search Controller 可能不总有益。Lucid 配置空间较小，额外 causal 剪枝曾让 average JCT 增加不超过百分之五；此时快速穷举或简单搜索已经足够。AutoSched 适合参数多、仿真 trace 长、workload 漂移明显的系统，不能把一百三十二倍搜索加速理解成所有 scheduler 的端到端收益。

实验逐 scheduler 解释

评测用三段两周生产 trace：Philly 从二零一七年九月二十二到十月六日，Helios 从二零二零年七月二十六到八月九日，PAI 为第八十四到九十八天。模拟容量为一百、七十、一百台八卡服务器，即八百、五百六十、八百 GPU。对照包括全程 Fixed、用历史动态调参 SelfTune 和知道真实未来的不可实现 Optimal。主评测全是模拟，不包含真实 GPU control-plane 切换。

Tiresias 上 AutoSched 相对 SelfTune average JCT 加速一点一零到一点三六倍。Causal Tuner 降低搜索开销九点五到二十二点七倍，Aggregator 再降二点六到五点八倍，合计最高一百三十二倍，多数搜索半分钟内完成。端到端 JCT 的一点三六倍和搜索的一百三十二倍是不同指标：后者只是让在线搜索可完成，不能写成训练加速。

Themis 的目标是 finish-time fairness 不大于一的作业比例。相对 Fixed，该比例提升一点零七到一点一二倍；Search Controller 在 Philly、PAI 再改善四、五个百分点。Causal 与 Aggregator 搜索开销分别降四点八到五点五倍、一点九到三点九倍。Lucid 相对 SelfTune JCT 最高一点一五到一点一七倍；causal tuner 和 aggregator 最多降配置延迟三点四、五点七倍，但 Search Controller 可使 JCT 增不超过百分之五。三种 case 的目标和配置空间不同，不能混成统一最高值。

局限、复现与上线判据

复现先实现三 scheduler 的确定性 simulator，用同一 trace 与固定配置重跑论文基线；再分别验证 Global 的十二点相似片段、Local 六档分类、Aggregator service conservation。Causal 图需保存配置、三个中间指标和目标样本，报告预测误差、被拒候选、探索候选与真正最优差距。最后按 Fixed、SelfTune、AutoSched、Optimal 四条线运行两周，报告 JCT 或 fairness、搜索秒数、配置切换次数和预测 trace 与真实 trace 的偏差。

消融要分别关闭 Global、Local、Causal、Aggregator 和五分钟后台 tuner。没有 Global 时只看现存负载，没有 Local 时漏长作业；没有 Causal 应回到相同 BlueFin 预算，没有 Aggregator 用完整 trace 测时间。参数热更新失败、正在执行 lease 如何处理、切换时 queue 是否重建都需记录。论文没有物理集群实验，复现最好以小型真实集群校准 simulator 的运行、抢占、packing 与切换开销。

适用边界包括周期与重复性弱的新业务，Local 对首次超大模型无法从历史采样，小于等于三十二 GPU 的小集群配置影响有限，operator 仍要提供参数空间、依赖和中间指标。Aggregator 与因果剪枝会损失最优性；Global 的相似历史不能预测异常事件。上线应保留配置回滚、最小驻留时间和改进阈值，预测置信不足时维持当前配置。

最终验收要区分四类错误：future trace 错，搜索模型错，simulator 错，配置更新错。若 oracle 好而 AutoSched 差，先查预测；若预测接近真实但候选差，查因果剪枝；若模拟好、真实差，查 fidelity；若配置正确却频繁震荡，查切换阈值。AutoSched 面向已知配置空间，用未来负载生成、因果搜索和服务量保持聚合，让参数随 workload 漂移在线调整；它并不自动理解任意 scheduler。

六档 Local Predictor 的输出不是精确时长。分类后从该区间历史分布采样，保留相似 workload 的随机性；四小时以上是开区间，特别长训练的尾部更难估。输入中的已运行时间能避免把已跑数小时的 job 当普通新作业，GPU request 反映规模；去掉 user information 后 Helios 与 PAI 准确率分别降百分之三点七七、七点一八，说明用户/团队复现模式确有预测价值，也带来身份漂移和冷启动风险。

Global 的 FFT 只帮助发现周期长度，相似片段检索才提供具体 job 属性。最近一小时十二个五分钟点若和历史某段 arrival count 接近，系统复制那段之后的真实 job 列表，包括到达、duration、GPU request。只匹配计数可能把“许多单卡短作业”和“少数八卡长作业”混淆，因此 repository 中完整后续属性与 Local 补充很关键。异常日没有匹配时应降低预测置信，不能强行复制。

因果图的价值在中间指标可解释。例如增加 packing limit 可能降低 queue delay，却提高 speed slowdown；缩短 lease 可能改善公平响应，却增加 preemption overhead。直接黑盒回归 JCT 只知道某配置好坏，无法在新 trace 上判断哪条机制变了。What-if 固定某参数前要确认其所有因果路径都不可能改善目标；FCI 结构学习有误时可能错误缩小搜索，所以算法保留探索概率，并用 simulator 的真实测量持续纠正。

Aggregator 的正确性可用 service 校验。对每个聚合组，原始总服务量为各 job 的 GPU request 乘 duration 求和；代表 job 的 GPU request 与校准 duration 的乘积应匹配。Arrival 取平均会改变瞬时 burst，过度合并可能低估排队峰值，因此相似阈值要平衡速度与 fidelity。应在完整/聚合 trace 上对同一配置比较 average JCT、p99、preemption 和 utilization，而不仅测 simulator 时间。

三种 scheduler 的配置切换语义不同。Tiresias 改 queue threshold 时，已在队列中的 job 是否重新分级会影响结果；Themis 改 lease 要等当前 lease 结束还是立刻重分配；Lucid 改 packing/profiler 参数不能撤销已经共置的作业。论文通过 Controller API 接入，但真实部署必须定义生效边界和幂等回滚。否则模拟假设瞬时切换，物理 control plane 却延迟，Optimal 与实际差距会扩大。

更新阈值一点一表示候选预测目标相对当前达到足够改善才应用，目的是抵抗模型误差与重配置成本。阈值太接近一会因噪声频繁切换，太高则错过渐进改进；每小时主循环与五分钟后台循环也构成时间尺度折中。复现应扫更新阈值和频率，记录配置驻留时间、切换数、目标波动与搜索开销，而不能把论文示例视为所有 trace 的固定最优。

Optimal baseline 知道真实未来 workload，是信息上界而非可部署算法；SelfTune 使用历史 trace 动态调参，隔离“调参但预测过时”；Fixed 隔离完全不调。AutoSched 若接近 Optimal，说明生成 trace 与搜索都有效；若只胜 Fixed 不胜 SelfTune，可能预测无增益；若搜索快但 JCT 不升，说明配置空间本就不敏感。四者的层级使端到端结果可以诊断，而不是四个普通调度器排名。

安全上线可采用影子模式：Generation 和 Search 持续产候选，但 Controller 只记录不应用，与当前配置的真实结果对照。验证 simulator 误差和回滚后，再只开放一个低风险 knob，设置最大变化幅度与最小驻留时间；最后逐步加入组合配置。Repository 需版本化 trace schema、scheduler 代码和因果模型，否则旧样本在 policy 升级后不可比。AutoSched 自动配置不等于允许搜索器无边界修改生产控制面。

配置约束投影是必需步骤，因为连续优化器可能给出不存在的队列数、负阈值或互相冲突的 lease/priority。Projection 应映射到 operator 声明的离散集合并满足依赖，例如启用 packing 后才有 pack limit；投影后要去重，否则多个采样点落到同一配置浪费仿真。复现记录应同时保存原始样本、投影配置和拒绝原因，判断搜索效率来自因果模型还是单纯约束。

BlueFin 的搜索轮数上限四十意味着最优性取决于初始范围和剪枝。相同随机种子可比较是否使用 causal rejection，多个种子则报告最佳目标和方差。预测低于当前最佳零点九五倍时跳过的方向要与目标定义一致：JCT 是越低越好，fairness 比例可能越高越好，实现需统一成收益分数。符号错误会系统性拒绝好配置，却仍快速结束。

PAI 中百分之六十 task semantic 重复超过十次解释 Local 与历史片段为何有效，但 task semantic 不是源码语义。作业代码或数据规模改变后，同一用户名和任务标记的 duration 可能漂移；模型每天重训只能事后适应。可结合版本、模型参数量或 SchedMate 提取特征扩充输入，但论文未验证。原方法复现应使用 trace 可得字段，不把扩展功能算进已有结果。

Simulator 的服务模型必须体现目标 scheduler 机制。Tiresias 要模拟队列升降、抢占和 packing slowdown，Themis 要模拟 lease 与 finish-time fairness，Lucid 要模拟 profiling 和共置干扰。一个只按 GPU-time 排队的通用 simulator 无法评估配置 knob。八千行实现的价值正在这些策略语义；复现要用小 trace 手算事件顺序，再与模拟日志逐事件比对。

搜索开销应计入配置周期预算。若完整 trace 仿真超过一小时，即使候选更好也来不及应用；Causal 与 Aggregator 合计最高一百三十二倍使多数搜索半分钟内结束。实际每轮还含 trace 生成、模型推理、gRPC 和配置生效。应报告端到端 controller latency 的分解，并在超时情况下保持当前配置，而不是应用未完成搜索中的任意候选。

公平指标与 JCT 的方向不同也影响 trace 聚合。Themis 的 finish-time fairness 取决于单作业理想份额和实际完成，过度合并会丢个体差异；因此 Aggregator 在该 case 不能只保持总 GPU-time，还要保留影响公平的 time attribute。论文分别评测三种 scheduler 正是因为一种聚合误差不一定对所有目标等价。复现应按目标校准聚合粒度。

周期检测也需避免数据泄漏。Global 搜历史片段时只能使用当前时刻以前 repository，Local 训练集不能包含测试窗口未来完成时间，因果 tuner 的 simulator 样本也只能基于生成 trace。若离线回放时不按时间切分，预测会无意看到未来，AutoSched 就接近不可实现 Optimal。两周 trace 应按真实时间推进模型更新与配置，而不是随机划分 job。

配置效果应按 workload segment 分析，而非只给两周平均。分别统计低峰、高峰、burst、长作业占用和周期转折处的 JCT/fairness，检查 Global 在稳定周期有效、Local 在现存长作业有效、后台 tuner 在预测失败后恢复。若平均改善只来自低峰而高峰恶化，生产风险仍高。每次切换还应保存触发的预测 trace 和最佳候选，支持回放。

最小生产保护包括搜索超时回退、非法配置拒绝、API 幂等、应用失败自动恢复旧值、目标连续多轮恶化熔断，以及 repository 故障时保持当前 scheduler。AutoSched 位于控制面，失败不应阻止底层 data-plane 调度。论文关注性能，自包含实现说明还需补这些可用性条件。

最终报告应公开每轮预测、采样、拒绝、仿真和应用结果，才能复核改进来自未来负载质量、因果剪枝还是聚合加速，并定位配置未生效的控制面问题。

还要保存原配置与回滚结果，证明自动搜索失败时不会破坏底层调度服务的连续运行。