Collective Communication / Collective Operation / 集合通信

集合通信：Collective operation - Wikipedia

xCCL（比如 NCCL）里的 CC 指的就是这个。包含了很多元语：Reduce, Gather 等等什么的。

![[NCCL.pdf#page=4&rect=4,2,861,482&color=annotate

NCCL, p.4]]

![[NCCL.pdf#page=6&rect=4,3,862,481&color=annotate

NCCL, p.6]]

![[NCCL.pdf#page=7&rect=3,2,862,484&color=annotate

NCCL, p.7]]

Scatter 这里画的有问题，应该是 B 在 GPU 1 的第二块位置、C 在 GPU 2 的第三块位置、D 在 GPU 4 的第四块位置。

![[NCCL.pdf#page=8&rect=3,3,861,482&color=annotate

NCCL, p.8]]

Gather 这里画的有问题，初始来说应该是 B 在 GPU 1 的第二块位置、C 在 GPU 2 的第三块位置、D 在 GPU 4 的第四块位置。

![[NCCL.pdf#page=9&rect=3,2,863,482&color=annotate

NCCL, p.9]]

All-Gather 这里画的有问题，初始来说应该是 B 在 GPU 1 的第二块位置、C 在 GPU 2 的第三块位置、D 在 GPU 4 的第四块位置。

![[NCCL.pdf#page=10&rect=5,2,861,483&color=annotate

NCCL, p.10]]

![[NCCL.pdf#page=11&rect=5,1,863,482&color=annotate

NCCL, p.11]]

![[NCCL.pdf#page=12&rect=5,1,863,483&color=annotate

NCCL, p.12]]

Reduce Scatter 这里画的有问题，最后结果应该是 $A1 + B1 + C1 + D1$ 在 GPU 1 的第二块位置、$A2 + B2 + C2 + D2$ 在 GPU 2 的第三块位置、以此类推。

![[NCCL.pdf#page=13&rect=2,2,861,482&color=annotate

NCCL, p.13]]

![[NCCL.pdf#page=14&rect=3,2,862,482&color=annotate

NCCL, p.14]]

![[NCCL.pdf#page=16&rect=5,3,861,484&color=annotate

NCCL, p.16]]

AllReduce

不同机器中的数据整合（reduce）之后再把结果分发给各个机器。

all-reduce 可以通过 reduce-scatter 和 all-gather 这两个更基本的集群通信操作来实现。

Ring AllReduce

说白了，就是每一个 GPU，把上一步中接收到的对应区间的数据，在本地做了运算之后，再发送到下一个 GPU 中。因为每一步接收到的区间是不一样的，所以每一步发出去的也不一样。一共需要 $2(n-1)$ 步就能实现，而且 reduce-scatter 和 all-gather 阶段的行为包括数据量什么的都是完全对称的。

有几个 GPU 就把数据切成几份是最优的吗？

• 如果切少了，那么 scatter 完的步骤还是 $n-1$ 步，但是每一步传输的数据量变大了，也就是更久了，不合适。
• 如果切多了，$n - 1$ 步其实是传不完的，还需要多传几步，而且这几步每一步都有可能并不是所有 GPU 都在传输，比如 3 个 GPU 切 4 份这种模式，所以很有可能带宽利用率变低，从而导致整体时间变长。

综合来看，正好是 $n$ 份是最优的。Ring Allreduce 算法的标准实现中，会将每个进程上的数据切分成与 Rank 总数相等的块。

先 reduce-scatter：

再 all-gather：

AllReduce 的实际物理数据通路

我们以双机共 32 卡为例，每一台机器 16 张 GPU 以及 8 张网卡，那么整体的链路应该是 0-15 走机内的 PCIe 或者 Fabric Link，15-16 走网卡，16-31 继续走机内的 PCIe 或者 Fabric Link，31-0 走网卡。

但是实际上我们可以指定多个环（或者叫作多个 NCCL Channel），每一个环在出到另一台机器的断点位置（也就是网卡）不一样，这样就能充分利用所有的网卡进行传输，如下图：

https://my.feishu.cn/wiki/XqESwN2zJijGDhkIewrc7JD6nrM#share-URfJdL25iobN5yxCj3TcBrJGnMh

因为 AllReduce 可以拆成两个原子的集合通信，一个是 ReduceScatter，另外一个是 All Gather。Reduce Scatter 要保证最后所有的 reduce 之后的 chunk 都分散在不同的 rank 上。因为上面不同的 channel 中有的 rank 的上一个 rank 和其他 channel 有区别，所以 NCCL 为了保证 reduce scatter 最后 chunk 结果分散位置的正确性，需要提前去计算，算出来这个 chunk 在这个 channel 应该从哪一个 rank 开始进行 reduce 计算。

但是这种设计存在下面缺陷（比如我们让 Channel 1 来传 Chunk 31，让 Channel 3 来传 Chunk 15，可以看到在 Step 1，C31 和 C35 都同时占用了 GPU0 -> GPU1 中间的这块通路，这就造成了阻塞。所以整体来看，NVLink/PCIe 和网卡，小的那个是瓶颈，怎么处理 channel 感觉是一个学问）：