前置讲 P5 · 网络与集合通信 · Networks and Collective Communication

定位：为没有分布式系统背景的读者补充的前置讲，原课没有对应的课次。它支撑第 4 讲（分布式推理：切分矩阵与张量并行，原课作业 3）、第 5 讲（解耦式推理：KV 传输）和第 7 讲（KV cache 的分层存储与搬运）。建议先读 P1 的 §4（延迟、带宽与 Little 定律）。 依据：J. Austin et al., How to Scale Your Model 第 2 章（TPU 与 ICI）、第 3 章（切分矩阵与集合通信的代价）、第 12 章（GPU 的网络：NVLink、NVSwitch、InfiniBand、SHARP）；R. Thakur, R. Rabenseifner, W. Gropp, Optimization of Collective Communication Operations in MPICH（2005）；P. Patarasuk and X. Yuan, Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations（2009）；M. Shoeybi et al., Megatron-LM（2019）；DeepSeek-AI, DeepSeek-V3 Technical Report（2024）§3.2、§3.4。 配套代码 Code：code/prereq5/（numpy；共享模块 comm_sim.py 是一台”虚拟集群”：真实数据 + 逐消息记账，+ 5 个脚本，每个不到 1 秒） 预计阅读时间：2.5 小时（含运行代码）

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

0.1 为什么需要这一讲

第 1 讲算过：Llama-3.1-70B 的 BF16 权重有 141 GB，一块 80 GB 的 H100 放不下；即使放得下，decode 受限于带宽，一块 H100 每秒最多把权重读二十几遍。把模型切到 8 块 GPU 上，容量和带宽都乘以 8——但芯片之间从此要交换数据。这笔账算得好，8 块 GPU 接近 8 倍快；算不好，通信会吃掉大半时间（§7：张量并行的 decode，通信可以和计算一样长）。

后面几讲都建立在这一讲的语言上：

0.2 学习目标 Learning goals

1. 用 α–β 模型估算一次通信的时间；说出半带宽点 $n_{1/2} = \alpha\beta$ 的含义，判断一个通信是延迟主导还是带宽主导。
2. 比较交换机、环、torus、两级网络的端口数、直径和对分带宽；知道 GPU 集群（NVLink + InfiniBand）和 TPU（ICI torus）的网络长什么样。
3. 准确说出 broadcast、reduce、all-reduce、reduce-scatter、all-gather、all-to-all 的输入和输出；会用”all-reduce = reduce-scatter + all-gather”这类恒等式。
4. 推导 ring、递归倍增、Rabenseifner、二叉树 all-reduce 的时间公式；知道每种算法适合什么消息大小和规模。
5. 解释拓扑映射、对分带宽、层次化算法为什么重要。
6. 给一个 LLM 推理配置算通信账：张量并行的 all-reduce、MoE 的 all-to-all、解耦式推理的 KV 搬运。

0.3 本讲地图 Map

§1  为什么要多芯片，为什么通信是代价
§2  链路：α–β 模型；延迟主导与带宽主导；常见链路                         ← 代码 01
§3  拓扑：交换机、环、torus、两级网络；直径与对分带宽；真实系统            ← 代码 01
§4  集合通信：语义、恒等式、每个设备至少要传多少字节                      ← 代码 02
§5  all-reduce 的算法：ring、递归倍增、Rabenseifner、树、交换机内归约      ← 代码 03
§6  拓扑感知：映射、二维算法、all-to-all 与对分带宽、层次化 all-reduce     ← 代码 04
§7  LLM 推理里的通信账：张量并行、MoE、KV 搬运、重叠                      ← 代码 05
§8  通信库与硬件：NCCL、自定义 all-reduce、SHARP、DeepEP
§9–13  小结、常见误区、练习（含答案）、延伸阅读、和正课的联系

0.4 关于数字 · About the numbers

• 本讲的实验数字都来自 comm_sim 的模拟和 α–β 公式，每次运行完全相同。
• 链路带宽取公开规格（单向）：NVLink 4 每块 H100 450 GB/s（18 条 × 25 GB/s）、InfiniBand NDR 每块网卡 50 GB/s、TPU v5e 每条 ICI 链路 45 GB/s 等。链路延迟 α 是量级上的假设值（NVLink 2 µs、InfiniBand 5 µs、ICI 1 µs），真实的有效延迟取决于软件栈，可能大一个数量级（§5.6）。
• 所以：模拟的时间用来比较算法和拓扑、理解趋势，不用来预测真实系统的绝对时间。引用别人的测量时注明出处。

1. 为什么要多芯片，为什么通信是代价 · Why multiple chips

推理把模型切到多块芯片上，有三个理由：

1. 容量：权重 + KV cache 放不进一块芯片（70B 的 BF16 权重 141 GB > 80 GB）。
2. 带宽：decode 每一步要把权重读一遍（第 1 讲 §4）。8 块 GPU 各读 1/8，总带宽 ×8，每步快 8 倍——这是降低单用户延迟的主要手段。
3. 算力：prefill 和大批量的 decode 受限于算力，多芯片同样 ×8。

代价是：每块芯片只有一部分权重，算出来的是部分结果，必须和别人交换数据才能继续——这就是通信。张量并行每一层都要把各块芯片的部分和加起来（all-reduce），MoE 要把 token 送到持有对应专家的芯片（all-to-all），解耦式推理要把 prefill 算好的 KV cache 送到 decode 的机器（点对点）。

通信的代价由两件事决定：网络有多快（§2–§3），以及用什么算法组织这些数据交换（§4–§6）。

2. 链路：α–β 模型 · Links

代码：01_links_and_topologies.py

2.1 α–β 模型

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

• $\alpha$：启动延迟——不管消息多小都要付的固定时间（软件开销、同步、信号在线路上的传播、经过交换机的转发）。
• $\beta$：带宽——每秒能传多少字节。

实际拿到的带宽是 $n / T(n)$。两项相等的消息大小

叫半带宽点：消息比它小，延迟占大头（延迟主导）；比它大，带宽占大头（带宽主导）。这和 P1 §4 的 Little 定律是同一件事的两种说法：要跑满带宽，就要有足够多的数据”在路上”。

2.2 常见链路

代码 01 演示 1：

两个结论贯穿全讲：

• 链路越快，半带宽点越大。NVLink 要 900 KB 以上的消息才能用上一半带宽。带宽涨得比延迟降得快，“小消息”的门槛不断提高。
• LLM 推理里两种消息都有：decode 时张量并行的 all-reduce 只有几 KB 到几 MB（延迟主导，§7.1）；prefill 的激活、KV cache、权重加载动辄几十 MB 到几 GB（带宽主导）。前者要少步数，后者要少字节。

2.3 scale-up 与 scale-out

GPU 集群里有两种很不一样的网络：

• scale-up（纵向）：一个”域”里的芯片用专门的高带宽、低延迟互连直接连起来，像一台大机器。NVIDIA 的 NVLink + NVSwitch：一个 DGX H100 节点 8 块 GPU，每块 18 条 NVLink、每条 25 GB/s（单向），一共 450 GB/s；GB200 NVL72 把这个域扩到 72 块 GPU、每块 900 GB/s。TPU 的 ICI 也属于这一类。
• scale-out（横向）：域与域之间用 InfiniBand 或以太网连起来，每块 GPU 一块网卡（ConnectX-7，400 Gb/s = 50 GB/s）。带宽只有 NVLink 的 1/9，延迟更大，但能连成几千、几万块 GPU。

这条”带宽断崖”是 GPU 集群上设计并行方式的头号约束：通信频繁的切分（张量并行、专家并行）尽量留在 scale-up 域里（§7.3）。

3. 拓扑 · Topologies

3.1 几种基本拓扑

拓扑是链路的连接方式。三个指标：每个设备几个端口（成本）、直径（任意两个设备之间最多几跳，决定最坏的延迟）、对分带宽（bisection bandwidth：把设备分成两半，两半之间能同时传多少，取最坏的分法——决定”人人对人人”的通信能多快）。代码 01 演示 2（为了公平，所有拓扑的单链路带宽都取 45 GB/s；两级网络用 NVLink + IB 的真实组合）：

• 交换机：任意两个设备 2 跳可达，对分带宽随设备数线性增长。代价在交换机本身：端口数随设备数增长，大交换机又贵又耗电。NVSwitch 就是这样连接一个节点的。
• 环：每个设备只有 2 个端口，便宜；但直径 $p/2$，对分带宽只有 2 条链路，不随 $p$ 增长。
• 二维 / 三维 torus（TPU 的做法：v5e 是 16×16 的二维 torus，v5p 是三维 torus）：每个设备 4（或 6）个端口，不需要交换机，可以做得很大；直径 $\sim\sqrt p$，对分带宽 $\sim \sqrt p$。
• 两级网络 / 胖树（GPU 集群的做法）：节点内 NVSwitch；节点之间是 InfiniBand 的胖树（fat tree）——叶交换机、脊交换机层层向上，每一层的总带宽相同，保证”满对分带宽”。How to Scale Your Model 第 12 章描述的 1024 块 H100 的 DGX SuperPOD：每 32 个节点（256 块 GPU）一个”可扩展单元”，下挂 8 台叶交换机，4 个单元再由 16 台脊交换机连起来。跨节点的对分带宽按网卡算，每块 GPU 只有节点内的 1/9。

3.2 点对点：距离和带宽

代码 01 演示 3 发一条消息：

大消息只看路径上最慢的链路（数据像流水一样穿过中间的芯片）；小消息几乎只看延迟，跳数开始要紧了——所以 torus 上要尽量只和邻居通信。

4. 集合通信 · Collective communication

代码：02_collectives_semantics.py

4.1 每一种在做什么

集合通信是一组设备一起完成的数据交换。代码 02 演示 1：4 个设备，设备 $d$ 一开始持有 $[10d, 10d+1, 10d+2, 10d+3]$：

• broadcast：根的数据复制给所有人。reduce：逐元素求和，结果只在根上。
• all-reduce：所有人都得到逐元素的和。张量并行每层都要做（§7）。
• reduce-scatter：和也求了，但每个设备只拿到一块——all-reduce 的”前一半”。
• all-gather：每个设备贡献一块，每个人都得到完整的拼接——all-reduce 的”后一半”。
• all-to-all：设备 $i$ 的第 $j$ 块发给设备 $j$。把数据排成矩阵（行 = 设备，列 = 块），all-to-all 就是转置。MoE 的专家并行用它分发 token。

4.2 恒等式

代码 02 演示 2 在 8 个设备上用真实数据验证：

• all-reduce = reduce-scatter + all-gather。ring all-reduce 正是这么实现的；拆开以后中间可以插入别的计算——“序列并行”把 LayerNorm 这类逐 token 的运算放在两半之间，只在 $1/p$ 的数据上算（第 4 讲）。
• all-to-all 做两次回到原样（转置的转置）：MoE 先 all-to-all 分发（dispatch），专家算完再 all-to-all 合并（combine）。
• broadcast = scatter + all-gather（Van de Geijn 的算法）：每条链路只传约 2 份数据，而二项树要传 $\log_2 p$ 份完整数据。小消息（32 KB）时它更慢（16.1 vs 6.2 µs，步数多），大消息（8 MB）时更快（49 vs 62 µs）。同一个语义，不同的实现，适合不同的消息大小——MPI、NCCL 都按消息大小切换算法。

4.3 每个设备至少要传多少字节

设每个设备有 $n$ 字节。无论用什么算法：

• all-gather / reduce-scatter：每个设备至少要收（发）$\frac{p-1}{p} n$。
• all-reduce：可以证明每个设备至少要发 $2\frac{p-1}{p} n$（Patarasuk & Yuan 2009）——约等于 $2n$，和 $p$ 几乎无关。
• all-to-all：每个设备要把 $\frac{p-1}{p} n$ 发给别人。

代码 02 演示 3 数了每种算法里每个设备实际发出的字节（$p = 8$）：

ring 和 Rabenseifner 达到下界——带宽最优；区别在步数。递归倍增字节多、步数最少。树和朴素算法的毛病是不均匀：根附近的设备忙死，其他设备闲着。all-reduce 的字节是 all-gather 的 2 倍，所以时间也约 2 倍（How to Scale Your Model 第 3 章的经验法则）。

5. all-reduce 的算法 · All-reduce algorithms

代码：03_allreduce_algorithms.py

5.1 ring：带宽最优

把 $p$ 个设备排成一个环，每个设备的数据切成 $p$ 块：

1. reduce-scatter 阶段（$p-1$ 步）：每一步，每个设备把一块部分和传给下一个，下一个加上自己的那一块。$p - 1$ 步之后，每个设备持有某一块的完整和。
2. all-gather 阶段（$p-1$ 步）：每一步，每个设备把最近收到的完整块传给下一个。

每一步每个设备发 $n/p$ 字节，一共 $2(p-1)$ 步：

带宽项达到下界，而且所有链路同时在忙、每个设备只和邻居说话——非常适合环和 torus。缺点是步数 $\propto p$。

5.2 递归倍增、Rabenseifner、树、交换机内归约

• 递归倍增（recursive doubling，$p$ 是 2 的幂）：第 $k$ 步，设备 $i$ 和 $i \oplus 2^k$（异或）交换完整数据并相加。$\log_2 p$ 步：$T = \log_2 p\,(\alpha + n/\beta)$。
• Rabenseifner：递归减半的 reduce-scatter（每一步和伙伴交换”一半的一半”）+ 递归倍增的 all-gather。$T = 2\log_2 p\,\alpha + 2\frac{p-1}{p}\frac{n}{\beta}$——步数像树，字节像 ring。
• 二叉树：二项树归约到根 + 二项树广播，$2\lceil\log_2 p\rceil$ 步，每步完整数据：$T = 2\lceil\log_2 p\rceil(\alpha + n/\beta)$。
• 朴素：所有人发给根、根再发给所有人：$T = 2(\alpha + (p-1)n/\beta)$——根的端口是瓶颈。
• 交换机内归约（in-network reduction，NVIDIA 的 SHARP 一类）：每个设备把数据发给交换机，交换机边收边求和、再组播回去，上下行流水起来：$T \approx \alpha + n/\beta$——理论上把大消息的 all-reduce 减半。How to Scale Your Model 第 12 章报告，实际（NCCL 2.27.5）只快了约 30%。

comm_sim 用真实数据跑了这六种算法：结果都等于 numpy 求和，模拟时间和上面的公式的最大相对差是 3.3e-06（浮点误差）。

5.3 谁最快：看消息大小

代码 03 演示 1（8 块 GPU、NVLink 交换机、$\alpha = 2$ µs）：

• 小消息：步数少的赢。最小的消息连朴素算法（2 步）都赢了；几百 KB 到 1 MB 递归倍增最快。ring 的 14 步光延迟就是 28 µs。
• 大消息：字节少的赢。ring 和 Rabenseifner 每个设备只发 1.75 $n$，递归倍增发 3 $n$。递归倍增和 ring 的交叉点：

• Rabenseifner 两头都接近最优。没有一个算法在所有大小上都最好，所以 NCCL、MPI 都按消息大小和拓扑切换算法。

5.4 设备变多：ring 的步数变成灾难

代码 03 演示 2（InfiniBand，$\alpha = 5$ µs）：

64 KB、512 个设备时，ring 要 1022 步，光延迟就超过 5 ms；递归倍增只要 9 步。256 MB 时，ring 和 Rabenseifner 的时间几乎不随 $p$ 变化——How to Scale Your Model 说”带宽主导时，集合通信的时间只取决于数组大小和带宽，不取决于设备数”，就是这个意思。

5.5 广播与”切块流水”

代码 03 演示 4 把 8 MB 广播给 7 个设备（ICI 链路，$n_{1/2}$ = 45 KB）：朴素 1.25 ms、二项树 536 µs；流水线链（切成 $k$ 块沿一条链传，$p - 2 + k$ 步）在 $k = 32$ 时只要 249 µs，是二项树的 46%、下界 $n/\beta$ 的 1.40 倍。最优块数可以求出来：

块太少，流水线”灌满”之前要等；块太多，每块一个 α。消息不够大时流水线反而吃亏：同样的算法在 NVLink 上、4 MB（只有 $n_{1/2}$ 的 4.4 倍）时，最好的流水线要 41.56 µs，二项树只要 32.67 µs。“切块 + 流水”让所有链路同时忙起来——ring all-reduce、NCCL 的分块协议、流水线并行的 micro-batch 都是这个思想。

5.6 模型 vs 实测

NCCL 报告两个指标：算法带宽 algbw = $n$ / 时间；总线带宽 busbw = algbw × $2(p-1)/p$（换算成每条链路实际承载的带宽，和链路规格可比）。代码 03 演示 3 把我们的模型和 How to Scale Your Model 第 12 章给出的 8×H100（关闭 SHARP）实测对照：

大消息时模型和实测差得不多（实测只能到规格的约 80%）；但在 58 MB 这样的中等消息上，模型乐观得多。要让 α–β 模型在 58 MB 时也只有 150 GB/s，每一步的”有效 α”得是约 32 µs——比链路本身的延迟大一个数量级：真实实现里还有同步、分块、协议、占用 SM 等开销。模型告诉你往哪个方向优化（少步数还是少字节），绝对时间要用实测校准。

6. 拓扑感知与层次化 · Topology-aware collectives

代码：04_topology_and_hierarchy.py

6.1 映射：逻辑环放在哪里

ring 算法需要一个”逻辑环”。在 torus 上，哪个逻辑编号放在哪块物理芯片上，决定了环上的邻居在物理上隔几跳。代码 04 演示 1（16 个设备、每条链路 45 GB/s，ring all-reduce 64 MB）：

蛇形映射让每一对邻居都物理相连，达到理想时间；按行映射多走的那一跳恰好用的是空闲链路，只慢 2%；随机映射让很多消息的路径重叠在同一条链路上，慢了一倍。JAX 的 device mesh、MPI 的拓扑感知映射都在处理这个问题。

二维 all-reduce：先在每一行内 reduce-scatter、再在每一列内 reduce-scatter，然后反过来 all-gather。字节和单环一样（大消息时一样快），步数从 $2(p-1) = 30$ 降到 $2(a-1) + 2(b-1) = 12$——64 KB 时从 32.67 µs 降到 14.67 µs。TPU 的多维 torus 就是按维度做集合通信的。

6.2 all-to-all 与对分带宽

all-to-all 是”人人对人人”：一半设备要发给另一半的数据，必须穿过中线。两个下界（每个设备有 $n$ 字节），取较大的：

代码 04 演示 2（每个设备 16 MB）：

交换机上 all-to-all 几乎跑到”出口”下界——每个端口一直满速；环上被对分带宽卡死，比交换机慢约 16 倍；torus 介于两者之间。这就是为什么 MoE 的专家并行偏爱大的 NVSwitch 域（GB200 NVL72），而 TPU 上的 all-to-all 相对更贵（How to Scale Your Model 第 12 章：节点内的 GPU all-to-all 理论上比 TPU 快一倍）。环和 torus 上模拟比下界高 2–4 倍，来自直接算法的步间同步和流量不均——更好的 all-to-all 算法会按拓扑重新安排每一步的发送对象。

6.3 层次化 all-reduce

两级网络上，节点内 NVLink 快（450 GB/s）、节点间网卡慢（50 GB/s）。扁平 ring把所有 GPU 排成一个大环：每一步都要等跨节点的那条慢链路，整个环按网卡的速度走。层次化：

1. 节点内 reduce-scatter（NVLink）：每块 GPU 得到本节点 1/8 的部分和；
2. 节点间 all-reduce：节点内编号相同的 GPU 组成一个环（8 个环同时，每个只处理 $n/8$，各走各的网卡）；
3. 节点内 all-gather（NVLink）。

代码 04 演示 3：

大消息：层次化让跨节点的流量只剩 $2\frac{N-1}{N}\cdot\frac{n}{8}$，8 块网卡同时工作。小消息：扁平 ring 有 $2(8N-1)$ 步、几乎每步都要付网卡的 α，层次化只有 $2 \times 7$ 步走 NVLink、$2(N-1)$ 步走网卡——加速反而随节点数变大。NCCL 在多节点上就是这样做的；“rail-optimized”网络（每个节点里第 $k$ 块 GPU 的网卡接到同一组交换机）让那 8 个节点间的环各走各的路。

7. LLM 推理里的通信账 · Communication in LLM inference

代码：05_communication_in_llm_inference.py

7.1 张量并行的 decode：延迟主导

Megatron 式张量并行（第 4 讲）：每层的注意力输出和 MLP 输出各做一次 all-reduce，消息 = $B \times d_\text{model} \times 2$ 字节。Llama-3.1-70B（80 层、$d_\text{model}$ = 8192）在一个 8×H100 节点上，每步 160 次 all-reduce。计算 / 访存时间用第 1 讲 llm_math.decode_step（理想切分，不含通信）：

（括号里是通信占”计算 + 通信”的比例，假设两者不重叠。）

• 每次 all-reduce 只有十几 KB 到几 MB，全部在延迟主导的区间。B = 1 时，ring 的 160 × 14 步光延迟就 4.5 ms，和整个计算 / 访存时间差不多。
• 步数少的算法（递归倍增；实际引擎里的”one-shot / two-shot”自定义 all-reduce，直接通过 NVLink 读写彼此的显存）把通信降到原来的约 22%。vLLM、TensorRT-LLM、SGLang 都为小消息专门写了 all-reduce 内核。
• α 的影响巨大：有效 α 从 2 µs 变成 20 µs，B = 1 时通信占比从 16% 变成 65%（递归倍增）。这也是为什么 decode 的张量并行不是切得越细越好，以及为什么第 11 讲的 megakernel 要把通信也融合进同一个内核。

7.2 张量并行的 prefill：带宽主导，可以重叠

prefill 一条提示时，消息变成 $n_\text{tok} \times 8192 \times 2$ 字节：

每个 token 的通信带宽时间约 10.2 µs、线性层计算约 17.6 µs，两者都 $\propto$ token 数，比值 58% 是一个常数——这就是第 1 讲 §3.10 的网络 roofline：通信时间 / 计算时间 = (每 token 的通信字节 / 带宽) / (每 token 的 FLOPs / 算力)。另外每次 prefill 有 4.48 ms 固定的 α（短提示时占比大），而注意力计算 $\propto n^2$（长提示时计算增长更快），所以比例从 107% 降到 45%。

prefill 的通信可以和计算重叠：把一层切成几块，前一块的 all-reduce 和后一块的矩阵乘法同时进行（第 4 讲）。只要通信 < 计算，理论上可以完全藏住。

7.3 为什么张量并行不出节点

把 TP 从 8 扩到 16（两个节点，B = 64）：每块 GPU 的计算 / 访存从 8.39 ms 减半到 4.20 ms，但每次 all-reduce 都多了跨节点的一段，每步通信从 5.13 ms 涨到 7.15 ms，合计只从 13.52 ms 降到 11.35 ms——远没有翻倍。所以实践中 TP 一般不超过一个 NVLink 域；更多的 GPU 用流水线并行、专家并行或多副本来扩展（第 4 讲）。

7.4 MoE 的 all-to-all

DeepSeek-V3 规模的 MoE（$d$ = 7168，每个 token 选 256 个专家里的 8 个，61 层里 58 层是 MoE——取自其技术报告）。专家并行时每个 MoE 层两次 all-to-all（分发、合并），每块 GPU 每层发出约 tokens × $k$ × $d$ × 字节 × $\frac{EP-1}{EP}$（每块 GPU 256 个 token）：

跨节点慢了约 10 倍（all-to-all 吃的是对分带宽，跨节点只有网卡的 50 GB/s）。DeepSeek-V3 的应对：分发用 FP8（合并仍用 BF16）；每个 token 最多发往 4 个节点，先经 InfiniBand 发到目标节点上编号相同的 GPU，再经 NVLink 转发（H800 上 NVLink 160 GB/s 约是 IB 的 3.2 倍）；prefill 时两个 micro-batch 交替，让 all-to-all 和计算重叠。这里还假设了专家选择均匀；实际的负载不均会让最忙的那块 GPU 决定 all-to-all 的时间（第 3、4 讲）。

7.5 解耦式推理的 KV 搬运

prefill 和 decode 放在不同的 GPU 上（第 5 讲），prefill 算完的 KV cache 要搬过去。Llama-3.1-70B 每 token 的 KV 是 327.68 KB（GQA，8 个 KV 头，BF16）：

8 块网卡并行时，搬运约是 prefill 时间的 4%–5%；只用一块网卡就是 9 倍。KV 还可以一层一层地发，和后面各层的计算重叠（DistServe、Mooncake 都这么做），暴露在首 token 延迟里的只有最后几层。模型结构直接决定这笔账：同样大小的模型如果用 64 个 KV 头的 MHA，KV 大 8 倍；用 FP8 存 KV 又能减半（P3、第 7 讲）。

8. 通信库与硬件 · Libraries and hardware

• NCCL（NVIDIA Collective Communications Library）：GPU 上集合通信的标准库。它根据拓扑（NVLink、PCIe、网卡）建立多个环和树（多个”channel”同时跑），按消息大小选择算法和协议。本讲的 ring、树、层次化都在其中。
• 自定义 all-reduce：小消息时 NCCL 的固定开销太大，vLLM、TensorRT-LLM 等为节点内的 all-reduce 写了专门的内核：利用 NVLink 让每块 GPU 直接读写其他 GPU 的显存，一步（one-shot）或两步（two-shot）完成——就是 §5.3 “步数少的赢”。
• SHARP / NVLink SHARP：交换机里的归约单元（§5.2）。Hopper 以后的 NVSwitch 和部分 InfiniBand 交换机支持。
• NVSHMEM 与 MoE 通信库：MoE 的 all-to-all 是稀疏、不规则的；DeepSeek 开源的 DeepEP 等库直接在 GPU 内核里发起通信（不经过 CPU），并把 NVLink 和 InfiniBand 叠加使用（§7.4）。
• MPI：高性能计算的老牌接口，集合通信算法（§5）大多先在 MPI 里被研究和实现（Thakur et al. 2005）。

9. 小结 · Summary

1. α–β 模型：$T = \alpha + n/\beta$。小于半带宽点 $\alpha\beta$ 的消息是延迟主导的（要少步数），大消息是带宽主导的（要少字节）。LLM 推理两种都有：decode 的 all-reduce 是前者，prefill、KV 搬运是后者。
2. 拓扑：交换机（2 跳、对分带宽 ∝ $p$、贵）、环（便宜、对分带宽恒定）、torus（介于两者）、两级网络（节点内快、节点间慢 9 倍）。all-to-all 吃对分带宽，ring all-reduce 只要一个环。
3. 集合通信：all-reduce = reduce-scatter + all-gather；all-to-all 是转置；all-reduce 每个设备至少发 $2\frac{p-1}{p}n$。
4. 算法：ring 带宽最优但 $2(p-1)$ 步；递归倍增 $\log_2 p$ 步但字节多；Rabenseifner 两头兼顾；交换机内归约理论上再减半。没有一个算法在所有消息大小上最好。
5. 拓扑感知：映射不好会让同一个算法慢一倍；按维度做能减少步数；两级网络上层次化 all-reduce 快 4–6 倍。
6. 推理的通信账：张量并行的 decode 通信可以和计算一样长（延迟主导，要少步数、小 α）；prefill 的通信可以被计算藏住；TP 不出节点；MoE 的 all-to-all 跨节点慢一个数量级；KV 搬运要多块网卡并行、逐层重叠。
7. 模型 vs 实测：α–β 模型指明方向，但真实的有效延迟比链路延迟大一个数量级，绝对时间要实测校准。

10. 常见误区 · Common pitfalls

1. “带宽高就快。” 小消息几乎只看延迟：NVLink 发 4 KB 拿到的带宽不到 1%（§2.2）。
2. “ring all-reduce 永远是最好的。” 它带宽最优，但小消息、大规模时步数是灾难（512 个设备、64 KB：5 ms vs 57 µs）。
3. “all-reduce 的时间随设备数线性增长。” 带宽主导时几乎不变（每个设备发约 $2n$）；延迟主导时才随步数增长。
4. “设备之间怎么编号无所谓。” 在 torus 上随机映射让 ring all-reduce 慢一倍（§6.1）。
5. “对分带宽决定一切。” 交换机上 all-to-all 受限于每个设备的出口（§6.2）。
6. “多加 GPU 做张量并行总是更快。” 跨节点后通信涨得比计算降得快（§7.3）。
7. “厂商的链路带宽就是集合通信能拿到的带宽。” 8×H100 的 all-reduce 在 58 MB 时实测总线带宽只有规格的约 1/3（§5.6）。

11. 练习 · Exercises

带 💻 的题可以用 comm_sim 验证。参考答案在每题后面。

练习 1（半带宽点）。InfiniBand NDR（β = 50 GB/s，α = 5 µs）的半带宽点是多少？发 25 KB 和 2.5 MB 时分别拿到多少带宽？

$n_{1/2} = 5\times10^{-6} \times 50\times10^{9} = 250$ KB。25 KB：$T = 5 + 0.5 = 5.5$ µs，实得 4.5 GB/s（9%）；2.5 MB：$T = 5 + 50 = 55$ µs，实得 45.5 GB/s（91%）。

练习 2（ring 的公式）。推导 $p$ 个设备 ring all-reduce 的时间公式。为什么每一步只发 $n/p$？

数据切成 $p$ 块。reduce-scatter 的 $p-1$ 步里，每一步每个设备把一块（$n/p$）传给下一个并累加；all-gather 的 $p-1$ 步里同样每步传一块。所有设备同时在发，每条链路每步承载 $n/p$。所以 $T = 2(p-1)(\alpha + \frac{n}{p\beta})$。每步只发一块，是因为每一块只需要”绕环一圈”（累加一圈 + 分发一圈），把数据切碎让所有链路同时工作。

练习 3（交叉点）💻。$p = 16$、NVLink（α = 2 µs、β = 450 GB/s）时，递归倍增和 ring 的交叉点在哪里？和 $p = 8$（7.92 MB）比，变大还是变小？

令 $\log_2 p(\alpha + n/\beta) = 2(p-1)\alpha + 2\frac{p-1}{p}n/\beta$：$4(\alpha + n/\beta) = 30\alpha + 1.875\,n/\beta$ → $2.125\,n/\beta = 26\alpha$ → $n = 26\alpha\beta / 2.125 \approx 11.0$ MB。变大了：设备多了，ring 的步数增长得比递归倍增快，要更大的消息才轮到 ring。用 t_formula("ring", 16, n, 2e-6, 450e9) 和 t_formula("rd", ...) 验证。

练习 4（all-gather）。8 块 H100（节点内 NVLink）对一个 bf16[1024, 16384] 的张量（按行切成 8 份）做 all-gather，带宽主导时要多久？

完整张量 $1024 \times 16384 \times 2 = 33.6$ MB。ring all-gather 每个设备收 $\frac{7}{8} \times 33.6$ MB = 29.4 MB，$/450$ GB/s ≈ 65 µs（加上 7α = 14 µs，约 79 µs）。How to Scale Your Model 第 12 章的同一道题给出约 65 µs（只算带宽）。

练习 5（all-to-all 的下界）。64 块 GPU 挂在一个无阻塞交换机上，每块 50 GB/s，每块有 64 MB 要做 all-to-all。两个下界各是多少？哪个起作用？

对分：$p\,n/4 = 64 \times 64$ MB / 4 = 1.024 GB 过中线，对分带宽 $32 \times 50 = 1600$ GB/s → 0.64 ms。出口：$\frac{63}{64} \times 64$ MB / 50 GB/s ≈ 1.26 ms。出口下界更大，起作用——无阻塞交换机的瓶颈在每个设备自己的端口。

练习 6（层次化）。4 个节点 × 8 块 GPU，all-reduce 512 MB。估算层次化算法各阶段的时间（只算带宽项）。

节点内 RS：$\frac{7}{8} \times 512$ MB / 450 GB/s ≈ 1.0 ms；节点间 AR（8 个环同时，每个处理 64 MB，4 个节点）：$2 \times \frac{3}{4} \times 64$ MB / 50 GB/s ≈ 1.92 ms；节点内 AG ≈ 1.0 ms。合计约 3.9 ms。扁平 ring 约 $2 \times \frac{31}{32} \times 512$ MB / 50 GB/s ≈ 19.8 ms，层次化快约 5 倍。

练习 7（TP 的通信账）💻。Llama-3.1-8B（32 层，$d_\text{model}$ = 4096）用 TP = 4、B = 16 做 decode。每步多少次 all-reduce？每次多大？用 ring 和递归倍增（NVLink，α = 2 µs）各要多久？

每步 64 次；每次 $16 \times 4096 \times 2 = 131{,}072$ 字节（131 KB），在 NVLink 上传一遍要 0.29 µs。ring（$p = 4$）：$6\alpha$ + 1.5 × 0.29 µs ≈ 12 + 0.44 = 12.4 µs，× 64 ≈ 0.80 ms；递归倍增：2 × (2 + 0.29) µs ≈ 4.6 µs，× 64 ≈ 0.29 ms。用 t_formula("ring", 4, 131072, 2e-6, 450e9) 验证。

练习 8（KV 搬运）。一个 MHA 模型（80 层、64 个 KV 头、$d_\text{head}$ = 128，BF16），一条 8192 token 的提示，KV 有多大？用一块 50 GB/s 的网卡要多久？换成 GQA（8 个 KV 头）和 FP8 呢？

每 token：$2 \times 80 \times 64 \times 128 \times 2 = 2.62$ MB；× 8192 = 21.5 GB，一块网卡 430 ms。GQA-8：÷8 → 2.68 GB、54 ms；再用 FP8：÷2 → 1.34 GB、27 ms。

练习 9（流水线广播）。$p = 8$、ICI（α = 1 µs、β = 45 GB/s），广播 8 MB。用公式算最优块数和对应的时间。

$k^* = \sqrt{6 \times 8 \times 10^6 / (10^{-6} \times 45 \times 10^9)} = \sqrt{1067} \approx 33$；$T^* = (\sqrt{6\ \mu s} + \sqrt{177.8\ \mu s})^2 = (2.45 + 13.33)^2 \approx 249$ µs。代码 03 演示 4 的模拟：$k = 32$ 时 249.11 µs。

练习 10（MoE 的出节点限制）。DeepSeek-V3 限制每个 token 最多发往 4 个节点。如果不限制（8 个专家可能在 8 个不同的节点上），跨节点的分发字节最多会增加多少？

不限制时，最坏每个 token 要向 8 个节点各发一份（$8d$ 字节）；限制在 4 个节点后，最多 4 份（先发到目标节点上同编号的 GPU，再在节点内用 NVLink 转发给该节点上的多个专家）。跨节点（InfiniBand）字节最多减半。代价是路由时多了一个约束，可能偏离最优的专家选择。

12. 延伸阅读 · Further reading

• J. Austin et al., How to Scale Your Model：第 2 章（TPU 与 ICI）、第 3 章（切分矩阵与集合通信，含 AllGather / ReduceScatter / AllReduce / AllToAll 的代价）、第 12 章（GPU：NVLink、NVSwitch、InfiniBand 胖树、SHARP、实测的 all-reduce 带宽）。
• R. Thakur, R. Rabenseifner, W. Gropp, Optimization of Collective Communication Operations in MPICH（IJHPCA 2005）：各种集合通信算法和它们的 α–β 代价。
• P. Patarasuk and X. Yuan, Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations（JPDC 2009）：ring all-reduce 的带宽最优性。
• M. Shoeybi et al., Megatron-LM（2019）：张量并行每层两次 all-reduce。
• DeepSeek-AI, DeepSeek-V3 Technical Report（2024）：MoE 的跨节点 all-to-all、FP8 分发、通信与计算重叠。
• NVIDIA NCCL 文档与 nccl-tests 的”Performance”说明：algbw 与 busbw 的定义。
• 本仓库 CS349D 前置讲 P5：从推理系统的角度讲分布式通信，含张量并行、序列并行、ring attention 的通信模型。

13. 和正课的联系 · Where this shows up

• 第 4 讲（分布式推理）：How to Scale Your Model 的切分记号和”四种切分矩阵乘法各需要哪种集合通信”（all-gather、reduce-scatter、all-reduce、all-to-all）；Pope et al. 的 1D / 2D 切分；Megatron 张量并行（原课作业 3）——都建立在本讲的代价模型上。
• 第 5 讲（解耦式推理）：prefill → decode 的 KV 搬运（§7.5）；异构硬件之间的网络。
• 第 6 讲（优化 decode）：decode 每一步都很短，通信的 α 直接加在 TPOT 上（§7.1）。
• 第 7 讲（KV cache 管理）：Mooncake 的分层 KV 存储与跨节点传输。
• 第 8 讲（硬件引擎）：TPU 的 ICI torus、GPU 的 NVLink / NVSwitch。
• 第 11 讲（内核优化）：megakernel 把通信也放进同一个内核，消灭每次 all-reduce 的固定开销。