💻 computer science

TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes

TEMPO 引入了一种感知完成时间（makespan-aware）的专家并行负载均衡调度器，该调度器对跨越内存受限与计算受限机制的非线性专家执行时间进行建模，以动态优化 Token 分布，在传统基于线性计数的方法失效的混合机制场景中，实现了高达 15.5% 的吞吐量提升和显著的延迟降低。

原作者： Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

发布于 2026-08-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在为一座永不眠城的超大规模、高速运转的披萨外送业务进行管理。你拥有一支完全相同的配送员队伍（即 GPU），以及一个拥有数百名不同专业厨师（即 AI 模型中的“专家”）的中央厨房。每当有客户订购披萨时，系统必须决定由哪些厨师来制作这块饼，以及由哪位司机来运送成品。在人工智能的世界里，特别是在一种被称为“混合专家”（Mixture-of-Experts，简称 MoE）的模型中，情况正是如此。这些模型就像是由数千个更小的、专门化的子大脑组成的巨型大脑。当 AI 进行思考时，它并不会同时动用整个大脑，而是挑选出几个特定的专家来处理这项任务。

巨大的挑战在于如何保持整个团队的运行速度一致。如果一名司机因为接到了一个极其复杂的大订单而陷入停滞，而其他所有人都处于闲置状态，那么整个配送过程都会被延误。多年来，平衡工作负载的标准规则一直很简单：“只需将订单数量均匀分配即可。”如果你有 100 个订单，就给 10 名司机每人分 10 个。这看起来很合乎逻辑，就像是平均分配一堆苹果。但如果有些苹果是沉重的石头，而另一些是轻盈的羽毛呢？或者如果厨房有一条规定，无论你做多少个披萨，挑选一位新厨师所花费的时间都是固定的。旧有的规则假设时间总是与订单的数量直接相关的。但这个研究提出了一个疑问：如果这个假设是错误的呢？

来自 KlingAI 的这些研究人员发现，旧有的“计算订单数量”规则实际上是一个陷阱。他们发现，在现代 AI 硬件中，处理一个专家的耗时不仅仅取决于它看到了多少个 Token（单词或数据块）。它是一个具有两面性的“怪兽”。有时，时间主要消耗在从内存库中加载专家的“食谱”（权重）这一纯粹的体力活上，无论订单量多小，这部分时间都是固定的。而另一些时候，一旦食谱加载完成，时间就会随着订单数量的增加而线性增长。旧的方法只关注订单数量，从而忽略了加载食谱的隐藏成本。他们试图通过计数来平衡一堆羽毛和石头，而不是通过称重。

为了解决这个问题，团队构建了一个新的调度器——TEMPO（基于时间建模的专家并行优化）。TEMPO 不仅仅是计数 Token，它更像是一个理解厨房物理规律的智能交通控制器。它使用了一种特殊的“成本模型”，精确测量加载专家食谱所需的时间以及烹饪披萨所需的时间。它意识到，如果你有一个“冷门”专家（即一段时间没被使用过的专家），将其微小的订单拆分给两个驱动程序将是一场灾难，因为你必须支付两次“加载费”。但如果你有一个拥有海量订单的“热门”专家，拆分它则是完全可以接受的。

论文表明，TEMPO 不仅仅是在靠直觉猜测；它能在毫秒级时间内为每一批次的请求计算出完美的平衡点。他们在真实的 AI 模型上进行了测试，发现旧方法往往会导致 15% 的速度下降，或者导致排队序列中最后几位客户面临显著的延迟。然而，TEMPO 能让排队流程平稳运行。这就像是从“每个人得到相同数量的苹果”这一规则，转变为“每个人承担相同的工作量”这一规则，同时也考虑到了有些苹果很重，而有些厨师醒来很慢。

研究人员非常谨慎地展示了这种新方法在何处有效，以及在何处无效。他们证明，如果“热门”专家过于密集，以至于系统仅仅是被庞大的数据量所淹没（即进入“计算受限”阶段），那么旧的 Token 计数法其实也是可以接受的。但在现实世界中，当某些专家正忙碌而另一些专家正在休息，且“加载费”很高时，TEMPO 的优势便会显现出来。他们甚至绘制了一张“相图”（Phase Diagram），这就像是 AI 交通的“天气预报图”，能够准确预测何时新方法能节省时间，以及何时旧方法已经足够好。

最终，这篇论文不仅仅是关于一种更快的算法；它是关于我们如何思考 AI 任务平衡方式的变革。它告诉我们，在现代 AI 这种复杂且高速运转的世界里，你不能仅仅是计数。你必须理解移动数据的隐藏成本以及工作的具体形态。通过衡量完成工作的实际时间，而非仅仅计数项目，TEMPO 让 AI 模型变得更快、更高效，并能应对未来的巨大需求。它将一个混乱的厨房变成了一台运转良好的精密机器，确保没有任何一名司机会在披萨放在保温灯下等待时，还只能干等着。

技术摘要：TEMPO – 感知最大完成时间（Makespan）的专家并行负载均衡

1. 问题定义

在混合专家模型（MoE）推理服务中，每一层的延迟由**最大完成时间（makespan）**决定（即所有 GPU 中耗时最长的那个），这是由于每一层结束时的同步点导致的。目前的生产级调度器（如 EPLB、LPLB、UltraEP、METRO）试图通过优化代理指标来平衡负载：要么是每个 GPU 的 Token 数量，要么是每个 GPU 激活的专家数量。这些代理指标依赖于隐性的线性假设——即专家执行时间与 Token 数量或专家数量成线性比例关系。

然而，对数据中心 GPU（特别是使用 DeepGEMM fp8 分组 GEMM 核函数的实验）的测量表明，专家执行时间是非线性的，并遵循双阶段结构：

内存受限（平坦）阶段： 在每个专家的 Token 数低于阈值 $n^* \approx 156\text{--}168$ 时，成本主要由从高带宽内存（HBM）中流式传输专家权重决定。在此阶段，无论 Token 数量如何，每个激活的专家副本的成本是恒定的。
计算受限（线性）阶段： 当超过 $n^*$ 时，成本随 Token 数量线性增加。然而，由于分组 GEMM 实现会将 Token 向上取整到 128 个 Token 的 M-tile，将一个专家拆分到多个副本会引入“填充计算（padded compute）”，使得成本呈现出一种简单的 Token 计数无法捕捉的非线性特征。

因此，现实世界的解码批次通常包含一个混合阶段：“热”专家拥有大量 Token（线性阶段）与“冷”专家拥有少量 Token（平坦阶段）并存。现有的代理策略之所以失效，是因为 Token 平衡策略会碎片化冷专家（支付隐藏的激活底噪），而激活平衡策略则会使热副本过载。没有任何单一的固定代理能在所有运行点上都是最优的。

2. 方法论

成本建模

作者将每个专家的执行时间 $t$ 公式化为一个最大仿射函数（max-affine function）：
$t = \max(a + bG, c + \beta N)$
其中 $G$ 是激活的专家副本数， $N$ 是 Token 数量。

$b$ (激活底噪)： 为增加一个额外的副本而流式传输权重的成本（内存受限）。
$\beta$ (Token 斜率)： 计算受限阶段中每个 Token 的成本。
Tile 感知： 对于预填充（prefill）或大批次场景，一个次级参数捕捉了 128-token 瓦片化的“阶梯效应”，将模型精细化为 $t = \max(a+bG+b_2(T-G), c+\beta N)$ 。

该模型通过在已部署的核函数上进行十分钟的黑盒微基准测试进行校准，测量了在 $(G, N)$ 网格下的实际墙钟时间。

问题形式化

调度问题被形式化为一个**带固定费用的最大完成时间最小化（fixed-charge makespan minimization）**问题。作者证明，即使在两个 GPU 且全复制的情况下，该问题也是 NP-hard 的，因为它需要同时平衡两个相互竞争的约束（激活计数 vs. Token 计数）。然而，在退化极限下（纯 Token 平衡或纯激活平衡），该问题是多项式时间的。

TEMPO 算法

TEMPO（时间建模的专家并行优化）是一个能在毫秒级解决该 makespan 问题的调度器，且运行在关键路径之外。其求解器 tempo fast 采用四个阶段：

成本感知贪婪种子生成（Cost-Aware Greedy Seeding）： 将完整的专家放置在边际成本最低的副本上，避免碎片化冷专家。
激活重平衡（Activation Rebalancing）： 使用增广链在平坦阶段重新平衡专家数量（在此时 Token 移动是无效的）。
瓶颈局部搜索（Bottleneck Local Search）： 执行部分 Token 迁移，以减少线性阶段中的 makespan。
带有切换容差的集成（Ensemble with Switching Tolerance）： 将当前解与 Token-LP（线性规划）基准和轮询（Round-Robin）启发式算法进行评分。只有当新解比旧解好 >1% 时才会进行切换，从而确保稳定性，并继承简单算法的理论保证。

系统集成

TEMPO 集成到 SGLang 中，专注于零开销的关键路径：

图内（In-Graph）： 单个融合 CUDA 核函数处理概率调度和计数收集，消除了以往 LP 求解器所需的逐层集合通信（collectives）。
进程外（Out-of-Process）： 求解器在独立的进程中运行，避免了 GIL 争用，并确保调度决策不会阻塞推理图。
拓扑感知： 对于多节点设置，采用两阶段拆分，确保 Token 首先路由到同一节点内的副本，在不改变核心求解器的情况下最小化节点间流量。

3. 关键结果

理论与仿真

相图（Phase Diagram）： 校准后的相图表明，基于批次大小和专家偏斜，最优固定策略会在激活平衡（内存受限）和 Token 平衡（计算受限）之间发生翻转。TEMPO 能够追踪整个映射图中的最优策略。
近似保证： 在全复制条件下，TEMPO 提供了一个加性近似保证 $OPT + \max(b, \beta n_{max})$ 。
仿真收益： 在仿真环境中，在混合阶段场景下（特别是针对 EP32–64 的外推），TEMPO 比最佳固定基准提升了高达 15.5%。

实证评估（测试平台 A & B）

微基准测试： 在 8-GPU 测试平台 A 上，TEMPO 在每个评估的网格点上都保持在最佳固定基准的 1% 以内，并在各阶段混合时领先高达 15.5%。
端到端服务（Qwen3-235B）：
- 在长上下文和解码密集型流量下，TEMPO 将吞吐量提高了 4–6%，并将 p99 token 间延迟降低了 ~15.6%。
- 在 2 节点 EP16 设置下，结合拓扑感知拆分，收益达到 4–7%。
- 至关重要的是，论文指出 TEMPO 与 SGLang 已交付的 LPLB 之间的差距很大程度上是架构性的（即移除了图内集合通信）；当 LPLB 被移植到相同架构时，TEMPO 的剩余收益主要体现在计算受限点上的稳定性。
端到端服务（DeepSeek-V3）： 在通信占主导且每个 GPU 上的专家较小的模型（处于“非获益区”）上，TEMPO 仅返回机制成本，表现与静态放置持平。这证实了论文的观点：其收益是条件性的。
陈旧性与放置： 系统对放置陈旧性（高达 200ms 的漂移）具有鲁棒性。但是，如果放置层显著陈旧（热专家被移动到了冷副本），仅靠调度无法恢复吞吐量；只有放置层可以修复均值，而调度负责修复延迟尾部。

4. 重要性与主张

该论文的主要主张并非提供普遍的性能提升，而是提出了一个预测何时进行基于时间调度的相图。

“获益区”（The Win Region）： 自适应调度仅在以下情况产生显著收益：
1. 模型具有大型专家（高激活底噪 $b$ ）。
2. 批次处于混合阶段（包含热专家和冷专家）。
3. 放置状态足够陈旧，以至于导致了不平衡，但又不至于陈旧到只能通过权重迁移来修复。
4. 专家计算在单步时间内占有显著份额（未被通信主导）。
方法论转向： 论文认为“平衡时间而非 Token”是 MoE 推理的原则性方法。它证明了 Token 计数代理在内存受限阶段是系统性错误的，且必须通过校准成本模型来应对内存与计算瓶颈的交互。
实用性： 该工作提供了一个可部署的解决方案（TEMPO），能够无缝集成到现有服务栈（SGLang）中，且开销极小，证明了复杂的 makespan 优化可以在不阻塞推理的情况下在毫秒级内完成。

作者明确指出，对于小型专家形状或通信主导的模型，自适应调度相比静态放置并无优势，且系统会正确降级为持平状态而非产生惩罚。其贡献在于映射了这些条件以及用于导航这些条件的算法。