前置讲 P4 · 计算机系统速成：存储层次、排队、并发、分页与网络 · A Crash Course on Computer Systems

这是一篇前置讲，不对应原课的某一次课。原课默认学生熟悉计算机系统的基本概念：第 2 讲讲 GPU 服务器里的 CPU、内存、PCIe、NVLink；第 4 讲讲显存的延迟（约 500 个周期）和”内存访问效率至关重要”；第 14–16 讲讲多卡通信和流水线；第 22 讲讲请求调度；第 24 讲的 PagedAttention 直接借用了操作系统的分页。这篇为没有系统背景的读者把这些概念补齐。 依据说明：本讲讲的是标准的计算机体系结构、操作系统和网络知识，参考 Bryant & O’Hallaron Computer Systems: A Programmer’s Perspective（CS:APP）、Arpaci-Dusseau Operating Systems: Three Easy Pieces（OSTEP）、Harchol-Balter Performance Modeling and Design of Computer Systems（排队论），以及 Jeff Dean 流传很广的”每个程序员都应该知道的延迟数字”。延迟和带宽的典型量级是常被引用的近似值；本机实测都标 ⏱；所有实验都是本讲义自己设计的。 配套代码 Code：code/prereq4/（5 个脚本 + 1 个模块 + 1 个 C 源文件；需要 numpy，01 号脚本的一部分需要 C 编译器；每个脚本 1–8 秒） 预计阅读时间：3–4 小时（含运行代码） 建议阅读时机：第 4 讲之前；第 14 讲（分布式训练）和第 22、24 讲（服务系统）之前回看

0. 本讲导航 · How to read this lecture

0.1 为什么要懂这些

LLM 系统里最重要的设计，很多都是几十年前计算机系统里的老想法换了个场景：

0.2 学习目标 Learning goals

1. 说出存储层次各级的延迟和带宽量级；理解局部性和缓存行；能用实验看到缓存的台阶，并解释”跳着读不省时间""随机读比顺序读慢”。
2. 区分延迟和吞吐量；会用流水线的瓶颈和气泡分析一条处理链；理解排队论的核心结论（时延 ∝ 1/(1 − 负载)）和 Little 定律；理解攒批为什么能用一点延迟换几倍吞吐量。
3. 区分进程和线程、并发和并行；理解 Python 的 GIL；知道竞争条件是怎样产生的、原子操作和锁怎样解决；理解计算与通信的重叠。
4. 理解虚拟内存、页表、按需分页；区分外部碎片和内部碎片，知道分页怎样消除外部碎片、页的大小怎样权衡；理解写时复制。
5. 会用 α-β 模型估算通信时间，理解为什么要把小消息分桶；知道环形和树形集合通信各自适合什么情况。

0.3 本讲地图 Map

§1  存储层次：量级；局部性；⏱ 缓存台阶；⏱ 缓存行；⏱ 顺序 vs 随机；GPU 的存储层次              ← 代码 01
§2  延迟、吞吐量与排队：定义；Little 定律；流水线与气泡；排队论；攒批                          ← 代码 02
§3  并发：进程与线程；GIL；并发 vs 并行；竞争条件与原子操作；计算与通信的重叠                  ← 代码 03
§4  虚拟内存与分页：地址翻译；按需分页；碎片；页的大小；写时复制；KV 缓存的预告               ← 代码 04
§5  网络：α-β 模型；⏱ 本机实测；分桶；拓扑与集合通信                                       ← 代码 05
§6  小结   §7  常见误区   §8  练习   §9  延伸阅读   §10 下一篇预告

0.4 先修

前置讲 P1（指针、数组、malloc / free）。会用 NumPy。

1. 存储层次 · The memory hierarchy

1.1 为什么要分层

理想的存储又大、又快、又便宜，但物理上做不到：快的存储（寄存器、SRAM）每个比特需要更多晶体管、更贵、而且必须离计算单元很近，所以容量很小；大的存储（DRAM、SSD）便宜，但离得远、访问慢。于是计算机把存储分成很多层，越靠近计算单元越小越快，并且想办法让程序需要的数据大部分时间都待在快的那几层。

1.2 量级：延迟与带宽

01 号脚本第 1 部分列出了常被引用的典型量级（不同硬件差几倍很正常，记住数量级即可）：

两条规律：延迟随距离指数增长（L1 到 DRAM 差约 100 倍，到 SSD 差约 2 万倍）；带宽也分层（同一块数据，从 GPU 显存读比经 PCIe 读快约 100 倍）。第 1 讲 §4.7 里”把一层的权重经 PCIe 搬过来，比算这一层慢 15 倍”，就是这两张表的直接推论。

1.3 缓存与局部性

缓存（cache）是一小块快速存储，自动保存最近用过的数据的副本。它之所以有用，是因为程序的访问有局部性：

• 时间局部性：刚用过的数据，很可能马上再用（循环里的累加变量、矩阵乘法里被反复使用的那一块）。
• 空间局部性：用了一个地址，很可能马上用它旁边的地址（顺序遍历数组）。

为了利用空间局部性，内存和缓存之间不是一个字节一个字节地搬，而是一次搬一整块，叫缓存行（cache line，常见 64 字节，本机 128 字节）。

1.4 ⏱ 实测：缓存的台阶

怎样测”读一次内存要多久”？难点是 CPU 很聪明：如果访问模式有规律，它会提前把数据取来（预取），或者同时发出好几个读取。指针追逐（pointer chasing）让这些优化全部失效：把数组排成一个随机的环，i = next[i] 一步步走——每次读的地址取决于上一次读到的值，只能老老实实一次一次地等。01 号脚本第 2 部分用 C 实现了这个循环（csrc/p4lib.c），工作集从 16 KiB 涨到 256 MiB（本机：L1 128 KiB、L2 16 MiB）：

台阶清清楚楚：放得进 L1 时 1 纳秒；超出 L1 后是 L2 的几纳秒；超出 L2 之后一路涨到主内存的一百多纳秒——和 §1.2 的典型量级一致。

1.5 ⏱ 缓存行：跳着读不省时间

01 号脚本第 3 部分在一个 256 MiB 的 float32 数组上，每隔 stride 个元素读一个（用 8 个独立的累加器，避免 P1 §1.3 说的加法依赖链成为瓶颈）：

• stride 从 4 到 16，读的元素少了 4 倍，时间几乎不变：只要每个缓存行都要碰到，从内存搬来的字节数就一样。
• 步长超过一行之后，碰到的行数减半，时间也大致减半（128 → 256）。
• 一个意外：stride = 32（恰好每行读一个）在本机上稳定地比 16 和 64 都慢。我没有找到确定的原因（可能和硬件预取器对这个步长的处理有关）。测量常常会碰到不符合简单模型的点，如实记录它，比假装它不存在更有用。

结论：数据搬运的最小单位是一整行。“只用其中一个数”就浪费了其余的带宽。GPU 上的对应概念是合并访存（coalescing）：一个线程束（32 个线程）的访问被合并成若干个 32 或 128 字节的内存事务，相邻线程读相邻地址时，一次事务就能满足所有线程（第 4 讲）。P1 §6.3 里”按列遍历比按行慢 5.7 倍”也是同一个原因。

1.6 ⏱ 顺序读 vs 随机读

01 号脚本第 4 部分用 np.take 从一个 128 MiB 的数组里按下标取出全部 3355 万个元素——同样的数据、同样的计算量，只是下标的顺序不同：顺序下标约 71 ms，随机打乱的下标约 340 ms，慢约 5 倍。顺序访问时每个缓存行都被用满，硬件预取也能提前把下一段取来；随机访问时几乎每次都要等一次内存延迟，一整行只用 4 个字节。

嵌入查表（按 token id 读嵌入矩阵的行）、MoE 把 token 分发给不同的专家，都是”按下标读取”——它们快不快，取决于访问能不能被组织得尽量连续（第 8、17 讲）。

1.7 GPU 的存储层次

GPU 有同样的层次，只是比例不同（第 2、4 讲细讲）：

和 CPU 最大的两个不同：

1. GPU 不靠缓存把单次访问变快，而是靠并行把等待藏起来：每个 SM 同时驻留几十个线程束，一个在等显存，就切换到另一个（延迟隐藏）。
2. 共享内存要程序员自己管：把一块数据从显存搬进共享内存，让一个线程块里的所有线程反复使用（时间局部性），再写回——这叫分块（tiling）。第 4 讲的分块矩阵乘法、第 21 讲的 FlashAttention，本质上都是在手工管理这一级”缓存”。

2. 延迟、吞吐量与排队 · Latency, throughput and queueing

2.1 两种”快”

• 延迟（latency）：一个请求从进来到完成要多久——用户感受到的快慢。
• 吞吐量（throughput）：单位时间完成多少个请求——系统的产能，决定成本。

02 号脚本第 1 部分：一个一个地处理、每个 10 ms，延迟 10 ms、吞吐量 100 个/秒；攒 8 个一起处理、一批 20 ms，吞吐量 400 个/秒，但每个请求至少要 20 ms（还没算等着凑批的时间）；开 4 台机器各自处理，延迟 10 ms、吞吐量 400 个/秒，但要花 4 倍的钱。LLM 服务的大部分设计（连续批处理、预填充/解码分离）都是在这两个指标之间找平衡。

Little 定律把它们联系起来：在一个稳定的系统里，

例如一个推理服务每秒完成 50 个请求、平均每个要 2 秒，那么任何时刻平均有 100 个请求正在处理——它们的 KV 缓存都要同时放在显存里。这个简单的等式常用来估算”需要多大的并发、多少显存”。

2.2 流水线：瓶颈与气泡

一条处理链由几道工序组成时，可以让各道工序同时处理不同的工件（流水线）。02 号脚本第 2 部分：三道工序各要 3 / 5 / 2 ms，处理 100 个工件：

流水线稳定之后每 5 ms 出一个工件——吞吐量由最慢的一道工序决定。加速非瓶颈的工序几乎没用，加速瓶颈才有效。这就是第 1 讲 §2.3 工厂题的道理，也是一切性能优化的第一原则：先找瓶颈。

流水线刚开始灌满、最后排空时，有的工序在空等，叫气泡（bubble）。4 道等长工序时，气泡占总时间的比例：1 个工件 75%，4 个 42.9%，16 个 15.8%，256 个 1.2%。第 16 讲的流水线并行把模型的不同层放在不同的 GPU 上，再把一个批次切成很多”微批次”依次送进去，就是为了把气泡压小。

2.3 排队论：为什么不能跑到 100%

请求是随机到达的。02 号脚本第 3 部分模拟了一个服务台（平均处理 10 ms，即最多 100 个/秒），请求按泊松过程到达，每个负载模拟 20 万个请求：

• 服务一个请求明明只要 10 ms，负载 90% 时平均却要 104 ms，95% 时 p99 将近 1 秒。原因是随机到达：偶尔一下子来好几个，就得排队；负载越高，队伍越难消化。
• 排队论给出的 M/M/1 公式 $W = S / (1 - \rho)$ 说明了一切：分母里的 1 − ρ 让时延在负载接近 100% 时趋向无穷。服务时间固定（M/D/1）时排队等待减半，但同样在 ρ → 1 时爆炸。
• 负载 99% 时，模拟值明显偏离公式：接近满载时队伍长度的波动极大，20 万个请求还不足以让平均值收敛——“接近满载的系统很不稳定”，在模拟里也体现了出来。

所以在线服务从不把机器跑到 100%，要给突发流量留余量；服务等级目标（SLO）通常约束的是尾部时延（p99），而不是平均值（第 26 讲）。

2.4 攒批：用一点延迟换几倍吞吐量

如果一次处理一批请求的代价是”固定开销 + 每个请求一点点”，就值得攒批。02 号脚本第 4 部分：每批耗时 20 ms 固定开销 + 1 ms × 批大小：

不攒批时产能只有约 1/(21 ms) ≈ 48 个/秒；允许攒批后，负载低时批很小（几乎没有额外延迟），负载高时自动攒成大批，产能涨到约 615 个/秒。这正是 LLM 解码的情形：每一步都要读一遍全部权重（固定开销），多服务一个请求只多一点点计算（第 1 讲 §5.7）。第 22 讲的连续批处理让新请求在每一步都能插进正在运行的批里，比这里”等上一批做完再凑下一批”更进一步。

3. 并发 · Concurrency

3.1 进程与线程

• 进程（process）：一个运行中的程序，有自己独立的内存空间（由虚拟内存隔开，§4）。
• 线程（thread）：同一个进程里的多条执行流，共享这个进程的内存。

03 号脚本第 1 部分：线程把共享变量改成 42，主程序立刻看到 42；子进程把它改成 99，主程序看到的还是 0——子进程改的是它自己的副本。进程之间要交换数据，必须显式地通信（管道、共享内存、网络）。多 GPU 训练通常是”每块 GPU 一个进程”，第 14–15 讲的 rank 就是进程编号，进程之间通过 NCCL 交换梯度。

3.2 Python 的 GIL

标准的 Python 解释器（CPython）有一把全局解释器锁（GIL）：同一时刻只有一个线程能执行 Python 字节码。03 号脚本第 2 部分（⏱，4 个纯 Python 的 CPU 密集任务，本机 12 核）：

线程几乎没有加速；进程各有自己的解释器和 GIL，真正并行。PyTorch 的 DataLoader 用多个工作进程预处理数据，就是这个原因。NumPy、PyTorch 的大运算在 C/C++ 里执行时会释放 GIL，所以”Python 慢”主要影响的是 Python 层的循环和调度——第 22 讲的 SGLang 专门讨论了怎样让 CPU 上的调度不拖累 GPU。（Python 3.13 起有一个实验性的”无 GIL”版本，本讲义用的是默认的有 GIL 版本。）

3.3 并发 vs 并行

• 并行（parallelism）：多件事在同一时刻、在不同的硬件上执行（4 个进程在 4 个核上）。
• 并发（concurrency）：多件事在时间上交叠（一个在等，另一个在做），不一定同时在执行。

03 号脚本第 3 部分：8 次”等待 0.1 秒”（模拟读文件、等网络），一个接一个要 0.83 秒，8 个线程同时等只要 0.11 秒——等待时不需要 CPU，也会释放 GIL。推理服务器同时处理成百上千个请求，大量时间花在等待上（等网络、等 GPU），并发的组织方式决定了它能撑多少负载。

3.4 竞争条件、原子操作与锁

两个线程同时给一个计数器加 1：每个线程要做三步——把 x 读进自己的寄存器、加 1、写回 x。03 号脚本第 4 部分把所有可能的执行顺序（交错）都列了出来：

一个出错的交错：A 读（x=0）→ B 读（x=0）→ A 加、写（x=1）→ B 加、写（x=1）——一次加法丢了（丢失更新）。这种依赖于执行顺序的 bug 叫竞争条件（race condition）。真实运行时各种交错出现的概率并不相等（线程恰好在这几步之间被切换的机会很小），所以这种 bug 可能运行很多次才出现一次——这正是它难查的原因。

解决办法是让”读-加-写”变成不可分割的一步：

• 锁（lock / mutex）：同一时刻只允许一个线程进入”临界区”。代价是其他线程要等，用不好还会死锁（两个线程各拿着一把锁、等对方的另一把）。
• 原子操作（atomic）：硬件直接提供不可分割的”读-改-写”指令。GPU 上成千上万个线程同时写同一个位置时（嵌入层的反向、直方图、某些归约），用的就是原子加法 atomicAdd。原子操作保证结果正确，但不保证加法的顺序——于是浮点结果每次可能略有不同（P2 §3.3）。

3.5 计算与通信的重叠

如果计算和通信由不同的硬件执行（GPU 的计算单元和网卡 / 拷贝引擎），而且数据被切成了块，就可以”发第 i 块的同时算第 i+1 块”。03 号脚本第 5 部分（16 块数据）：

计算比通信慢时，重叠几乎把通信完全藏了起来；通信比计算慢时，总时间由通信决定——又是瓶颈（§2.2）。第 15 讲的 DDP 把梯度分成多个”桶”，一个桶算完就开始 all-reduce，同时继续算下一个桶；CUDA 用多个流（stream）让拷贝和计算同时进行。第 1 讲 §5.6 的那个”通信比计算还慢”的例子，正是需要这种重叠的场景。

4. 虚拟内存与分页 · Virtual memory and paging

4.1 虚拟地址与页表

程序里用的地址（P1 里打印出来的那些 0x16d8e282c）都是虚拟地址，不是真实的物理内存位置。内存被切成固定大小的页（本机 16 KiB，常见是 4 KiB）。硬件把虚拟地址拆成”虚拟页号 + 页内偏移”，查页表把虚拟页号换成物理页号，偏移不变：

04 号脚本第 1 部分用两张玩具页表演示了：相邻的两个虚拟页（0x3FFF 和 0x4000）可以落在物理内存里完全不相邻的地方；两个进程用同一个虚拟地址，访问的是不同的物理内存——这就是 §3.1 里子进程改不到父进程变量的原因。虚拟内存同时带来了隔离（安全）和灵活（程序看到的是连续的地址，物理上却可以东一块西一块）。查页表要访问内存，所以 CPU 用一个专门的小缓存（TLB）记住最近的翻译结果。

4.2 ⏱ 按需分页

04 号脚本第 2 部分：np.empty 申请 512 MiB，峰值内存增加 0；写入前 256 MiB，增加 256 MiB；写入全部，增加 512 MiB。申请时操作系统只在页表里登记了一段虚拟地址，第一次写某一页时才真正分配物理页（按需分页，demand paging）。

GPU 显存通常没有这种”先登记、后分配”的机制：cudaMalloc 申请多少就立刻占多少。所以推理系统如果按”最大可能长度”为每个请求预留 KV 缓存，预留的部分就实打实地浪费掉了（§4.6）。

4.3 碎片：外部与内部

如果每个块都必须是一段连续的空间（连续分配），反复申请、释放之后，空闲空间会被切成很多小空洞。04 号脚本第 3 部分在容量 10,000 的空间里做 4000 步随机申请（20–399 个单位）/ 释放：

一次典型的失败：要 366 个单位，当时空闲总量有 2562，但被切成了 25 个空洞，最大的只有 301。这叫外部碎片（external fragmentation）。分页把空间切成固定大小的页，一个块的各页不需要相邻，所以没有外部碎片（分页的 9 次失败都是页真的用完了）。代价是每块的最后一页可能没用满，叫内部碎片（internal fragmentation），平均浪费半页——这里是 3.0%。

4.4 页该多大

04 号脚本第 4 部分对 2000 个随机大小的块计算：

页越小，浪费越少，但页表越大、管理开销越高；页越大则相反。操作系统的页通常是 4 KiB，vLLM 的 KV 缓存默认每页 16 个 token——都是这个折中的结果（第 24 讲）。

4.5 共享与写时复制

页表还让”共享”变得很便宜：两个进程的页表可以指向同一个物理页。写时复制（copy-on-write）更进一步：先共享，谁要修改某一页，才给它复制一份私有的。04 号脚本第 5 部分：一段 100 个单位的公共前缀分出 4 个分支，每个分支再各写 10 个单位（页大小 16）——各自复制前缀要 28 页；共享前缀 + 写时复制只要 10 页（前缀的 6 个完整页只存一份，最后那个没写满的页被每个分支复制了一次，共 4 次）。

操作系统的 fork() 就是这样创建子进程的（P1 讲过的”子进程有自己的内存”，物理上一开始是共享的）。LLM 推理里，同一个提示词的多个采样分支、束搜索的多个候选，就是用这个办法共享前缀的 KV 缓存（第 24 讲）。实现上需要给每个物理页维护一个引用计数：分支释放时计数减一，减到 0 才真正回收。

4.6 预告：KV 缓存怎样分配

把上面的想法用到 LLM 推理上（04 号脚本第 6 部分）：1000 个请求，提示词 50–499 个 token，输出长度事先未知（平均约 200、上限 2048），显存能放 200,000 个 token 的 KV 缓存：

按最大长度预留时，八成显存是”以防万一”的空位；按需分页时几乎全部用上，能同时服务的请求数是前者的近 5 倍——批更大，吞吐量就更高（§2.4）。vLLM 的论文正是从”已有系统的 KV 缓存显存大量被浪费”这个观察出发，把操作系统的分页搬到了 KV 缓存上（第 24 讲）。

5. 网络 · Networking

5.1 α-β 模型

发一条大小为 $n$ 字节的消息，时间近似为

$\alpha$ 是固定延迟（软件栈、同步、网络往返），和消息大小无关；$\beta$ 是带宽。有效带宽 $n / T(n)$ 在 $n = \alpha\beta$ 时达到峰值的一半。05 号脚本第 1 部分（量级）：

小消息时时间几乎全是 α：在 InfiniBand 上发 1 KB 只能用到峰值的 0.4%。带宽越高的连接，要用满它需要的消息反而越大。

5.2 ⏱ 本机实测

05 号脚本第 2 部分用一对本地 socket 在两个线程之间传消息（操作系统内核负责搬运），用最小二乘拟合 α 和 β：64 字节的消息每条约 0.75 μs、有效带宽约 0.08 GB/s；4 MiB 的消息有效带宽约 33 GB/s；拟合得 α ≈ 0.7 μs、β ≈ 33 GB/s（⏱）。这两个线程在同一台机器的内存里交换数据，所以 α 很小、带宽接近内存复制的速度；跨机器的网络要经过网卡和交换机，α 是几微秒（RDMA）到几十微秒（TCP）。但”固定开销 + 大小 / 带宽”这个形状是一样的。

5.3 分桶：把小消息攒成大消息

反向传播会产生成百上千个梯度张量。05 号脚本第 3 部分：用 InfiniBand（α = 5 μs、50 GB/s）发送 1000 个 100 KB 的张量（共 100 MB）：

但只发一个大桶有代价：要等所有梯度都算完才能开始发，没法和反向计算重叠（§3.5）。PyTorch DDP 默认把梯度攒成约 25 MB 一个桶：既摊薄了 α，又能边算边发（第 15 讲）。

5.4 拓扑与集合通信

多块 GPU 之间怎样连？同一台服务器里的 8 块 GPU 通常通过 NVLink 交换芯片（NVSwitch）两两全速互连；服务器之间通过网卡和交换机组成多层网络。在这样的拓扑上，“所有人把各自的梯度加起来、每人都拿到结果”（all-reduce）有不同的组织方式。05 号脚本第 4 部分用 α-β 模型比较了两种（α = 5 μs、50 GB/s）：

• 环形：每个参与者只和左右邻居通信，数据切成 N 份轮流传，每人总共发送约 2S 的数据——和 N 无关，带宽利用率最好；但要走 2(N − 1) 步，每步都付一次 α。
• 树形：只走 2·log₂N 层，但每层都要传整条消息。

所以大消息（梯度）用环形，小消息、参与者很多时用树形。NCCL 会根据消息大小和拓扑自动选择算法（还有更多变体）。第 14 讲会一步步推导环形 all-reduce，并在多个进程之间真的跑一遍。

6. 小结 · Summary

• 存储层次：越靠近计算越小越快。L1 约 1 ns、主内存约 100 ns、SSD 几十微秒、网络往返微秒到毫秒；带宽也分层（HBM 3.35 TB/s 对 PCIe 32 GB/s）。程序靠局部性让数据待在快的那几层；数据以缓存行为单位搬运，跳着读不省时间，随机读比顺序读慢数倍。GPU 靠大量线程隐藏延迟，并让程序员手工管理共享内存（分块）。
• 延迟 vs 吞吐量：Little 定律把两者联系起来。流水线的吞吐量由最慢的工序决定，开头结尾有气泡。排队论：时延 ∝ 1/(1 − 负载)，接近满载时平均和尾部时延都会爆炸，所以要留余量、看 p99。攒批把固定开销摊给整批，用一点延迟换几倍吞吐量——LLM 解码正是这种情形。
• 并发：线程共享内存、进程不共享；Python 的 GIL 让纯 Python 的线程不能并行计算，但能重叠等待。没有保护的”读-改-写”会竞争、丢失更新；锁和原子操作让它不可分割（原子加法不保证顺序）。计算和通信由不同硬件执行时可以重叠，总时间由较慢的那个决定。
• 虚拟内存：页表把虚拟页映射到物理页，带来隔离和灵活；按需分页让”申请”不等于”占用”。连续分配会产生外部碎片，分页消除了它，代价是内部碎片和页表；写时复制让共享很便宜。把这些搬到 KV 缓存上，就是 vLLM 的 PagedAttention。
• 网络：α-β 模型——小消息被固定延迟主导，要分桶；大消息被带宽主导。all-reduce 的环形算法带宽最优，树形步数最少。

7. 常见误区 · Common pitfalls

1. “读的数据少了，时间就成比例地少。” 只要还要碰到同样多的缓存行（或 GPU 的内存事务），时间几乎不变。
2. “内存访问的速度是固定的。” 取决于数据在哪一级（L1 还是 DRAM 差 100 倍）以及访问模式（顺序还是随机差数倍）。
3. “吞吐量高 = 延迟低。” 两者常常冲突：攒批提高吞吐量，却会增加单个请求的延迟。
4. “服务器跑到 95% 负载很高效。” 排队论说此时平均时延是空载时的 20 倍，p99 更夸张。
5. “加速任何一道工序都能让整体更快。” 只有加速瓶颈才有用。
6. “Python 里多开几个线程，计算就能并行。” 有 GIL 时纯 Python 的计算不能并行；要么用多进程，要么让计算在释放 GIL 的 C/C++ 代码里进行。
7. “x += 1 是一步操作。” 它是读、加、写三步，多个线程同时做会丢失更新。
8. “申请了内存就占用了内存。” CPU 上有按需分页，申请不等于占用；但 GPU 的 cudaMalloc 申请多少就占多少。
9. “分页没有浪费。” 没有外部碎片，但有内部碎片（每块最后一页没用满）和页表的管理开销。
10. “带宽 50 GB/s，发 1 KB 就是 20 纳秒。” 还有几微秒的固定延迟 α，小消息几乎全是 α。

8. 练习 · Exercises

练习 1（存储层次）。 一个程序随机访问一个 1 GB 的表 1 亿次，每次读 4 字节。按 §1.2 的量级，大约要多久？如果这 1 亿次访问是顺序的（读完整张表的一部分），大约要多久？

参考答案：随机访问几乎每次都落在主内存、要等一次延迟：$10^8 \times 100$ ns = 10 秒（真实 CPU 能同时发出多个读取，会快几倍，但量级如此）。顺序读 $4 \times 10^8$ 字节，按约 100 GB/s 的内存带宽约 4 毫秒。差了三个数量级——访问模式比访问次数更重要。

练习 2（缓存行）。 缓存行 64 字节，一个 float32 数组按 stride = 8 读取（每 32 字节读一个）。和 stride = 1 相比，从内存搬运的字节数是多少？和 stride = 32 相比呢？

参考答案：stride = 8 时每 32 字节读一个，每个 64 字节的行仍然要读 2 个数，所以每一行都要搬：字节数和 stride = 1 一样。stride = 32（每 128 字节读一个）时，每隔一行才碰到一次，搬运的字节数是前两者的一半。

练习 3（Little 定律）。 一个推理服务每秒完成 40 个请求，平均每个请求从进来到返回要 3 秒。平均有多少个请求同时在系统里？如果每个请求平均占 0.5 GB 的 KV 缓存，需要多少显存？

参考答案：$40 \times 3 = 120$ 个；$120 \times 0.5 = 60$ GB。如果想把延迟降到 1.5 秒而吞吐量不变，同时在系统里的请求就只有 60 个——延迟、吞吐量和显存是绑在一起的。

练习 4（流水线）。 一个模型被切成 4 段放在 4 块 GPU 上（流水线并行），每段的前向耗时都是 10 ms。一个批次切成 m 个微批次。(a) m = 1 时，每块 GPU 有多少时间在空等？(b) m = 16 时呢？

参考答案：用 §2.2 的公式，总时间 = 4 × 10 + (m − 1) × 10 ms。(a) m = 1：总时间 40 ms，每块 GPU 只忙 10 ms，空等 75%。(b) m = 16：总时间 190 ms，每块 GPU 忙 160 ms，空等 30/190 ≈ 15.8%。（这里只算了前向；第 16 讲会把反向也算进来。）

练习 5（排队）。 一个服务台平均处理一个请求要 50 ms。按 M/M/1 公式，要让平均时延不超过 200 ms，负载最多能到多少？此时每秒能处理多少个请求？

参考答案：$50 / (1 - \rho) \le 200$ ⇒ $\rho \le 0.75$；吞吐量 $= 0.75 / 0.05 = 15$ 个/秒（而满载的产能是 20 个/秒）。为了时延达标，四分之一的产能必须空着。

练习 6（攒批）。 解码一步的耗时是 30 ms（读权重）+ 0.2 ms × 批大小。批大小 1 和 64 时，每秒分别能生成多少个 token？每个请求每秒能拿到几个 token？

参考答案：批 1：每步 30.2 ms，33 token/秒，每个请求 33 token/秒。批 64：每步 42.8 ms，64 / 0.0428 ≈ 1495 token/秒，每个请求约 23 token/秒。总吞吐量涨了约 45 倍，每个请求的速度只慢了约 30%。

练习 7（竞争条件）。 两个线程各执行”读-加-写”两次（即各给计数器加 2，共 6 步）。最终 x 最小可能是多少？给出一个这样的交错。

参考答案：最小是 2。例如：A 读（0）；B 读（0）、加、写（1）；B 读（1）、加、写（2）；A 加、写（1）——此时 x 被 A 覆盖成 1；A 读（1）、加、写（2）。最终 2。（可以把 interleavings 用在两个各 6 步的序列上验证：共 924 种交错，最终 x 为 2、3、4 的分别有 702、216、6 种——只有 6 种是正确的 4。）

练习 8（页表）。 页大小 16 KiB，一个进程的页表把虚拟页 3 映射到物理页 77。虚拟地址 0xC123 对应的物理地址是多少？

参考答案：16 KiB = 0x4000。0xC123 = 3 × 0x4000 + 0x123，虚拟页号 3、偏移 0x123。物理地址 = 77 × 0x4000 + 0x123 = 0x134000 + 0x123 = 0x134123。

练习 9（碎片）。 一个 KV 缓存系统每页 16 个 token，平均每个请求的序列长度 700 个 token。内部碎片大约是多少？如果改成每页 256 个 token 呢？

参考答案：如果序列长度分布比较分散，每个请求的最后一页平均浪费约半页：页大小 16 时约 8 个 token（约占 700 的 1.1%），256 时约 128 个 token（约 18%）。对恰好 700 个 token 的序列：页大小 16 时用 44 页 = 704 个位置、浪费 4 个；256 时用 3 页 = 768 个位置、浪费 68 个（约 9%）。无论按哪种方式算，大页的浪费都高一个数量级。这就是 vLLM 选择小页的原因。

练习 10（写时复制）。 一个 1000 个 token 的提示词，用”并行采样”生成 8 个回答，每个回答 200 个 token。每页 16 个 token。不共享前缀和共享前缀（写时复制）时，KV 缓存各需要多少页？

参考答案：不共享：每个分支 1200 个 token = 75 页，共 600 页。共享：前缀 1000 个 token = 62.5 页，即 62 个满页 + 1 个用了 8 个位置的半页；62 个满页只存一份，那个半页在每个分支第一次写入时被复制，于是每个分支的私有部分是”复制的半页（8 + 8 个 token 填满）+ 剩下 192 个 token 的 12 页” = 13 页。总共 62 + 8 × 13 = 166 页，约为不共享时的 28%。

练习 11（α-β）。 一条连接 α = 10 μs、带宽 25 GB/s。(a) 发 1 MB 要多久？有效带宽是多少？(b) 多大的消息能达到一半带宽？

参考答案：(a) 10 μs + 1 MB / 25 GB/s = 10 + 40 = 50 μs，有效带宽 20 GB/s（峰值的 80%）。(b) α × β = 10 μs × 25 GB/s = 250 KB。

练习 12（思考题：瓶颈在哪）。 一台推理服务器的监控显示：GPU 利用率只有 30%，CPU 的一个核心 100% 忙，其余核心空闲。最可能的瓶颈是什么？可以怎样改进？

参考答案：最可能是 Python 层的调度 / 预处理（被 GIL 限制在一个核上）跟不上 GPU，GPU 大部分时间在等下一批数据。改进：把调度和计算重叠起来（CPU 准备下一批时 GPU 在算这一批，§3.5）；把预处理（分词等）放到多个进程里（§3.2）；减少每一步的 Python 开销（把小操作合并、用 CUDA Graph 等）。第 22 讲 SGLang 的”零开销调度器”正是针对这个问题。

9. 延伸阅读 · Further reading

• 体系结构：Bryant & O’Hallaron, Computer Systems: A Programmer’s Perspective（CS:APP）第 6 章（存储层次、缓存、局部性）；Ulrich Drepper, What Every Programmer Should Know About Memory（长文）。
• 操作系统：Arpaci-Dusseau, Operating Systems: Three Easy Pieces（OSTEP，免费在线）——“Virtualization”部分（地址翻译、分页、TLB）和”Concurrency”部分（线程、锁、竞争条件）。
• 排队论：Mor Harchol-Balter, Performance Modeling and Design of Computer Systems 第 1–7 章；Little (1961) 的原始论文。
• 延迟数字：Jeff Dean 的 “Latency Numbers Every Programmer Should Know”（有很多按年份更新的版本）。
• 网络与集合通信：Thakur, Rabenseifner & Gropp (2005) Optimization of Collective Communication Operations in MPICH（α-β 模型下各种 all-reduce 算法的分析）；NVIDIA NCCL 文档。
• 预告：Kwon et al. (2023) Efficient Memory Management for Large Language Model Serving with PagedAttention（第 24 讲的阅读材料，引言部分把 KV 缓存与操作系统分页的类比讲得很清楚）。

10. 下一篇预告 · Next

四篇前置讲到此结束。回到主线：第 2 讲（GPU 编程基础一） 从原课 slides 的文本分类网络出发（P3 §4 实现过的那个），看它怎样拆成矩阵乘法、逐元素运算和归约；再看一台 GPU 服务器由哪些部件组成（本讲 §1.2 的带宽表在那里会变成具体的硬件），GPU 由哪些 SM 组成、为什么要同时跑上万个线程来隐藏显存延迟（本讲 §1.7），以及一个 CUDA 内核是怎样被切成网格、线程块和线程束来执行的。我们会写一个 Python 的 SIMT 模拟器，让 P1 里读过的 CUDA 代码真正”跑”起来，并逐项统计它的内存访问。