[Paper] 研究调度抢占对动态任务图调度的影响

Source: arXiv - 2602.03081v1

请提供您希望翻译的具体文本内容（例如摘要、章节或其他段落），我将为您翻译成简体中文并保留原有的格式。

概述

本文研究了 调度抢占 在动态任务图工作负载中的应用——即一系列相互依赖的任务需要实时分配到计算资源池的情形。作者并未始终坚持原始分配，也不对所有内容进行持续的全局重新优化，而是提出了一种折中方案：仅允许 最近的 任务进行重新调度。其 Last‑K 抢占 模型表明，适度且受控的抢占能够获得几乎全部全重新调度的性能提升，同时保持公平性并将开销控制在可接受范围内。

关键贡献

• Last‑K抢占模型：一种新颖、可调的策略，将重新调度限制在最近提交的 K 个子图。
• 全面的实证研究，覆盖四类工作负载（synthetic、RIoTBench、WF‑Commons、adversarial），比较三种策略：
  1. 非抢占（no reshuffling）
  2. 完全抢占（re‑schedule everything each round）
  3. 部分抢占（Last‑K）
• 多指标评估：makespan、fairness（per‑task slowdown）、resource utilization，以及 scheduler runtime overhead。
• 设计指南：根据工作负载波动性和公平性需求选择 K。
• 开源实现和基准套件，以确保可复现性。

方法论

1. 任务图模型 – 每个进入的作业是一个带有 CPU/IO 需求和前置约束的有向无环图（DAG）。
2. 调度轮次 – 系统周期性收集所有 就绪 任务，并运行启发式算法（例如列表调度）将它们映射到一组固定的同质工作节点上。
3. 抢占策略
   • 非抢占: 一旦任务被放置，其分配永不改变。
   • 完全抢占: 在每轮调度前，调度器丢弃所有先前的放置并重新计算全新的调度。
   • Last‑K: 仅最近 K 个 DAG 中的任务可以重新分配；更早的分配被冻结。
4. 工作负载生成器
   • Synthetic: 参数化的 DAG，深度/宽度可控。
   • RIoTBench: 真实的物联网流处理图。
   • WF‑Commons: 科学工作流痕迹（如 Montage、Epigenomics）。
   • Adversarial: 为考验公平性而构造（例如大量小型、延迟敏感的 DAG 与大型批处理作业混合）。
5. 指标
   • Makespan（总耗时）
   • 公平性指数（基于每个作业慢速的 Jain 公平性）
   • 利用率（CPU 周期用于有用工作的比例）
   • 调度器开销（调度算法消耗的实际时间）

所有实验在 16 节点集群上运行（每节点 8 核），使用相同的基线启发式，仅更改抢占策略。

结果与发现

关键要点

• 部分抢占捕获了 > 80 % 的全抢占完成时间收益，同时保持公平性几乎与非抢占基准相同。
• 开销大致随重新洗牌任务数量线性增长；限制为最近 K 可显著降低调度时间。
• 工作负载波动性很重要：对于高度动态的流（RIoTBench），较大的 K（≈15 % 的活跃 DAG）提供最佳折衷；对于稳定的科学工作流，K = 5 % 已足够。
• 对抗性混合暴露了全抢占的公平性陷阱——小型、延迟敏感的作业会被反复置换——而最近 K 通过“锁定”早期分配来保护它们。

实际影响

• 云原生批处理/流处理平台（例如 Apache Flink、Spark Structured Streaming）可以采用 Last‑K 风格的“部分再平衡”钩子，在不牺牲短作业的延迟保证的前提下提升吞吐量。
• 边缘计算编排器在运行异构 IoT 流水线时，可以将重新洗牌窗口限制在最近的传感器突发上，从而在受限设备上实现更高的 CPU 利用率。
• 调度器设计者获得了一个具体的调节旋钮（K），用于在三大竞争目标之间取得平衡：运行时间（makespan）、公平性以及控制平面开销。论文中的指南帮助根据观察到的作业到达模式设定 K。
• **服务等级协议（SLA）**若对抖动有惩罚时也能受益：通过冻结较旧的分配，系统降低了“任务迁移风暴”导致的临时资源匮乏风险。

实现 Last‑K 非常简单：维护一个活动 DAG 标识符的 FIFO 队列，在新一轮调度开始时，仅从队列尾部提取任务供启发式算法使用；其余任务保持不变直接通过。

限制与未来工作

• 同质资源：实验假设工作节点完全相同；异构的 CPU/GPU 或受内存限制的节点可能会影响最优的 K。
• 单一启发式：本研究使用经典的列表调度启发式；在 Last‑K 约束下探索更复杂的求解器（ILP、强化学习）是一个开放方向。
• 静态 K：论文为每个工作负载选择固定的 K；基于观察到的波动在运行时自适应调节 K 的方案可能进一步提升权衡。
• 网络感知调度：数据传输成本被抽象化处理；将带宽因素纳入考虑可能会改变公平性/利用率的平衡。

总体而言，研究为动态 DAG 调度器提供了一条务实的中间路径，表明 受控且有限的抢占 能在可管理的复杂度下实现接近最优的性能——这一洞见已可被众多生产系统立即采用。

作者

• Mohammadali Khodabandehlou
• Jared Coleman
• Niranjan Suri
• Bhaskar Krishnamachari

论文信息

• arXiv ID: 2602.03081v1
• 分类: cs.DC
• 发表时间: 2026年2月3日
• PDF: 下载 PDF