本研究由中国科学院软件研究所的Zichao Yang、Heng Wu、Yuanjia Xu、Yuewen Wu、Hua Zhong和Wenbo Zhang主导完成，并于2023年8月发表在ieee transactions on computers期刊（第72卷，第8期）上。

该研究属于计算机科学领域的集群调度与深度学习系统方向。随着深度学习(DL)在计算机视觉、自然语言处理等领域的广泛应用，MLaaS（机器学习即服务）已成为主流趋势。在此背景下，大量深度学习作业在异构GPU集群上运行，导致资源竞争激烈，许多作业的作业完成时间(JCT)远超用户预期，因此部分作业对截止时间变得敏感。然而，现有调度器存在明显缺陷：以效率为导向的调度器虽能最小化总JCT，但完全忽略截止时间要求；而截止时间感知的调度器虽考虑截止时间，却往往导致总JCT大幅增加。更重要的是，在异构GPU集群中，同一作业在不同GPU上的执行时间差异可达3倍以上，而现有方法缺乏定量分析能力，无法在保证截止时间的同时兼顾效率。为解决这一挑战，本研究提出了Hydra，一个新颖的基于定量成本比较的调度器，旨在最小化总延误时间（tardiness）的同时尽可能降低总JCT。

Hydra系统的工作流程主要包含两大核心组件：执行时间估计器（Estimator）和调度器（Scheduler）。首先，在作业执行时间估计阶段，研究团队利用深度学习作业固有的迭代周期性（iterative periodicity）进行精确预测。由于直接运行作业至完成来获取执行时间不现实（通常需数小时甚至数天），Hydra采用了一种自适应采样方法（adaptive sampling method）。研究人员发现，由于CUDA库初始化、内存拷贝、硬件预热等“冷启动”（cold-start）现象，作业最初的若干次迭代执行时间显著长于后续稳定阶段。因此，传统的前端采样（head-based sampling）和随机采样（random sampling）均无法准确估计执行时间。Hydra的自适应采样方法通过计算相邻迭代执行时间的百分比差异δ，当δ小于预设阈值γ时，判定迭代进入稳定状态，然后才开始采样。最终执行时间t由公式t = tb + (i - ib) × (ts / is)计算，其中tb和ib分别为稳定前的执行时间和迭代次数，ts和is分别为采样的执行时间和迭代次数。此外，为了降低估计开销，Hydra在异构GPU上并行运行作业，且仅需少量训练数据子集即可完成估计。对于占65%的重复性作业，Hydra会缓存并重用历史估计结果。

在调度阶段，Hydra采用了一种基于多轮最小成本搜索（multi-round min-cost search）的算法求解最优调度方案。该部分的核心思想是定义一个定量成本函数（cost），其数学表达式为cost(m,s) = Σ(cn + f × tardiness_n)，其中cn为作业jn的JCT，tardiness_n为超出截止时间的延误时长，f为一个极大的惩罚系数（默认设为10^9）。这一定义使成本定量地体现了调度目标：优先最小化总延误，其次最小化总JCT，同时能自然捕获GPU异构性。调度算法流程如下：在每一轮中，算法为每个未分配作业计算其分配到各个GPU上的最小成本mincost，然后全局选择具有最小mincost的作业-GPU对进行分配，并更新该GPU的作业序列。如此循环n轮直至所有作业分配完成。为在每一轮中高效计算某作业集在某GPU上的mincost，研究团队设计了一个基于分支定界（branch-and-bound）的最优作业序列搜索算法，并实现了四种有效的剪枝策略：预测最优剪枝（predict-optimum-pruning）、下界剪枝（lower-bound-pruning）、相对位置剪枝（relative-position-pruning）和约束剪枝（constraint-pruning），极大压缩了搜索空间。为避免数据规模过大时搜索开销过高，Hydra还实现了一个基于交换的启发式算法作为备用，并引入超时阈值参数α来限制搜索时间。

为验证系统性能，研究团队进行了详尽的实验评估。实验设置上，他们在Kubernetes上实现了3250行Go代码的Hydra系统，部署于包含5个节点7块异构GPU（4块RTX 2080 Ti，3块V100）的真实集群上。同时，为进行大规模评估，开发了936行代码的事件驱动集群模拟器，模拟含45块异构GPU的集群。工作负载基于阿里巴巴异构GPU集群的两个月生产轨迹数据生成，包含100,000+作业和6,500+块GPU，同时构建了轻负载和重负载两种工作负载类型，分别为20%和30%的作业设置了截止时间。

实验结果显示，在估计器有效性方面，Hydra的自适应采样方法在各类深度学习作业上均表现出最高的估计精度，其估计误差显著低于前端采样和随机采样方法，且最大估计开销不超过15秒，相较于通常持续数小时甚至数天的作业执行时间可忽略不计。

在调度器有效性方面，真实集群实验和仿真实验均表明，Hydra在总延误时间（total tardiness）指标上一致且显著地优于Chronus、EDF、Gavel和Allox等现有先进调度器。例如，在轻负载仿真实验中，除Hyper外其他所有对比方法均产生大量延误，而Hydra始终保持零延误，仅在批处理作业规模达到350时才出现极少量延误。在总JCT指标上，Hydra比Chronus、EDF和Gavel更低，且与具有理论上最优JCT的Allox相比增幅最多仅为10%，这是在完全满足截止时间的前提下实现的。Hydra的纯启发式版本Hydra*虽然在延误时间上略逊于完整版Hydra，但仍全面优于其他所有对比方法，展现了良好的性能。在完工时间（makespan）上，Hydra同样具有竞争力。

关于估计器对调度效率的影响评估表明，不同的执行时间估计方法对总JCT影响较小，但对总延误时间影响显著，且Hydra的采样方法在处理大规模批处理作业时的优势尤为突出。在搜索开销及剪枝效率评估上，当搜索作业集大小为14时，剪枝策略将搜索空间压缩至原有空间的2.66×10^(-7)倍。默认α为5秒时，最小成本搜索算法有99.03%的概率在规定时间内找到最优结果。参数α的评估显示，较大的α能带来更高的调度效果，但开销也随之增加，适当设定α可在效果与开销间取得最佳平衡。总体来看，在阿里巴巴轨迹上的评估实验表明，相比最先进的现有成果，Hydra可在降低总延误时间85.8%的同时，尽可能降低总JCT。

本研究的核心结论是，Hydra作为面向异构GPU环境下深度学习作业的截止时间感知且效率导向的调度器，通过创新的定量成本比较方法，成功实现了最小化总延误时间并兼顾降低总JCT的双重调度目标。其科学价值在于提出了一种将截止时间约束和效率目标统一于定量成本函数的新范式，以及配套的基于多轮搜索与高效剪枝的最优调度求解算法。应用价值上，Hydra可直接部署于现代MLaaS平台的生产集群中，有效保障用户体验，提升资源利用率。该研究的亮点包括：一是发现并解决了现有调度器在异构环境下缺乏定量分析的不足；二是设计了利用深度学习作业迭代周期性避免冷启动噪声的自适应采样方法；三是提出了基于成本的多轮最小成本搜索框架，并开发了能指数级压缩搜索空间的剪枝策略；四是全面验证了系统在真实生产轨迹和集群上的优越性能。