# 第 19 章 推理系统与性能工程


> 本章把"模型能跑"推进到"模型跑得快"。核心只有一个问题：时间花在算力上，还是花在把数据搬进搬出计算单元的路上。

## 学习目标

读完本章，你应当能够：

1. 复述 GPU 存储层级的容量与带宽数量级，解释"片上 / 片外"为何差一个数量级，并说明什么是显存墙（memory wall）。
2. 用 Roofline 模型判断一个算子处于 `compute-bound` 还是 `memory-bound` 区间，并估算其可达性能上限。
3. 推导 prefill 与 decode 的算术强度，说明两者瓶颈为何不同，并由此导出 batching 这一优化方向。
4. 完整推导 KV Cache 的单 token 显存公式 `2 × L × h × 2` 字节，并估算总显存。
5. 解释算子融合（operator fusion）的收益来源与收益边界，分析 `ResidualAdd + RMSNorm` 与 GEMM Epilogue 两类融合。
6. 推导 online softmax 的递推公式，说明 FlashAttention 为什么是精确算法而非近似。
7. 辨析静态 batching 与 continuous batching，说明 PagedAttention 的虚拟内存类比。
8. 用 TTFT、TPOT、吞吐、QPS 四类指标描述一个推理服务的性能。

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| GEMM / GEMV 的运算量（FLOPs 计数） | 本章 19.2.2 |
| 矩阵乘法的维度账本与权重形状 | 第 15 章（注意力与多头维度） |
| Softmax 的数值稳定写法（减最大值） | 第 5 章（数值计算基础） |
| RMSNorm 的定义与残差连接 | 第 13 章（归一化层与残差） |
| 自回归解码与上下文因果掩码 | 第 15 章、第 18 章 |
| `O(·)` 记号与复杂度主导项 | 第 22 章 |
| 线性量化的基本公式（本章只需概念） | 第 20 章 |

## 19.1 GPU 存储层级：为什么"数据在哪"比"算得多快"更重要

### 19.1.1 存储层级的容量与带宽

冯·诺依曼结构里，计算单元和存储单元是分离的：要把数据搬过来才能算。问题在于，这个"搬"的速度几十年来的增长远慢于"算"的速度。结果就是今天的 GPU 不是算不动，而是**常常在等数据**。

现代 GPU 的存储层级如下（数量级以 A100/H100 这一代为例，具体数值随型号变化，但层级之间的**比例关系**是稳定的）：

| 层级 | 典型容量 | 典型聚合带宽 | 延迟数量级 | 谁来管理 |
|---|---|---|---|---|
| 寄存器（register file） | 每 SM 256 KB | 约 20 TB/s | 数周期 | 编译器 / 程序员 |
| 共享内存 SMEM + L1 | 每 SM 192~256 KB | 约 19 TB/s | 约 30 周期 | 程序显式管理 |
| L2 缓存 | 40~50 MB | 约 5~8 TB/s | 约 200 周期 | 硬件自动 |
| HBM（显存） | 40~80 GB | 1.5~3.5 TB/s | 约 400~800 周期 | 硬件自动 |

从这张表可以读出两个事实：

1. **容量与带宽反向变化**：越快的地方越小。寄存器只有几百 KB，显存有几十 GB，相差约 5 个数量级。
2. **相邻层级之间带宽差约一个数量级**：SMEM 到寄存器的带宽是 HBM 的 5~10 倍。这就是"片上（on-chip）"与"片外（off-chip）"的分界线——**SMEM / L1 / 寄存器是片上，L2 与 HBM 是片外**。

> [!IMPORTANT]
> SMEM 与 L1 在物理上是同一块 SRAM，由硬件按配置划分比例。所谓"把数据放进 SMEM"，本质是**把一次 HBM 往返换成了片上重复读写**。FlashAttention、GEMM tiling 全部建立在这条性质上。

### 19.1.2 显存墙

把"算力增长"和"带宽增长"画成两条曲线，会看到一个越来越大的裂口：算力（FLOPS）每两年多增长约 3 倍，而 HBM 带宽每两年只增长约 1.5~1.6 倍。这个裂口叫**显存墙（memory wall）**。

它的直接后果是：**一个算子的实际性能，往往不由它的 FLOPs 决定，而由它必须搬运的字节数决定**。为了量化这件事，我们需要一个统一的口径——算术强度。

## 19.2 Roofline 模型：一个判断瓶颈的坐标系

### 19.2.1 定义与拐点

**算术强度（arithmetic intensity, AI）** 定义为单位访存字节所对应的浮点运算次数：

`AI = FLOPs / Bytes`（单位：FLOP/Byte）

Roofline 模型的纵轴是可达算力（FLOP/s），横轴是算术强度（对数坐标）。可达到的性能受两条上界约束：

```
可达性能 P ≤ min( 峰值算力 P_peak , 算术强度 I × 内存带宽 BW )
```

把两条上界画出来，会得到一个"屋顶"形状：

```
性能 (FLOP/s)
  │
  │            ┌────────────────────────  P_peak（算力屋顶）
  │           ╱
  │         ╱     ← 内存带宽屋顶： P = I × BW
  │       ╱
  │     ╱
  │   ╱
  └──┴──────────────────────────────────→ 算术强度 I (FLOP/Byte)
      I*
   拐点
```

两条线的交点叫**拐点（ridge point）**：

`I* = P_peak / BW`

- **`I < I*`：`memory-bound`（访存受限）**。此时性能 ≈ `I × BW`，增加算力毫无用处，唯一有用的是**减少搬运的字节**或**提高数据复用**。
- **`I > I*`：`compute-bound`（计算受限）**。此时性能 ≈ `P_peak`，再省带宽也没用，唯一有用的是**用更快的计算单元**（如 Tensor Core）或**减少 FLOPs**。

估算拐点：A100 的 FP16 张量算力约 `312 × 10¹²` FLOP/s，HBM 带宽约 `1.55 × 10¹²` B/s，于是

`I* = 312 × 10¹² / 1.55 × 10¹² ≈ 201 FLOP/Byte`

取整记住 **200 左右**这个量级。后面所有判断都围绕它展开。

> [!TIP]
> 记忆锚点：**拐点数量级 = 峰值算力(TFLOPS) / 带宽(TB/s)**。A100 约 `312/1.55 ≈ 200`，H100 约 `990/3.35 ≈ 295`。算力涨得比带宽快，所以**拐点在持续右移，也就是说有越来越多原本 compute-bound 的算子在变成 memory-bound**。

### 19.2.2 GEMM 与 GEMV 的算术强度

设矩阵乘 `C = A·B`，其中 `A` 为 `M×K`、`B` 为 `K×N`、`C` 为 `M×N`。

**运算量**：每个输出元素需要 `K` 次乘加，每次乘加记 2 FLOPs：

`FLOPs = 2·M·K·N`

**最小访存量**：理想情况下只用读一次输入、写一次输出：

`Bytes = 2·(M·K + K·N + M·N)`

于是

`AI = M·K·N / (M·K + K·N + M·N)`

分两种情况看这个式子：

- **`M`、`N` 都大，`K` 中等**：分母中最小的项主导不了，`AI` 大致是 `min(M,N)` 量级。例如 `M=N=4096`、`K=4096`：`FLOPs = 1.37×10¹¹`，`Bytes = 2×(1.68+1.68+1.68)×10⁷ = 1.0×10⁸`，`AI ≈ 1360`，**远大于 200，是 compute-bound**。
- **`M = 1`（退化为 GEMV）**：把 `M = 1` 代回原式，有 `FLOPs = 2·K·N`，而 `Bytes = 2·(K + K·N + N) ≈ 2·K·N`（`N` 远大于 1 时，`K·N` 项主导分母）。于是

`AI ≈ 2·K·N / (2·K·N) = 1`

**GEMV 的算术强度恒为约 1 FLOP/Byte**，比拐点低两个数量级。这就是"读一遍权重只能换来一次乘加"的含义。**GEMV 永远是 memory-bound，且离拐点极远。**

> [!IMPORTANT]
> 本章最该记住的一句话：**GEMM（大 M/N）是 compute-bound，GEMV（M=1）是 memory-bound。** 而 LLM 推理的两个阶段——prefill 与 decode——恰好分别对应这两者。

Tensor Core 是把这条规则的边界往外推的硬件：它把 `4×4` 或更大尺寸矩阵块的乘加在一条指令里完成，等效把峰值算力提高约一个数量级。代价是它要求数据以特定精度（FP16/BF16/TF32/INT8）和特定布局进入，这正是第 20 章量化存在的硬件动因。

## 19.3 prefill 与 decode：同一模型，两种完全不同的物理过程

自回归生成把一次请求拆成两个性质迥异的阶段。

### 19.3.1 prefill：一次大 GEMM

prefill（也叫 prefill 或 prompt 阶段）把整段 prompt 的 `N` 个 token **一次性**并行喂进模型。此时所有线性层的输入形状是 `N×d` 而不是 `1×d`，于是每个权重矩阵乘都是一次 **`M = N` 的大 GEMM**。

`N` 通常为几百到几万，`AI` 在千量级，**compute-bound**。它能吃饱 Tensor Core，是最"划算"的阶段。

### 19.3.2 decode：逐步退化为 GEMV

decode 每步只生成一个 token。此时输入形状是 `1×d`，每个线性层退化为 `M = 1` 的 GEMV。

关键在于：**为了算这一个 token，必须把整个模型权重从 HBM 读一遍**。同时注意力部分还要把当前所有历史 token 的 KV Cache 读一遍。而换来的 FLOPs 只有 `2×参数量 + 注意力部分`。

用 LLaMA-7B 量级做一次估算（`P = 7×10⁹` 参数，FP16 存储，`L = 32` 层，`h = 4096`，16 头）：

```
每步 FLOPs ≈ 2P + 2·L·h·s     （第二项是 QKᵀ 与 AV 两个乘积）
             ≈ 1.4×10¹⁰ + 2×32×4096×1024
             ≈ 1.4×10¹⁰ + 2.7×10⁸  ≈ 1.4×10¹⁰
每步字节数 ≈ 2P + 4·L·h·s      （权重 + K/V 各 2 字节读一遍）
             ≈ 1.4×10¹⁰ + 5.4×10⁸  ≈ 1.4×10¹⁰
算术强度   ≈ 1 FLOP/Byte        ← 离拐点 200 差了 200 倍
单步耗时   ≈ 1.4×10¹⁰ / 1.55×10¹² ≈ 9 ms（纯带宽下界）
```

同一个模型，prefill 一个 2048 token 的 prompt 大约只需要 10 ms（2048 个 token 一次算完），而 decode 2048 个 token 需要约 18 秒。**差了三个数量级，差别完全来自算术强度。**

### 19.3.3 由此推出的优化方向

既然 decode 的瓶颈是"读一遍权重只换来一个 token 的计算"，那么最直接的优化就是：**让同一遍权重读取服务更多 token**。这就是 batching。

- 若 batch size 为 `B`，权重只需读一遍，却产出 `B` 个 token 的计算：`AI` 提高约 `B` 倍。
- 当 `B` 逼近拐点（约 200）时，decode 重新变成 compute-bound，此时再增大 batch 就不划算了。

这条推论解释了整个现代推理栈的设计动机：**continuous batching、PagedAttention、投机解码、KV Cache 量化，全都在解决"decode 阶段权重与 Cache 的读取成本"。**

> [!WARNING]
> 常见错误是把 decode 慢归因于"生成是串行的"。串行确实限制了并行度，但真正的瓶颈是**访存**：即使你把它串行化，只要算术强度是 1，GPU 的算力就闲置 99% 以上。反过来，prefill 同样有串行依赖的替代品（如逐 token 做），它快是因为 GEMM 的复用率高。

## 19.4 KV Cache：用显存换计算

### 19.4.1 为什么需要

自回归注意力中，第 `t` 步要计算 `softmax(Q_t Kᵀ/√d)V`，其中 `K`、`V` 包含**全部历史 token** 的键值。如果不缓存，第 `t` 步就得**重新计算前 `t−1` 步的 K 和 V**。

不算缓存时的总计算量是 `O(N²·d)` 的键值投影，算上缓存后降为 `O(N·d)`，代价是额外显存。这笔交易在长上下文下极其划算，所以 KV Cache 成为标配。

### 19.4.2 单 token 显存公式的完整推导

设：层数 `L`、隐藏维度 `h`、头数 `H`、单头维度 `d_h = h/H`、FP16 存储（每元素 2 字节）。

```
第 1 步（单个头）：
  该头在每个 token 位置需要缓存 K 向量与 V 向量各一个
  每个 K 向量：d_h 个元素；每个 V 向量：d_h 个元素
  单个头单 token 元素数 = 2·d_h = 2h/H

第 2 步（单层所有头）：
  H 个头合计 = H × 2h/H = 2h 个元素
  ⟹ 等价说法：单层缓存的 K、V 两个矩阵各为 h 维，合计 2h 个元素

第 3 步（所有层）：
  L 层合计 = 2·L·h 个元素

第 4 步（换算字节，FP16 = 2 字节/元素）：
  字节数 = 2·L·h × 2 = 4·L·h 字节
```

即 **单 token 占用 `2 × L × h × 2` 字节**。

> [!IMPORTANT]
> 这个公式里**没有 Q**。原因很直接：`Q` 只在当前步被用来和全部历史 K 打分，用完这个位置就再也不需要它了；而 `K`、`V` 会被**未来每一个 token**用到。**"会被未来复用的才值得缓存"** 是判断一个中间结果该不该进 Cache 的唯一标准。

**总显存估算算例**：`L = 32`、`h = 4096`、FP16，先算出单 token 占用：

`2 × L × h × 2 = 2 × 32 × 4096 × 2 = 524288 字节 ≈ 0.5 MB`

于是总占用随上下文长度线性增长：

| 上下文长度 s | KV Cache 总量 | 对比：7B 权重（FP16，14 GB） |
|---|---|---|
| 1 | 0.5 MB | 1/28000 |
| 1024 | 512 MB | 3.6% |
| 4096 | 2.0 GB | 14% |
| 32768 | 16.0 GB | 114%（已超过权重） |

**结论**：`s = 4096` 时 KV Cache 已占 2 GB；`s = 32k` 时占 16 GB，超过 7B 权重本身。这才是长上下文服务真正的显存压力来源。也解释了为什么 batch size 会被 KV Cache 卡住：`B` 个并发请求各 4096 上下文，就需要 `2.0 × B` GB。

> [!WARNING]
> 逐项相乘时务必写清量纲。`2×L×h×2` 里两个 `2` 的含义完全不同——前一个是「K 和 V 各一份」，后一个是「FP16 每元素 2 字节」；把层数 `L` 漏掉（或把它并进前一个 `2` 里）就会算出小 32 倍的错误答案，这正是 `【2026-09-09 选择 Q3】` 干扰项 A 的构造方式。

### 19.4.3 KV Cache 的压缩思路

既然显存被 KV Cache 主导，压缩它就有直接收益。三条主流思路：

| 思路 | 做法 | 代表方法 | 代价 |
|---|---|---|---|
| 量化 | 把 K/V 从 FP16 降到 INT8/FP4 | KV Cache 量化 | 精度损失，需校准 |
| 淘汰（eviction） | 按重要性丢弃部分 token 的 KV | H2O、StreamingLLM、滑窗注意力 | 被丢的信息永久丢失 |
| 结构性压缩 | 多 query 共享 K/V（MQA/GQA） | GQA | 需重新训练 |

**为什么可以淘汰**：注意力分数本身极度稀疏。H2O 的观察是，少数 token 累积了绝大部分注意力质量（称为 heavy hitters），其余 token 的贡献可以忽略。**StreamingLLM** 则发现序列开头若干 token（attention sink）几乎总被大量关注，因此保留"开头 sink + 最近窗口"就能支撑无限长流式推理。**滑窗注意力**（第 15 章）是最简单的一种：只保留最近 `W` 个 token 的 KV。

`【2026-09-09 编程题 1】` 就是这类淘汰策略的算法内核：给定每层每头的注意力分数与全局显存预算 `M`，选保留哪些 token 的 KV。它的规则值得单独记住：

1. **当前生成位置 `C` 无条件保留**（每层每头各占 1 个名额），刚性开销 `L×H`，剩余预算 `M − L×H`；
2. 其余候选**不分层不分头**，全部汇入一个池子按分数**全局**排序竞争——这正是"每层保留数量可以不同"的来源；
3. 同分时按 `层升序 → 头升序 → token 升序`，把三级优先级编码成一个排序键 `key = (−score, l, h, t)`，负数第一维把"降序"统一成一次升序排序；
4. 排序键构成全序，因此结果唯一。

朴素做法"每轮扫全表挑最优、重复 `M−LH` 轮"是 `O((M−LH)·L·H·N)`，两个因子都可达 `10⁵` 量级，必然超时；一次全局排序是 `O(LHN·log(LHN))`，把"反复求同一个序的前几名"一次性算完。

## 19.5 算子融合：把 HBM 往返省下来

### 19.5.1 逐元素算子的真实成本

逐元素算子（element-wise）如加法、乘法、ReLU、逐元素 Norm，其算术强度极低：每个元素读一次、算一两次、写一次，`AI` 约为 `1/3` 到 `1`。它们**几乎不耗算力，耗的全是显存带宽**。

以 `ResidualAdd + RMSNorm` 为例，设张量形状 `N×d`，元素数 `E = N·d`，FP16：

```
不融合（两个 Kernel）：
  Kernel 1（Add）  ：读 residual(E×2B) + 读 x(E×2B) + 写 y(E×2B) = 6E 字节
  Kernel 2（RMSNorm）：读 y(E×2B) + 读 weight(小) + 写 z(E×2B) ≈ 4E 字节
  合计 ≈ 10E 字节

融合（一个 Kernel）：
  读 residual(2E) + 读 x(2E) + 写 z(2E) = 6E 字节
  中间结果 y 只活在寄存器/SMEM 里，不落 HBM

节省 = 4E 字节，即访存量降到原来的 6/10
```

`E = 4096 × 4096 ≈ 1.7×10⁷` 时，省下约 `6.7×10⁷` 字节；在 1.55 TB/s 的带宽下节省约 **43 微秒**。单个算子省几十微秒看起来不多，但一个 Transformer 层有 2 个这样的位置，32 层每步就是 64 次——**decode 每步总耗时也只有几毫秒，这就是可观的比例**。

> [!IMPORTANT]
> 融合的收益来源**不是减少计算，而是减少 HBM 往返**。因此判断一个融合值不值得做，只需问：**这两个算子之间传递的中间张量有多大？** 中间张量越大，融合收益越大。反过来说，如果两个算子之间本来就没有中间张量（例如中间结果已被下游复用），融合就没有收益。

`【2026-09-02 选择 Q4】` 的四个选项中，D 说"为了增加 FLOPs"是方向完全反了的干扰项。**FLOPs 越少越快才是常态**——在 memory-bound 区间，FLOPs 甚至与耗时无关。

### 19.5.2 GEMM Epilogue 融合

GEMM 的正常收尾是把结果写回 HBM。如果 GEMM 后面紧跟 bias 加、激活函数（GELU/SwiGLU）、或 dropout，那么这些逐元素操作都可以**融进 GEMM 的 Epilogue（收尾阶段）**：结果算出来还躺在寄存器/累加器里，就地加上 bias、过一遍激活，再一次性写回。

省下的是"写完再读回来"的完整一轮 `O(M·N)` 往返。这在 prefill 的大 GEMM 上尤其值钱，因为 `M·N` 可以非常大。

### 19.5.3 融合的收益边界

融合不是免费的，有三条边界：

1. **寄存器压力**：更多逻辑挤进同一个 Kernel → 每线程寄存器用量上升 → 占用率（occupancy）下降，可能反而变慢。
2. **可融合的前提是数据依赖简单**：需要跨块通信的算子（如全局归约）无法简单融合。
3. **工作量太小则不划算**：Kernel 启动本身有固定开销，若中间张量只有几 KB，融合省下的带宽还不如启动开销。

## 19.6 FlashAttention：分块与 online softmax

### 19.6.1 标准注意力的问题

标准注意力需要显式物化分数矩阵 `S = QKᵀ ∈ R^{N×N}`，再对每一行做 softmax，再乘 `V`。

```
标准流程（每一步都往返 HBM）：
  S = Q·Kᵀ        读写 N×N       ← 写 N²×2B
  P = softmax(S)  读写 N×N       ← 再写 N²×2B
  O = P·V         读写 N×N
```

显存与访存都是 `O(N²)`。`N = 4096`、`H = 16` 时，仅 `S` 一个矩阵就是 `16 × 4096² × 2 B = 512 MB`——单层！长上下文下这是不可接受的。

### 19.6.2 online softmax 的递推

FlashAttention 的目标是：**不物化 `S`，也不把 `S` 写回 HBM，只在片上分块处理**。障碍在于 softmax 需要**整行**的统计量（最大值与指数和），而分块处理只能看到行的一部分。

解决办法是维护**running 统计量**并允许事后修正。先回顾数值稳定的 softmax（第 5 章）：对一行分数 `x₁…x_N`，

`softmax(x)_i = e^(x_i − m) / Σ_j e^(x_j − m)`，其中 `m = max_j x_j`

现在把行分成若干块 `B₁, B₂, …`。处理到第 `k` 块时，定义：

- `m_k`：前 `k` 块的最大值
- `ℓ_k = Σ_{j ∈ 前 k 块} e^(x_j − m_k)`：以 `m_k` 为基准的指数和
- `O_k`：前 `k` 块的（未归一化）加权和 `Σ_j e^(x_j − m_k) · v_j`

**递推更新的关键**：新来一块 `B_{k+1}`，其块内最大值为 `m̃`：

```
第一步：更新 running max
  m_{k+1} = max(m_k, m̃)

第二步：计算修正因子（rescale factor）
  c = e^(m_k − m_{k+1})        ∈ (0, 1]

第三步：把已累积的量"改换基准"——因为基准从 m_k 变成了 m_{k+1}
  ℓ_{k+1} = c · ℓ_k + Σ_{j ∈ B_{k+1}} e^(x_j − m_{k+1})
  O_{k+1} = c · O_k + Σ_{j ∈ B_{k+1}} e^(x_j − m_{k+1}) · v_j
```

`c` 的必要性来自**基准不统一**：`ℓ_k` 与 `O_k` 是以 `m_k` 为基准算出来的指数，而新块要用 `m_{k+1}` 作基准。把旧结果换成新基准，等价于整体乘 `e^(m_k − m_{k+1})`：

```
e^(x_j − m_{k+1}) = e^(x_j − m_k) · e^(m_k − m_{k+1})
                              └──────┬──────┘
                                     c
```

由于 `m_{k+1} ≥ m_k`，恒有 `c ≤ 1`，**乘一个小于等于 1 的因子是数值安全的**（不会上溢）；这也是必须用 `max` 而不是其他统计量的原因。

**为什么结果是精确等价的**：上述递推只用了指数运算的加法律 `e^(a+b) = e^a·e^b`，没有任何近似。所有块处理完后，`O / ℓ` 就是标准 softmax 的加权和。差别只在**浮点舍入顺序**，与"近似算法"（如线性注意力、稀疏注意力）有本质不同。

### 19.6.3 tiling 与反向

正向：把 `Q` 按行切成块（外层循环），`K`、`V` 按列切成块（内层循环），每对块载入 SMEM 计算，维护 running `m`、`ℓ`、`O`，全程不写回 `N×N` 矩阵。

```
for each Q-block (外层，常驻 SMEM):
    初始化 m = −∞, ℓ = 0, O = 0
    for each K/V-block (内层，流式载入 SMEM):
        S_blk = Q_blk · K_blkᵀ            （只活在片上）
        按上面三条递推更新 m, ℓ, O          （不物化 N×N）
    写回 O / ℓ                            （只写 N×d）
```

结果：**显存从 `O(N²)` 降到 `O(N)`，HBM 访存从 `O(N²)` 降到 `O(N²/M)`**（`M` 为 SMEM 能容纳的块大小），`M` 越大收益越大。反向传播需要重算 `S` 而不是保存它（recomputation），这是 FLOPs 换访存的又一处典型交易。

## 19.7 批处理与调度

### 19.7.1 静态 batching 的问题

静态 batching 把 `B` 个请求打包成一个 batch，一起做 prefill，再一起做 decode，直到**全部**请求生成结束才返回。

它有三个致命缺陷：

1. **长短不一导致空转**：batch 里有请求生成了 5 个 token 就结束，其他请求要生成 500 个，那 5 个槽位在后 495 步全部闲置。
2. **等待延迟**：新请求必须等当前 batch 整体结束才能进入，队头阻塞严重。
3. **填充浪费**：prefill 的 prompt 长度不一致，需要 padding 到最长，pad 部分白算。

### 19.7.2 continuous batching

**continuous batching**（也叫 iteration-level scheduling）把调度粒度从"整个 batch"降到"单个 decode step"：**每一步结束时都重新检查谁完成了、谁在等待，立刻把空出的槽位填给新请求**。

效果：GPU 槽位利用率大幅提高，新请求的排队延迟从"一个完整 batch 的时间"降到"一个 step 的时间"。这也是 vLLM / TensorRT-LLM 最核心的吞吐优化。

### 19.7.3 PagedAttention：用虚拟内存的思路治碎片

即便有了 continuous batching，KV Cache 的**显存管理**仍然棘手。传统做法是给每个请求预分配一段**连续**的最大长度显存（因为要预留最长可能的输出）。这带来两类浪费：

```
内部碎片：预分配 2048 token，实际只用了 300   → 浪费 85%
外部碎片：不同长度的空洞散落，无法拼给新请求
```

**PagedAttention** 借用操作系统的虚拟内存（virtual memory）类比来解决：

| OS 概念 | PagedAttention 对应物 |
|---|---|
| 页（page） | KV block（固定大小，如 16 个 token） |
| 页表（page table） | block table（逻辑块 → 物理块映射） |
| 物理帧（frame） | 显存中的物理 block |
| 虚拟地址连续、物理可离散 | 逻辑上连续上下文，物理上可任意散布 |
| 按需分页 | 按需分配新 block |

于是 KV Cache 可以**按需增长、非连续存放**，内部碎片被限制在一个 block 内（最多浪费 15 个 token 的槽位），外部碎片完全消失。附带的好处是**前缀共享**：多个请求共享同一段 system prompt 时，它们的 block table 可以指向同一批物理 block，用引用计数管理——这就是 prefix caching。

### 19.7.4 调度策略

| 策略 | 规则 | 适用 |
|---|---|---|
| FCFS | 先到先服务 | 简单，但长请求会阻塞短请求 |
| 优先级 | 按用户/任务等级排队 | 在线服务分级 SLA |
| SJF / 最短剩余优先 | 优先短输出 | 降低平均延迟，可能饿死长请求 |
| 抢占式 | 显存紧张时换出请求的 KV | 防止 OOM，代价是重算 |

实践中常组合：**优先级 + 抢占 + 公平性约束**。核心矛盾始终是**延迟与吞吐的权衡**（见 19.9）。

## 19.8 投机解码：用并行验证换串行生成

decode 的串行性来自自回归依赖：第 `t+1` 个 token 依赖第 `t` 个。**投机解码（speculative decoding）** 用一个便宜的 **draft 模型**先连续猜出 `γ` 个 token，再用**目标模型一次性并行验证**这 `γ` 个位置。

为什么能加速：验证 `γ` 个 token 只需要**一次**目标模型前向（形状是 `γ×d` 的小 GEMM），而串行生成 `γ` 个 token 需要 `γ` 次前向。draft 模型很小，猜得快；目标模型只做一次。

关键在于**接受准则**：设 draft 分布为 `q`、目标分布为 `p`，对每个位置以概率 `min(1, p(x)/q(x))` 接受。可以证明这样得到的样本**分布与原目标模型完全一致**——即**加速不改变输出分布**，只改变生成路径。若某个位置的猜测被拒绝，就从修正分布 `norm(max(0, p − q))` 重新采样并弃掉其后所有草稿。

**期望加速比**取决于**接受率 `α`**：每轮期望接受的 token 数为 `(1 − α^(γ+1))/(1 − α)`。`α` 高（draft 与目标分布接近）时收益大；`α` 过低时，draft 的开销反而成为负担，此时应减小 `γ` 或放弃投机。

## 19.9 性能度量

| 指标 | 定义 | 受什么影响 |
|---|---|---|
| **TTFT**（time to first token） | 从请求发出到第一个 token 返回 | 排队时间 + prefill 时间；prefill 是 compute-bound，受 prompt 长度主导 |
| **TPOT / ITL**（time per output token / inter-token latency） | 后续每个 token 的平均间隔 | decode 步耗时；memory-bound，受权重大小与 batch size 影响 |
| **吞吐**（throughput） | 全系统每秒产出的 token 总数 | batch size、并发数；`吞吐 ≈ B / TPOT` |
| **QPS** | 每秒完成的请求数 | 与输出长度强相关 |

端到端延迟可近似拆解：

`总延迟 ≈ TTFT + (输出 token 数 − 1) × TPOT`

**延迟与吞吐的权衡**：增大 batch size 会提高吞吐（权重读取被摊薄），但每个请求的 TPOT 也可能上升（算力开始成为瓶颈、且排队变长）。因此**在线服务通常追求"满足 TPOT SLA 前提下的最大 batch"**，而不是一味追求吞吐。反过来，离线批处理（如数据标注）则把 batch 开到最大。

**显存对 batch size 的硬约束**：

`可用显存 ≥ 权重(2P 字节) + B × KV缓存(单请求) + 激活与工作区`

把 19.4 的算例代进去：80 GB 卡、7B 模型 FP16（14 GB）、每个请求 4096 上下文（2 GB），`B` 最多约 30；若上下文降到 1024（512 MB/请求），`B` 可达 120 以上。**这正是长上下文服务必须做 KV Cache 压缩的算术原因。**

`【2026-08-05 选择 Q13】` 考的是同一件事的另一面：**推理峰值内存远大于模型文件**，因为还要驻留中间激活、算子临时工作区（workspace）与多分支并发时的多份中间结果。

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 存储层级 | 片上（寄存器/SMEM）带宽约为 HBM 的 5~10 倍，容量却小 5 个数量级 | 以为显存大就够快，忽略带宽是瓶颈 |
| 算术强度 | `AI = FLOPs / Bytes`，拐点 `I* = 峰值算力 / 带宽`（A100 约 200） | 直接拿峰值 TFLOPS 估性能 |
| GEMM vs GEMV | 大 M/N 的 GEMM 是 compute-bound；`M=1` 的 GEMV `AI ≈ 1`，是 memory-bound | 认为矩阵越大越慢 |
| prefill vs decode | prefill 是大 GEMM（算力受限），decode 是 GEMV（访存受限，每步读一遍权重+KV） | 把 decode 慢归因于"串行"，而非访存 |
| KV Cache | 单 token `2 × L × h × 2` 字节，无 Q | 漏乘层数 `L`，或把 `s` 乘进单 token 口径 |
| 算子融合 | 收益来自省 HBM 往返，不来自省 FLOPs | 认为融合是为了增加计算量 |
| FlashAttention | online softmax 递推 + 分块，`O(N²)` 显存降为 `O(N)`，结果精确等价 | 把它当成近似注意力 |
| 批处理 | continuous batching 把调度粒度降到单步；PagedAttention 用分页治碎片 | 以为静态 batching 也能服务在线流量 |
| 投机解码 | draft 猜测 + 目标模型并行验证，接受率决定加速比 | 以为会改变输出分布 |

## 自测题

**Q1**（判断）某算子在一次执行中读取了 2 GB 数据、完成了 `5×10¹¹` 次浮点运算。在 A100（FP16 峰值约 312 TFLOPS、带宽 1.55 TB/s）上，它是 compute-bound 还是 memory-bound？

<details><summary>答案与解析</summary>

`AI = 5×10¹¹ / 2×10⁹ = 250 FLOP/Byte`，大于拐点约 200，因此是 **compute-bound**，但非常接近拐点。

估算两种上界：

```
访存上界耗时 = 2×10⁹ / 1.55×10¹² ≈ 1.3 ms
算力上界耗时 = 5×10¹¹ / 312×10¹² ≈ 1.6 ms
```

算力上界更紧，故 compute-bound。注意两个数字只差 30%，这类"贴着拐点"的算子对两端优化都敏感——这是实际工程中最难优化的一类。

常见错误：直接把 `FLOPs / 峰值算力` 当作耗时而不检查访存是否更紧；或者只算带宽耗时。**两个上界都要算，取较大者。**
</details>

**Q2**（计算）一个 13B 参数的模型，`L = 40` 层、隐藏维度 `h = 5120`，权重与 KV Cache 都用 FP16。求：(a) 单 token 的 KV Cache 占用；(b) 上下文长度 8192 时的单请求 KV 总量；(c) 在 80 GB 显存、batch size 为 32 时，KV Cache 占多少显存，是否放得下？

<details><summary>答案与解析</summary>

(a) 单 token 字节数 = `2 × L × h × 2 = 2 × 40 × 5120 × 2 = 819200` 字节 ≈ **0.78 MB**。

(b) `0.78 MB × 8192 ≈ 6.4 GB`。

(c) `6.4 GB × 32 ≈ 205 GB`。权重是 `2 × 13×10⁹ = 26 GB`，加上 `205 GB` 远超 80 GB，**完全放不下**。即使 batch 取 1，KV Cache 也要 6.4 GB（权重 26 GB + 6.4 GB + 激活 ≈ 35 GB，可行）。

这说明：**13B 模型在 8192 上下文下的并发能力被 KV Cache 卡在个位数**。要提高到 batch 32，必须把 KV Cache 压到约 1/8，例如 GQA（`H_kv = H/8` 直接省 8 倍）或 INT8/FP8 量化（省 2~4 倍）。

常见错误：忘记 `h` 是**隐藏维度**而不是单头维度。若模型是 40 头、`d_h = 128`，用 `2×L×H×d_h×2` 得到的是同一个数——两条路径必须一致，可作为自检。
</details>

**Q3**（推导）说明 `ResidualAdd + RMSNorm` 融合为什么能省掉"一整轮 HBM 往返"，并用 `E = 3.0×10⁷` 个 FP16 元素、带宽 1.55 TB/s 估算节省的时间。

<details><summary>答案与解析</summary>

不融合时，Kernel 1 把 Add 的结果 `y` 写回 HBM，Kernel 2 再把它读回来。这一写一读各 `2E` 字节，合计 `4E` 字节的纯浪费。

```
节省字节 = 4E = 4 × 3.0×10⁷ = 1.2×10⁸ 字节
节省时间 = 1.2×10⁸ / 1.55×10¹² ≈ 77 微秒
```

（若只算"多出来的一轮往返"即 `4E`；若把两次执行的访存总量对比，则从不融合的 `10E` 降到 `6E`，省 `4E`，结论一致。）

对 decode 而言，单步总耗时约几毫秒，77 微秒约占 2%；但一个 32 层模型每步有 64 个这样的融合点，累计可达毫秒量级，**与 decode 单步总耗时同量级**，因此收益是实质性的。

关键论证点：**融合的收益与中间张量的元素数成正比，与 FLOPs 无关**。若把两个算子之间的中间张量缩小（如先降维再做 Norm），收益也随之减小。
</details>

**Q4**（推导）写出 online softmax 的递推式，并说明 rescale 因子 `c = e^(m_k − m_{k+1})` 为什么必须乘在已累积的 `ℓ_k` 和 `O_k` 上。如果不乘会发生什么？

<details><summary>答案与解析</summary>

递推式：

```
m_{k+1} = max(m_k, m̃)
c       = e^(m_k − m_{k+1})
ℓ_{k+1} = c · ℓ_k + Σ_{j ∈ B_{k+1}} e^(x_j − m_{k+1})
O_{k+1} = c · O_k + Σ_{j ∈ B_{k+1}} e^(x_j − m_{k+1}) · v_j
```

必须乘 `c` 的原因：`ℓ_k` 与 `O_k` 中的指数**都是以 `m_k` 为基准**算出来的，而新块要统一到 `m_{k+1}` 基准。由 `e^(x−m_{k+1}) = e^(x−m_k)·e^(m_k−m_{k+1})`，旧结果整体乘 `e^(m_k − m_{k+1})` 即完成换基准。

不乘的后果：一个块的指数和与另一个块的指数和基准不同，**相加在数学上无意义**。具体表现是——若后面出现了更大的分数，前面那些块用较小基准算出来的 `e^(x−m_k)` 会偏大，累加后 `ℓ` 虚高、`O` 被高估，最终输出 `O/ℓ` 错误（前面的 token 权重被系统性放大）。

另一层必要性：`c ≤ 1` 恒成立（因为 `m_{k+1} ≥ m_k`），所以修正只会**缩小**已累积量，不会上溢。这也是必须用 `max` 作为基准的原因——若用别的统计量，`c` 可能大于 1 而导致溢出。
</details>

**Q5**（辨析）某推理服务把 batch size 从 8 提高到 64，吞吐从 400 tokens/s 升到 2400 tokens/s，但每个请求的 TPOT 从 22 ms 涨到 40 ms。请解释这两个现象同时出现的原因，并说明什么情况下不应继续增大 batch。

<details><summary>答案与解析</summary>

原因：decode 是 memory-bound，每步要读一遍全部权重与 KV Cache。batch 从 8 到 64 时，**权重只读一遍却服务了 8 倍的 token**，因此吞吐接近线性增长（400→2400，恰好 6 倍）；但 KV Cache 的读取量随 batch 线性增长，加上算力开始被占用，单步总耗时上升，于是 TPOT 变大。

什么时候停：

1. **算力成为瓶颈**：`AI = B` 逼近拐点（约 200）时，继续加大 batch 不再带来吞吐收益，只会推高 TPOT。
2. **违反 SLA**：若业务要求 TPOT ≤ 30 ms（约 33 tokens/s 的体感），则在 batch 约 48 处就该停。
3. **显存不足**：KV Cache 随 `B × s` 线性增长，触顶后无法继续加 batch。

结论：**吞吐与延迟的权衡点由 SLA 而非硬件决定**。在线服务应取"满足 TPOT 上限的最大 batch"，离线批处理才取吞吐最大化。
</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| `【2026-09-02 选择 Q11】` prefill/decode 瓶颈特征 | prefill 是大 GEMM 故 compute-bound，decode 是 GEMV 故 memory-bound | 19.2.2、19.3 |
| `【2026-09-02 选择 Q4】` ResidualAdd + RMSNorm 融合原因 | 逐元素算子 memory-bound，融合省 HBM 往返 | 19.1、19.5.1 |
| `【2026-09-09 选择 Q3】` KV Cache 单 token 显存公式 | `2 × L × h × 2` 字节的逐项推导，Q 不进 Cache | 19.4.2 |
| `【2026-09-09 编程题 1】` KV 缓存稀疏化与多级排序 | 全局排序键 `(−score, l, h, t)`、当前 token `C` 的刚性开销 `L×H`、KV 淘汰策略 | 19.4.3 |
| `【2026-08-05 选择 Q13】` 推理峰值显存构成 | 权重之外还有激活、临时工作区与多分支并存结果 | 19.9 |
| `【2026-09-02 选择 Q12】` 张量并行通信位置 | 层内前向/反向的 All-Reduce（详见第 21 章） | 19.2.2（Tensor Core 与通信代价） |

## 延伸阅读

- Williams, Waterman, Patterson, *Roofline: An Insightful Visual Performance Model for Multicore Architectures*, CACM 2009 —— 算术强度与拐点的原始出处。
- Dao et al., *FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness*, NeurIPS 2022 —— 重点读 online softmax 的递推与反向重算部分。
- Kwon et al., *Efficient Memory Management for Large Language Model Serving with PagedAttention*, SOSP 2023 —— 虚拟内存类比与 block table。
- Zhang et al., *H2O: Heavy-Hitter Oracle for Efficient Generative Inference of LLMs*, NeurIPS 2023；Xiao et al., *Efficient Streaming Language Models with Attention Sinks*, ICLR 2024 —— 两类 KV 淘汰策略。
- Leviathan et al., *Fast Inference from Transformers via Speculative Decoding*, ICML 2023 —— 接受准则与分布等价性证明。
- 第 20 章（量化与压缩）接着本章的"减少搬运字节"往下走；第 21 章（分布式训练与并行）解答"单个 GPU 放不下怎么办"。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch19/  

