Blink — 按拓扑动态拼生成树替代 NCCL ring

是什么

Blink 是一个集合通信库，给多 GPU 训练用。它要解决的问题一句话：

当你的 GPU 机器里 NVLink 和 PCIe 混着用（云上几乎都是这样），NCCL 那套「所有 GPU 串成一个环」的方法会被最慢的一段链路拖死。

Blink 的做法：根据真实拓扑，在 GPU 互联图里同时打包多棵生成树，让数据沿不同的树并行流动，把所有链路同时吃满。

日常类比：送快递。

NCCL ring：把全市快递员排成一个圈，每个人只把包裹递给下一个人。只要有一段路堵车，整圈都得等。
Blink：同时开 3 条独立线路（高架 / 地铁 / 普通路），把包裹拆 3 份分头送，到目的地再拼。所有路的容量都用上。

为什么重要

不理解 Blink 解决的问题，就解释不了下面这些事：

为什么云上租 8 卡机训练，通信占整轮训练时间的 30–50%，比单卡还慢
为什么同样是 V100 8 卡，本地服务器和 AWS p3.16xlarge 跑出来速度差很多——拓扑不一样
为什么 PyTorch / Horovod / NCCL 后来都吸收了 Blink 的思想（多树 / 拓扑感知）
为什么”加机器训练就更快”在异构集群里不成立

核心要点

Blink 干的事可以拆成三步：

第一步：探测拓扑，建一张图

跑一遍 nvidia-smi topo -m 拿到 GPU 间的连接（NVLink 几条、PCIe 怎么挂、跨不跨 NUMA），再实测每条链路带宽，建一张有向加权图。每个 GPU 是一个点，每条互联是一条边。

第二步：在图里打包尽量多的生成树

生成树：一棵覆盖所有 GPU 的树（无环）。一棵生成树就能完成一次 broadcast / all-reduce——根节点把数据发下去，叶子节点收到。

关键洞见（Edmonds 1973 已证）：有向图里边不交的生成树最多有 min(入度) 棵。也就是说，每条边只能被一棵树用一次，但你可以同时拼出好几棵互不冲突的树。

如果拓扑是规则的（如 DGX-1 V100 立方体），可以解析地算出最优树数
如果是不规则的（云上常见），用线性规划（LP）启发式搜出近似最优解

第三步：多棵树并行跑

每棵树负责数据的一片（chunk）。N 棵树 = N 倍带宽，因为它们用的是不同的边。

加上 chunking + pipelining（把数据切片流水送），全链路同时被打满。

实践案例

案例 1：DGX-1 V100 8 卡的拓扑陷阱

DGX-1 把 8 张 V100 接成一个立方体：每张卡有 4–6 条 NVLink，但对角线两点（如 GPU 0 和 GPU 6）之间没直连——必须中转。

NCCL ring 在这种拓扑里：

选一个环（必然是 8 个点首尾相连）
这个环里至少有一段不是 NVLink（某些版本会经过 QPI / PCIe）
整环带宽 = 那一段的带宽

Blink 在同一个立方体上：

算出能打 3 棵边不交的生成树（每棵都全是 NVLink）
三棵并行 → 3x 带宽
all-reduce 实测比 NCCL 快约 2x

案例 2：异构云机器的”环路塌方”

AWS p3.16xlarge：8 张 V100，但 NVLink 只在某些卡之间有，跨 socket 要走 PCIe。

NCCL ring 把所有 8 张串起来 → 环带宽被 PCIe（约 8 GB/s）锁死，远低于 NVLink（25 GB/s 单向）。

Blink 探测后把 NVLink 子图和 PCIe 边分别用，VGG16 端到端训练最高 8x 加速（VGG16 通信量大，受益最多；ResNet50 通信量小，加速 1.4–2x）。

案例 3：消息大小决定算法

small messages (< 256 KB)  →  Blink 反而比 NCCL 慢（多 stream 启动开销）
medium messages            →  Blink 持平或略胜
large messages (> 4 MB)    →  Blink 大幅领先

实际系统会按 message size 动态切换算法。这是 Blink 留给后续工作的一个口子——后来 NCCL 自己也加了「多通道」（multiple channels）借鉴这个思路。

案例 4：单机 vs 跨机的不同收益

论文实测里，单机内（机内 NVLink + PCIe）all-reduce 的加速来自”把 PCIe 边也利用起来”，倍数稳定 2x 左右。

跨机（多台 p3.16xlarge 经 25 Gbps 网卡）的加速更夸张：VGG16 端到端 8x。原因是跨机网络带宽就是瓶颈，Blink 对每台机器内部先打包出一棵树压缩出口数据，再走网络——相当于减少了跨机要传的量。

这告诉我们：通信优化的收益看你瓶颈在哪。机内瓶颈是异构链路；跨机瓶颈是网络出口。Blink 同时压两端。

踩过的坑

拓扑必须可探测且稳定。多租户共享 GPU 时，“邻居” 的流量会污染带宽测量；Blink 的 LP 解就可能选错树。
多 stream 吃 SM 资源。N 棵树并行 = N 个 CUDA stream，每个 stream 都要 launch kernel；树太多时调度开销吃掉收益。论文里 N 一般 ≤ 6。
不是所有集合操作都能套。Blink 重点优化 broadcast / reduce / all-reduce；像 all-to-all（MoE 训练用得多）这类全互联通信，生成树打包不对症。
生成树打包是 NP-hard（一般有向图）。论文用 LP 松弛 + 取整，得到近似解；最坏情况可能与最优差 2x。

适用 vs 不适用场景

适用：

异构 GPU 拓扑（混合 NVLink + PCIe；多 socket；跨 NUMA）
大消息集合通信（梯度同步、参数广播，几 MB 起）
训练框架已经按 collective 抽象（PyTorch DDP、Horovod、TensorFlow MirroredStrategy）

不适用：

同构高带宽拓扑（如 NVSwitch 全连接的 DGX A100）→ ring 已经够好，多树没空间
小消息 / 高频通信（如参数服务器风格的稀疏更新）→ stream 启动开销吃掉收益
多租户云 → 拓扑/带宽不稳定，LP 解失准
all-to-all 主导的工作负载（MoE、GNN）→ 生成树不是合适抽象

历史小故事（可跳过）

1973：Edmonds 证明有向图边不交生成树最多 min(入度) 棵——纯图论结果，跟 GPU 没关系。
2017：NCCL 1.x 用 ring；DGX-1 上手写规则环；性能不错但只对自家拓扑调过。
2018：作者 Guanhua Wang（Berkeley RISELab）在云上跑 ResNet 时发现 p3.16xlarge 比本地慢一半，溯源到 ring 选了 PCIe 链路。
2020 MLSys：Blink 论文发表，把 Edmonds 的 50 年前定理搬到 GPU 训练上。
2020+：NCCL 2.7 引入「tree all-reduce」、PyTorch torch.distributed 加入 process group 后端选择——都吸收了 Blink 的「按拓扑选算法」思想。

学到什么

环算法的瓶颈是最慢边——这件事在网络里早就是常识（min-cut），但 GPU 训练界长期被 NCCL 的”够用”覆盖。
图论 → 系统：把”集合通信”翻译成”打包生成树”，问题就有了 50 年前的现成定理可用。第一性原理推导比拍脑袋设计强得多。
拓扑感知比加带宽便宜：与其升级硬件，不如先把已有链路用满。Blink 的所有收益不需要换任何硬件。
同构假设是性能杀手：NCCL 设计时假设拓扑同构（DGX 内部规则），云时代这个假设就崩了。Blink 是面向”碎片化拓扑现实”的第一个系统化回应。

关联

nvlink-nvswitch-2018 —— Blink 的优化对象就是 NVLink + PCIe 混合拓扑
gpipe-2019 —— 流水并行；与 Blink 的数据并行通信优化是正交问题
alpa-2022 —— Alpa 的并行策略搜索把 Blink 这类通信方案当一个候选项
ring-allreduce —— Blink 替代的旧算法
horovod —— Uber 早期跨框架 all-reduce 库；Blink 思想可作为它的后端
byteps-2020 —— 同时期参数服务器风格的另一条路；与 Blink 形成对照