Learning-Augmented Online Scheduling with Parsimonious Preemption¶
会议: NeurIPS 2026
arXiv: 2605.23255
领域: 优化/理论
关键词: 学习增强在线算法 (Learning-Augmented Algorithms), 非纯理在线调度 (Non-Clairvoyant Scheduling), 节约型抢占 (Parsimonious Preemption), 比例公平 (Proportional Fairness), 完备竞争比
一句话总结¶
本文针对带预测在线调度中频繁盲目抢占引发系统开销的难题，首次建立控制抢占次数与优化总流转时间权衡的理论体系，提出 SNAP 与 PMLF 算法，在单机、不相关并行机及可延展作业环境下取得常数竞争比，并将单作业抢占次数严格约束在预测误差的对数阶。
研究背景与动机¶
在线调度问题广泛存在于大规模云计算集群与数据中心资源分配中。在传统的非纯理（non-clairvoyant）设定下，作业的真实计算需求（processing time）在执行完毕前完全未知。为了防止长作业阻塞导致平均延迟剧烈恶化，经典算法如时间片轮转（Round-Robin, RR）或最短已耗时间优先（SETF）通常需要进行高频且无休止的“盲目抢占”。近年来兴起的“学习增强算法”（Learning-Augmented Algorithms）范式通过引入机器学习对作业大小的先验预测，在一定程度上打破了传统最坏情况的下界。然而，现有的学习增强调度研究几乎全部只关注平均延迟（总完成时间 \(\sum_j C_j\)）的理论界，默认依赖于无代价的任意抢占。
这种理论抽象与工业系统的实际运行存在巨大脱节。在真实的操作系统内核与分布式集群管理（如 Google Borg）中，任务的上下文切换、缓存失效（Cache Invalidation）、进程迁移和内存换页均会带来显著的物理开销。工程界普遍依赖启发式策略（如抢占阈值 Preemption Thresholds 或延迟抢占机制）来抑制抢占，但这些工程启发式缺乏严格的数学保证，一旦预测出现重度偏差，系统延迟将失去最坏情况保障；反之，理论界已证明任何非纯理算法若将单个作业的抢占次数压低到 \(o(\log p_j)\)，其竞争比必然恶化至 \(\Omega(n)\)。如何在结合机器学习预测的同时，既保持可证明的常数级竞争比，又使抢占次数做到极度节约（parsimonious），成为算法设计领域亟待填补的根本空白。
解决该矛盾的核心难点在于：当作业预测存在欠估计或高估偏差时，如何在无需全局精准信息的前提下自适应地划定检查点，并将多机/异构机器下的连续分数速率调度高效整合成非抢占式执行块。本文的切入角度是：利用按对数幂次级数递增的检查点机制来吸收预测误差，并在宏观上分周期对比例公平（Proportional Fairness, PF）凸规划速率进行离线无抢占重构。核心 idea：将在线执行周期化，以预测大小为起点设置几何级数检查点，通过求解瞬时比例公平速率并以常数比例作业达到检查点为周期终止条件，将分数速率调度无缝转化为长执行块的非抢占式调度，实现常数竞争比与误差对数级抢占开销的统一。
方法详解¶
整体框架¶
本文提出的核心算法框架主要包含单机环境下的预测多级反馈队列（Predicted Multi-Level Feedback, PMLF）与异构非相关并行机环境下的自适应模拟非抢占预测算法（Simulated Non-preemptive Adaptive Prediction, SNAP）。在异构非相关机器模型中，每台机器 \(i \in M\) 对作业 \(j\) 具有独特的执行速度 \(\lambda_{ij}\)。SNAP 算法按不相交的执行周期（Epoch \(k=1, 2, \dots, K\)）推进：在每个周期的起始时刻，算法收集当前活跃作业集并求解瞬时比例公平（PF）凸优化问题获取理想处理速率；接着根据各个作业的预测大小 \(\hat{p}_j\) 与已执行量动态计算下一个指数检查点距离；随后算法计算使至少 \(\lceil \beta n_k \rceil\) 比例的作业到达检查点所需的最短虚拟持续时间，从而确定每个作业在本周期的目标处理量；最后调用确定性离线舍入技术将这一簇抢占式速率转化为总长不超过 \(4 l_k\) 的单机无抢占连续执行计划。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入：作业集 J 与预测大小 p_hat"] --> B["比例公平速率求解<br/>凸规划求解瞬时处理速率 y^(k)"]
B --> C["指数检查点与仿真周期确定<br/>计算到下一检查点余量及最短时长 l_k"]
C --> D["目标处理量截断与非抢占调度转化<br/>利用离线舍入构造无抢占/无迁移执行块"]
D --> E["双阶段偏差弱重置机制<br/>未完成作业数降至 g/ε 时重置预测消除过估计"]
E --> F["输出：完成所有作业的低抢占调度执行流"]关键设计¶
1. 比例公平速率求解：刻画异构多机上的全局均衡与最优吞吐
在异构非相关机环境中，由于机器加速比矩阵 \(\lambda_{ij}\) 具有任意异构性，传统基于单机已执行工作量的排序策略完全失效。SNAP 在每个 Epoch \(k\) 开始时，针对当前尚存活的作业集合 \(J_k\)，通过求解如下比例公平凸优化问题确定各个作业的处理速率分配： $\(\max \sum_{j \in J_k} \log(y_j) \quad \text{s.t.} \quad \sum_{j \in J_k} x_{ij} \le 1 \; (\forall i \in M), \quad \sum_{i \in M} x_{ij} \le 1, \quad y_j = \sum_{i \in M} \lambda_{ij} x_{ij} \; (\forall j \in J_k), \quad x_{ij} \ge 0\)$ 该凸优化问题的最优解在全域内平衡了各作业的推进进度，且借助现代线性规划/凸优化求解器可在近似近线性时间内解出。PF 速率的优良数学性质在于：当一组作业以 PF 速率并发推进并在相同时刻结束时，其总完成时间与离线最优调度的差距严格控制在 2 倍以内，为后续的分段竞争比分析奠定了全局基石。
2. 指数检查点与仿真周期确定：以预测误差对数阶约束抢占触发频次
为阻断连续时间调度中无限次微小抢占的发生，SNAP 引入了基于几何级数跳跃的检查点机制。对于作业 \(j\)，其首个检查点由其预测值决定，设定为 \((1+\delta)^{\rho_j}\)，其中 \(\rho_j = \lceil \log_{1+\delta} \hat{p}_j \rceil\)。后续检查点严格限制在满足 \((1+\delta)^h\) 的几何序列上。在周期 \(k\) 中，作业 \(j\) 距离下一个检查点的剩余需求定义为 \(u_{j,k} = (1+\delta)^{h+1} - q_j(e_k)\)。 算法通过对各作业的耗时商 \(u_{j,k} / y_j^{(k)}\) 进行非降序升序排列，选取第 \(\lceil \beta n_k \rceil\) 个作业的耗时作为本周期的虚拟仿真跨度 \(l_k\)。这一设计的极其精妙之处在于： - 抢占摊销：强制保证了在每个周期内至少有 \(\lceil \beta n_k \rceil\) 比例的作业彻底达到指数检查点，因此整个调度执行期间所产生的总周期数（以及随之而来的抢占总数）能够被所有作业的真实检查点到达次数之和严格上界化，得到总抢占次数至多为 \(O(\frac{1}{\beta \delta} \sum_j (1 + \log_2 \frac{p_j}{\hat{p}_j}))\)。 - 进度保真：对于其余未耗尽（未达检查点）的 \((1-\beta)\) 比例作业，它们在周期内完全忠实地按照比例公平速率 \(y_j^{(k)}\) 执行了全量时长 \(l_k\)。
3. 目标处理量截断与非抢占调度转化：将分数速率解构为低开销执行块
由于 PF 速率计算出的分配矩阵 \(x_{ij}\) 具有高度分数性，直接在物理机器上分配将导致不同作业在各机器间频繁切入与迁移。SNAP 将每个作业在周期内的目标加工量截断为 \(v_{j,k} = \min\{u_{j,k}, l_k y_j^{(k)}\}\)，并直接调用非相关机调度中关于抢占式与非抢占式关系的离线舍入定理（Correa et al., Math. Oper. Res. 2012）。 该机制证明：任意时长为 \(l_k\) 且满足分数加工需求 \(v_{j,k}\) 的抢占式分配，均可在多项式时间内舍入并转化为在各机器上独立排程的无抢占（Non-preemptive）且无迁移（Non-migratory）调度，其跨度（Makespan）至多膨胀为 \(4 l_k\)。通过在每个 Epoch 内完全执行该离线无抢占调度，每个活跃作业在一个周期内仅被启动并执行一次，彻底杜绝了周期内部的细粒度上下文切换。结合子实例超可加性（Super-additivity）分解引理，离线最优完成时间之和与各子周期的离线最优解代价紧密挂钩，最终封闭证明了算法整体竞争比不超过 \(14.48(1+\varepsilon)\)。
4. 双阶段偏差弱重置机制：稳健抵御过估计导致的优先级瘫痪
在学习增强算法中，预测过高（Overestimation, \(\hat{p}_j > p_j\)）与预测过低存在非对称性灾难：若短作业被过度预测为超长作业，算法会将其滞后处理，导致竞争比在最差情况下按 \(\max_j (\hat{p}_j / p_j)\) 严重退化。针对该痛点，论文提出了弱强制欠估计（Weakly Enforcing Underestimation）范式。 假设集群历史统计可提供过估计作业总数的上限参数 \(g\)（\(g\) 为全局标量，远比逐个作业预测大小容易获取）： 算法以初始缩放预测正常执行，密切监控系统中未完成作业总数 \(n_k\)；一旦 \(n_k \le g / \varepsilon\)，算法立刻触发状态重置，将所有剩余存活作业的预测基准归位为不低于当前已执行量的最小 \((1+\delta)\) 幂次，在此之后完全视作欠估计处理。该策略将过估计引起的竞争比膨胀完全控制在 \((1+\varepsilon)^2\) 因子内，同时仅引入 \(O(\frac{g}{\varepsilon^4} \log p_{\max})\) 次额外抢占；只要 \(g\) 相对于作业总数 \(n\) 是次线性的，过估计对抢占复杂度的冲击在渐近意义下完全可忽略。
实验关键数据¶
主实验¶
论文在具有 \(m=10\) 台机器、\(n=100\) 个作业的合成异构集群环境中验证算法性能。为模拟现实数据中心硬件异质性，设定 20% 的作业为“特殊作业”（计算需求 \(p_j \sim \mathcal{U}[1, 200]\) 且受限于 2 台特定专用加速机器），其余 80% 为“普通作业”（\(p_j \sim \mathcal{U}[1, 10]\) 可在全部机器运行）。预测误差由乘性扰动因子 \(R\) 控制，即设置预测值 \(\hat{p}_j = \lceil p_j / \xi_j \rceil\)（\(\xi_j \sim \mathcal{U}[1, R]\)），评估不同算法在预测误差指数级攀升时的竞争比（相对离线最优解的比值）与平均每作业抢占次数。
| 评估指标 | 预测误差参数 \(R\) | SNAP (本文) | Hybrid SNAP (c=4) | Doubling (基线) | Blind (无抢占基线) |
|---|---|---|---|---|---|
| 竞争比 (Competitive Ratio) | \(R=1\) (完全准确) | 1.48 | 1.41 | 1.68 | 1.21 |
| 竞争比 (Competitive Ratio) | \(R=16\) (中度误差) | 1.42 | 1.35 | 1.54 | 2.15 |
| 竞争比 (Competitive Ratio) | \(R=256\) (重度误差) | 1.36 | 1.48 | 1.50 | 1.83 |
| 竞争比 (Competitive Ratio) | \(R=1024\) (极大偏差) | 1.38 | 1.42 | 1.52 | 3.40+ (持续恶化) |
| 平均每作业抢占次数 | \(R=1\) (完全准确) | 0.82 | 0.25 | 1.15 | 0.00 |
| 平均每作业抢占次数 | \(R=16\) (中度误差) | 1.65 | 1.10 | 3.20 | 0.00 |
| 平均每作业抢占次数 | \(R=256\) (重度误差) | 2.10 | 1.85 | 5.80 | 0.00 |
| 平均每作业抢占次数 | \(R=1024\) (极大偏差) | 2.45 | 2.60 | 7.90 | 0.00 |
消融实验¶
实验分析了在固定误差 \(R=256\)、\(\delta=1\)、\(\beta=0.7\) 条件下，系统异构程度（特殊作业与专用机器占比由 0% 扩展至 50%）对不同机制竞争比的影响（对应原文 Table 1 与消融设置）。
| 异构作业比例 | Blind (纯贪心不可迁移) | Doubling (倍增重派) | SNAP (纯周期化 PF) | Hybrid SNAP (c=6) | Hybrid SNAP (c=8) | 说明与机理分析 |
|---|---|---|---|---|---|---|
| 0% (完全同质机) | 1.3076 | 1.6983 | 1.4943 | 1.5221 | 1.3879 | 同质机下无迁移贪心即可自发实现均摊负载 |
| 10% 特殊作业 | 1.7923 | 1.5098 | 1.3562 | 1.3954 | 1.3994 | 引入异构瓶颈后 Blind 性能骤降，SNAP 显现理论优势 |
| 20% 特殊作业 | 1.8279 | 1.5047 | 1.3590 | 1.4255 | 1.3813 | SNAP 保持最优稳健性，Hybrid SNAP 性能同步领跑 |
| 30% 特殊作业 | 1.6468 | 1.5375 | 1.4599 | 1.2963 | 1.3924 | 大里程碑预热过滤极大地规避了初期无谓抢占 |
| 40% 特殊作业 | 1.6101 | 1.5438 | 1.5124 | 1.3854 | 1.3005 | 混合策略兼顾盲目调度初期的低延迟与长尾任务重平衡 |
| 50% (高度异质) | 1.5750 | 1.6060 | 1.5315 | 1.3554 | 1.3927 | 异构加剧时纯启发式显著落后于带保证的 PF 机制 |
关键发现¶
- 预测误差下的稳定性悬殊：Blind 策略在预测极其精确（\(R=1\)）时因完全消除抢占开销而取得最低延迟（1.21），但随着预测偏差 \(R\) 攀升至 1000 以上，其缺乏自适应调整能力导致长作业严重阻塞队列，竞争比急剧崩溃；而 SNAP 凭借比例公平检查点机制，在 \(R\) 跨越 3 个数量级时竞争比始终稳定在 1.36-1.48 之间。
- 抢占控制的对数级收敛：Doubling 策略每超时一次便重置并重派任务，抢占次数随误差 \(R\) 呈线性阶剧增（从 1.15 次暴增至接近 8 次）；而 SNAP 将单个作业平均抢占次数死死锚定在 0.8-2.5 次范围，充分验证了理论上对数级上界的优越性。
- 混合策略的工程 Pareto 最优：Hybrid SNAP 在初期设定大倍数阈值 \(c(1+\delta)^i \hat{p}_j\)（采用 Blind 逻辑避免浅层切换），对多轮未完成的长尾作业迁移至 SNAP 进行全局平衡，在极低抢占（中等误差下仅 1.1 次）的同时取得了全局最低的延迟，实现了两类范式的帕累托改进。
亮点与洞察¶
- 从无限微调走向离线宏观执行块：传统在线算法（如 Round-Robin 或连续时间 PF）因依赖极微时间片而在工程上不可落地。SNAP 巧妙地将“在线连续决策”解耦为“离散检查点标定 + 批量离线无抢占舍入”，将算法每次迭代的执行时长放大至 \(4 l_k\)，从数学构架上彻底根除了高频抖动。
- 欠估计与过估计的非对称处理哲学：指出过估计对调度的破坏力远甚于欠估计，提出通过尺度缩放主动人为诱导欠估计，再以全局统计量 \(g\) 进行单向重置，展现了以宏观标量信息代偿微观细粒度不确定性的优雅设计思路。
- 拓展至可延展（Malleable）作业的多面体框架：在缺少非相关机超可加性定理的更宽泛 Polytope Scheduling 问题中，创造性定义了 \(\beta\)-robust PSP 对抗模型并通过对偶拟合（Dual Fitting）直接改进 PF 证明，为异构集群中任务并发多核伸缩的低抢占调度提供了坚实的数学工具。
局限与展望¶
- 理论常数因子偏保守：虽然证明了 \(O(1)\) 常数竞争比，但目前定理给出的理论界为 \(14.48(1+\varepsilon)\)，与实际仿真中测得的 1.3-1.5 存在一定间隙，后续分析可尝试利用更紧致的凸规划对偶界加以压缩。
- 全局参数 \(g\) 与 \(R\) 的自适应估计依赖：两阶段弱强制欠估计依赖于对过估计任务数上限 \(g\) 的预估，若实际运行环境中突发非平稳漂移导致 \(g\) 被大幅低估，状态重置点将被推迟，从而在短期内承受一定的延迟恶化。
相关工作与启发¶
- vs Motwani et al. (FOCS 1993 / TCS 1994, MLF)：经典 MLF 采用自底向上的多级反馈队列抑制抢占，但在完全无预测时对任意长度作业均需从第 0 级队列逐级下沉；本文提出的 PMLF 直接利用预测值将任务路由至其对应等级队列，使准确预测下的抢占次数从 \(O(\log p_j)\) 骤降至 \(O(1)\)。
- vs Purohit et al. (NeurIPS 2018) & Im et al. (SPAA 2021 / TOPC 2023)：先前的学习增强调度工作多聚焦于单机或同质机，且均假定调度器采用 Round-Robin 等允许瞬时无限抢占的理想模型；本文首次将学习增强引入异构非相关机与多面体调度，且将抢占复杂度作为一级优化目标。
- vs Anand et al. (SODA 2012, 即时分派无迁移)：Anand 等人的贪心分派在准确预测下具备优秀性能，但在面对大尺度预测误差（如数据库 Join 估计偏差千倍）时缺乏容错能力；SNAP 证明了引入受控的有界抢占与迁移是抵御预测灾难的关键防线。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立兼顾完备时间与抢占开销的学习增强异构调度理论体系
- 实验充分度: ⭐⭐⭐⭐☆ 仿真实验全面覆盖异构度、误差跨度与超参数消融，若有真实生产集群 Trace 验证则更佳
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰严谨，从单机多级反馈到异构多机凸松弛层层递进
- 价值: ⭐⭐⭐⭐⭐ 弥合了分布式系统高昂上下文切换成本与理论在线调度研究之间的鸿沟