跳到主要内容

Scheduler-as-workload

continuous batching / 请求分布 / PD 分离作为 perf model 输入,排队论与请求级 DES 作为分析工具

核心要点:

  • 软件调度(continuous batching、PD 分离、请求队列)是被建模对象,不是建模方法——在 perf model 里作为 workload 输入参数化
  • workload spec 三件套:请求到达分布、输入/输出长度分布、SLO 目标
  • continuous batching 让 batch 形状在每个 decode step 动态变化,perf model 必须建状态机而非用静态 batch 近似
  • 端到端指标分三层算:L1 算子时长(02 篇)→ L2 单请求 TTFT/TPOT → L3 系统吞吐 / P99 / SLO 命中率
  • L3 两种范式:排队论闭式(秒级,平均态)vs 请求级 DES(分钟级,尾分布)
  • PD 分离引入 KV 跨实例传输事件,作为新的关键路径节点

名词定义​

名词定义
Workload spec驱动 perf model 的请求侧规范:到达过程 + 长度分布 + SLO
Continuous batching每 decode step 动态加入 / 移出请求的调度,Orca 提出
Chunked prefill把长 prefill 切成 chunk 与 decode 共 step 执行,DeepSpeed-FastGen / Sarathi 提出
PD 分离prefill 与 decode 在不同实例,经网络传 KV
TTFT / TPOTTime To First Token / Time Per Output Token
Goodput满足 SLO 的吞吐(不是总吞吐)
请求级 DES以一次请求为最小事件的离散事件仿真,Vidur 上层属此

本篇范围​

软件调度的系统机制(continuous batching 算法、PagedAttention 块管理、PD 分离设计、cache-aware 路由)已有完整调研,本篇不重复:

系统机制主题已有调研位置
PagedAttention 与 KV 管理3.7 推理侧 — KV 管理
Continuous batching / chunked prefill3.8 推理侧 — 调度优化
PD 分离原理9.2 Prefill/Decode 分离原理
DistServe / Mooncake / SGLang-PD / NVIDIA Dynamointerconnect/09-推理服务化通信/ 03-06 各篇
KV 传输瓶颈9.7 KV cache 跨节点传输瓶颈
Cache-aware 调度9.9 Cache-aware 调度

本篇独占的 perf model 视角增量:

  • 软件调度如何参数化为 workload 输入(到达、长度、SLO)
  • continuous batching 在 perf model 里的状态机表达
  • 三层指标计算路径与各自负责的 metric
  • 排队论闭式 vs 请求级 DES 取舍
  • PD 分离在 perf model 里作为新关键路径节点

Scheduler 在 perf model 里的角色​

关键判断:Scheduler 是被建模对象,不是建模方法。 它的系统设计(批策略、队列、路由)决定 workload 形态,perf model 把它作为输入参数化,不是作为算法实现。

这与 compute / memory / interconnect 三个资源域不同——后三者是物理资源,perf model 直接建它们的时序;scheduler 是软件行为,perf model 建的是"在某种 scheduler 策略下,资源被怎样占用"。

两种角色细分:

角色含义在 perf model 里出现
Scheduler-as-workload调度策略 + 请求分布 → 驱动 compute/memory/interconnect 的输入 trace输入侧
Scheduler-as-analysis排队论 / 请求级 DES → 把 L2 单请求时长 + 调度策略 → L3 服务指标分析工具

@tbl-ipm-s-roles Scheduler 在 perf model 里的两种角色

Workload Spec 三件套​

驱动 perf model 的请求侧规范由三部分组成:

请求到达过程​

  • Poisson 到达($\lambda$ 请求 / 秒):最简单,假设独立同分布。适合大规模服务、负载稳定场景
  • Trace replay:用生产 trace(时间戳序列)直接回放,捕获真实突发性
  • Bursty / on-off:开关切换的到达率,建模白天 / 夜间或活动期

典型来源:Vidur 论文用 Microsoft Azure LLM trace(arxiv 2310.18547),Splitwise 也基于此 trace。学术 perf model 默认 Poisson + 高斯长度,部署评估必须用生产 trace。

输入 / 输出长度分布​

  • 输入长度:决定 prefill 工作量,影响 TTFT
  • 输出长度:决定 decode 步数,影响 TPOT × N
  • 两者通常对数正态(log-normal)或重尾分布,均值不代表 P99

对建模的关键:用平均长度估算 TTFT/TPOT 会严重低估尾延迟。perf model 必须分别建均值与分布形状。

SLO 目标​

  • TTFT P99 上限(典型 500ms-2s)
  • TPOT 均值或 P99 上限(典型 50-200ms / token)
  • Goodput:满足 SLO 的吞吐(不是总吞吐)

Goodput 是 DistServe 论文[1] 提出的关键概念——传统优化总吞吐会牺牲尾延迟,导致 SLO 命中率下降,反而损失"有效收入"。perf model 必须以 goodput 为优化目标,不是 raw throughput。

Continuous Batching 的状态机表达​

静态 batching 假设一批请求一起开始、一起结束,$b$ 固定。真实系统 $b$ 在每个 decode step 都变化——已完成的请求立刻退出、新到达的请求立刻加入。算法机制见 3.8 推理侧 — 调度优化,本节讲怎么把它建进 perf model。

状态机定义​

每个 decode step 是一个状态转换:

  • 状态:当前活跃请求集合 $\mathcal{R}_t = \{r_1, r_2, \ldots\}$,每个请求有 $(s_i, p_i)$——已生成 token 数 $s_i$ 与剩余预算 $p_i$
  • 输入:新到达请求集合(从到达过程采样)
  • 输出:本 step 的算子形状(batch GEMM 的 $b$ 维 = $|\mathcal{R}_t|$,attention 的序列维异构)

对算子时长的影响​

continuous batching 让每个 step 的算子参数动态:

  • GEMM 的 $b$ 维:每 step 不同,$T_{\text{gemm}}(b, h, h')$ 必须按 $b$ 查表(Vidur 用 RF 回归)
  • Attention 的序列维:每个请求 KV 长度不同,attention kernel 必须 capture 异构(各请求 $s_i$ 独立)
  • KV 字节随 step 演化:每多生成一个 token,KV 增加一行,带宽需求线性涨

简化建模常见错误:用初始 batch 大小或固定平均 batch 算 TPOT,会低估长序列尾段的 TPOT(因为 step 末尾 batch 缩小、KV 累积大,实际更慢)。

Chunked prefill 的状态机扩展​

把长 prefill 切成 chunk 与 decode 共 step 执行(Sarathi-Serve / DeepSpeed-FastGen):一个 step 内同时有 prefill chunk 与 decode token。对 perf model 的影响:

  • 算子形状混合(prefill chunk 是 GEMM、decode 是 GEMV),roofline 取最长边
  • 减少 prefill 对 decode 的 head-of-line blocking,改善 TPOT 尾分布
  • TTFT 略变长(prefill 被切片)——这是工程取舍,perf model 必须能 capture

三层指标计算路径​

端到端指标分三层算,每层消费下层的产出:

L1 算子时长 (02/03/04 篇负责)
   ↓ 查表 / 标定
L2 单请求 TTFT / TPOT (本篇 L2 状态机)
   ↓ 请求级仿真 / 排队论
L3 系统吞吐 / P99 / SLO 命中率 (本篇 L3 分析工具)

L2 单请求 TTFT​

$$\begin{equation} \text{TTFT} = T_{\text{queue}} + T_{\text{prefill}}(s_{\text{in}}) \label{eq:ipm-s-ttft} \end{equation}$$

$T_{\text{prefill}}$ 沿关键路径累加 prefill 算子时长(每算子时长查 L1 标定表),$T_{\text{queue}}$ 是请求在服务队列里的等待时间(由 L3 给出)。

L2 单请求 TPOT​

$$\begin{equation} \text{TPOT} = T_{\text{decode\_step}}(b, \{s_i\}_{i\in\mathcal{R}}) \label{eq:ipm-s-tpot} \end{equation}$$

一个 decode step 的关键路径时长,显式依赖当前 batch composition——$b$ 是当前批,$\{s_i\}$ 是各请求当前 KV 长度。L2 状态机推进每 step 时,根据 L3 给的 batch composition 更新 $T_{\text{decode\_step}}$。

关键结论:TTFT 对输入序列长度敏感,TPOT 对批量大小和 KV cache 大小敏感。两者有独立的调优空间,不能合并成单一指标。

PD 分离的 TTFT 改写​

PD 分离把 prefill 与 decode 放不同实例,prefill 产出的 KV cache 必须通过网络传给 decode 实例。传输延迟:

$$\begin{equation} T_{\text{KV transfer}} = \alpha + \frac{M_{kv}}{B_{\text{inter}}} \label{eq:ipm-s-kv-transfer} \end{equation}$$

其中 $M_{kv}$ 是 KV cache 字节数(见 03-Memory 公式 $\href{/knowledge/推理性能建模/访存与内存建模}{\text{(8.3)}}$),$B_{\text{inter}}$ 是 prefill-decode 实例之间的互联带宽。长上下文时 $M_{kv}$ 大,KV 传输可能成为新瓶颈,机制见 9.7 KV cache 跨节点传输瓶颈。

PD 分离下 TTFT:

$$\begin{equation} \text{TTFT}_{\text{PD}} = T_{\text{queue,prefill}} + T_{\text{prefill}} + T_{\text{KV transfer}} + T_{\text{queue,decode}} \label{eq:ipm-s-ttft-pd} \end{equation}$$

两个独立队列——prefill 队列与 decode 队列各自排队,L3 必须分别建。Mooncake / DistServe / SGLang-PD 的具体调度策略见 9.4 Mooncake 等。

L3 系统吞吐​

两种范式,精度速度取舍:

排队论闭式​

$$\begin{equation} \text{Throughput} \approx \min\left(\lambda_{\text{arrival}},\; \frac{1}{T_{\text{service per request}}}\right) \label{eq:ipm-s-queueing} \end{equation}$$

$T_{\text{service}}$ 来自 L2 的 $\text{TTFT} + \text{TPOT}\times N_{\text{tokens}}$。M/M/c 类闭式可给平均等待时间,适合秒级 DSE 扫描,但无法给 P99——因为闭式建立在指数到达 / 指数服务的强假设上,LLM 实际服务时长重尾,闭式严重低估尾延迟。

请求级 DES​

按真实到达时间戳模拟每个请求进队 → batch → 执行 → 出队,每 step 执行时长查 L2(L2 又查 L1)。输出吞吐 / P99 / SLO 命中率。

代表工具:Vidur 的请求级仿真器[2]——它是少见的把 L1+L2+L3 三层都做了的框架。论文报告:静态 workload P95 误差 ≤ 3.33%,高负载动态场景 < 5%,全场景 < 9%(verbatim)。

取舍表​

范式速度精度能算 P99适用
排队论闭式秒级平均态 ±10-30%否容量规划初筛
请求级 DES分钟级全分布 < 9%(Vidur)是SLO 评估、PD 选型

@tbl-ipm-s-l3-tradeoff L3 服务系统两种建模范式取舍

L3 关键指标:P99 与 SLO 命中率​

只有 L3 请求级 DES 能算——尾延迟来自请求间相互干扰(谁挤了谁的 batch),L1/L2 单看一个请求看不见。

P99 延迟:取请求集合延迟分布的 99 分位。重尾的根因:

  • continuous batching 下,新请求加入时已有请求 KV 长 → 长 KV attention 拖慢整 batch
  • prefill 阻塞短 decode(无 chunked prefill 时):一个长 prefill 占满 step,所有 decode token 等
  • KV cache 容量墙触发 → 请求被驱逐 / 重算,产生超长延迟

SLO 命中率:定义在请求级。perf model 输出 $(\text{TTFT}_i, \text{TPOT}_i)$ 对每个请求 $i$,然后:

$$\begin{equation} \text{SLO hit rate} = \frac{|\{i : \text{TTFT}_i \le \tau_{\text{TTFT}} \land \text{TPOT}_i \le \tau_{\text{TPOT}}\}|}{N_{\text{total}}} \label{eq:ipm-s-slo-rate} \end{equation}$$

Goodput = SLO hit rate × arrival rate × tokens per request。

业界工具的三层覆盖对比​

工具L1 算子L2 单请求L3 服务系统备注
LLM-Viewerroofline✗✗仅 L1
GenZroofline + 双 η✓ TTFT/TPOT✗L1+L2
Calculonroofline + 分段 η✓ training step✗L1+L2,training
ASTRA-simbackend 可换✓ event-driven部分L1+L2
VidurRF 回归 trace✓ continuous batching✓ 请求级 DES + Azure traceL1+L2+L3 三层
Splitwiseprofile✓ PD 各 stage✓ 集群模拟L1+L2+L3,聚焦 PD
DistServeanalytical + profile✓ goodput-oriented✓ goodput 优化L2+L3,goodput 范式

@tbl-ipm-s-tools-coverage 主流 perf model 工具的三层覆盖对比

关键观察:多数解析工具只覆盖 L1+L2,静态 batch 近似 L3。Vidur 是唯一明确覆盖三层并显式模拟 continuous batching 状态机的开源工具——这是它在请求级评估上的核心价值。

升降档判据(scheduler 层)​

  • 回答"哪个并行配置吞吐高":L1+L2 + 平均 batch 近似够用,L3 用排队论闭式
  • 回答"P99 / SLO 命中率":必须 L3 请求级 DES,无替代
  • 回答"continuous batching 调度策略选哪个":必须 L3 + 状态机,Vidur 类
  • 回答"PD 分离 ratio 怎么定":必须 L3 双队列 + KV 传输节点,Splitwise / DistServe 类

G5 落地视角(scheduler 层)​

G5 是 cycle-approx 档,不涉及 L3——请求级 DES 跑不动 cycle 级硬件。G5 的角色是 L1 标定提供方:把"一个 step 多少 cycle"作为 L2 输入,L3 再用 L2 输出做请求级仿真。

具体接口:G5 跑代表性 batch size × KV length 配置 step,产出 $T_{\text{step}}(b, \{s_i\})$ 标定表,喂给 Vidur 类 L3 仿真器。这与 02 Compute 篇的"cycle-approx 反向喂养 analytical"是同一模式。

Takeaway​

知识点核心结论
Scheduler 角色被建模对象 + 分析工具,作为 workload 输入参数化,不是直接建系统
Workload spec 三件套到达分布 + 输入输出长度 + SLO
Continuous batching状态机推进每 step,batch 形状动态变化,静态 batch 近似会低估尾 TPOT
三层指标路径L1 算子 → L2 TTFT/TPOT → L3 吞吐/P99/SLO
L3 两种范式排队论闭式秒级算平均,请求级 DES 分钟级算 P99
PD 分离引入 $T_{\text{KV transfer}}$ + 双队列,新关键路径节点
三层都做的工具Vidur(L1+L2+L3),Splitwise/DistServe(PD 聚焦)
G5 在 L3 不直接出现跑不动,作为 L1 标定喂给 L3 仿真器

开放问题​

  • 异构 GPU 集群(不同代芯片混部)的 batch 调度策略对 perf model 的反作用——见 07 多目标与异构篇待写
  • Cache-aware 路由(prefix cache 命中)如何在 perf model 里建模——机制见 9.9 Cache-aware 调度,建模视角待补
  • Speculative decoding 改变 decode 步数结构,L2 的 TPOT 公式需扩展——见 11 投机解码篇待写

参考资料​

  1. Zhong et al., DistServe: Disaggregating Prefill and Decoding for Goodput-Optimized Large Language Model Serving, OSDI 2024. https://arxiv.org/abs/2401.09670
  2. Agrawal et al., Vidur: A Large-Scale Simulation Framework for LLM Inference, MLSys 2024. https://arxiv.org/abs/2405.05465

延伸阅读​