关于深度学习:手把手推导-Ring-Allreduce-的数学性质

撰文|袁进辉

分布式深度学习里的通信重大依赖于规定的集群通信（见《反抗软件系统复杂性③：失当分层，不多不少》对通信的探讨），诸如 all-reduce, reduce-scatter, all-gather 等，因而，实现高度优化的集群通信，以及依据工作特点和通信拓扑抉择适合的集群通信算法至关重要。

本文以数据并行常常应用的 all-reduce 为例来展现集群通信操作的数学性质。

1

all-reduce 在干什么？

图 1：all-reduce

如图 1 所示，一共 4 个设施，每个设施上有一个矩阵（为简略起见，咱们特意让每一行就一个元素），all-reduce 操作的目标是，让每个设施上的矩阵里的每一个地位的数值都是所有设施上对应地位的数值之和。

图 2：应用 reduce-scatter 和 all-gather 实现 all-reduce

如图 2 所示，all-reduce 能够通过 reduce-scatter 和 all-gather 这两个更根本的集群通信操作来实现。基于 ring 状通信能够高效的实现 reduce-scatter 和 all-gather，上面咱们别离用示意图展现其过程。

2

reduce-scatter 的实现和性质

图 3：通过环状通信实现 reduce-scatter

从图 2 能够看出，reduce-scatter 的后果是每个设施保留一部分 reduce 之后的后果。为了不便探讨，咱们先定义一些符号。

假如有 p 个设施（下面的例子中 p=4）；假如整个矩阵大小是 V, 那么 reduce-scatter 后，每个设施上有 V / p 大小的数据块；假如卡和卡之间通信带宽是 β, 而且是双工通信（duplex），即每个设施进口和入口带宽能够同时达到 β，所有设施的入口带宽总和是 p xβ，所有设施的进口带宽总和也是 p xβ。

高效实现一个集群通信的要害是如何充分利用设施和设施之间的带宽，基于环状（ring）通信实现的集群通信算法就是这一思维的体现。 咱们以 reduce-scatter 为例来看看环状通信算法是怎么工作的。

一共有 p 个设施，每个设施上数据都划分为 p 份，环状 reduce-scatter 一共须要 p-1 步能力实现。

在第 1 步中，每个设施都负责某一块 V/ p 的数据并向右边的设施发送这块数据，譬如在图 3 中，第 1 个设施负责第 2 片数据并向第 0 个设施发送（也就是第 4 个设施），第 2 个设施负责第 3 片数据并向第 1 个设施发送，第 3 个设施负责第 4 片数据并向第 2 个设施发送，第 4 个设施负责第 1 片数据并向第 3 个设施发送，每个设施收到左边设施的数据后，就把收到的数据累加到本地对应地位的数据下来（通过逐步变深的色彩示意数据累加的次数更多）。留神，在这样的安顿下， 每个设施的入口带宽和进口带宽都被用上了，而且不会产生争抢带宽的事件 （挑战一下本人，能不能想出比环状通信更厉害的集群通信实现？）。

在第 2 步中，第 1 个设施把累加后的第 3 片数据向第 0 个设施发送（也就是第 4 个设施），第 2 个设施把累加后的第 4 片数据向第 1 个设施发送，第 3 个设施把累加后的第 1 片数据向第 2 个设施发送，第 4 个设施把累加后的第 2 片数据向第 3 个设施发送，每个设施收到左边设施发过来的数据后，就把收到的数据累加到本地对应地位的数据下来（累加后色彩更深）。

在第 3 步中，第 1 个设施把累加后的第 4 片数据向第 0 个设施发送（也就是第 4 个设施），第 2 个设施把累加后的第 1 片数据向第 1 个设施发送，第 3 个设施把累加后的第 2 片数据向第 2 个设施发送，第 4 个设施把累加后的第 3 片数据向第 3 个设施发送，每个设施收到左边设施发送过去的数据后，就把收到的数据累加到对应地位的数据下来（累加后色彩更深）。

通过 p-1 步之后，每个设施上都有了一片所有设施上对应地位数据 reduce 之后的数据。整个过程中，每个设施向外发送了 (p−1)V/ p 大小的数据，也收到了（p−1)V/ p 大小的数据，因为每个设施的进口或入口带宽是 β，所以整个过程须要的工夫是 (p−1)V/pβ，如果 p 足够大，实现工夫近似为 V /β，神奇的是，这个工夫和设施数 p 无关。当然，在所有设施间传递的数据量是 (p-1)V，和设施数 p 成正比。

让咱们强调一下： 基于环状通信的集群通信算法执行工夫简直和设施数无关，但总通信量和设施数成正比。

3

all-gather 的实现和性质

reduce-scatter 执行完结之后，再通过 all-gather 过程就能够实现 all-reduce，其中 all-gather 也能够通过环状通信算法来实现。

图 4：通过环状通信实现 all-gather

图 4 给出了环状 all-gather 的实现过程，咱们就不详细描述了，值得注意的是，它的通信工夫和通信量的剖析与 reduce-scatter 截然不同：整个过程须要的工夫是 (p−1)V/pβ，如果 p 足够大，实现工夫近似为 V /β，这个工夫和设施数 p 无关，当然，在所有设施间传递的数据量是 (p-1)V，和设施数 p 成正比。

不过，请留神在 reduce-scatter 里，V 都是残缺矩阵的数据量，即 reduce-scatter 输出矩阵的数据量和 all-gather 输入矩阵的数据量。

4

通信量和冗余显存之间的关系

上文只剖析了通信量，而没有剖析对设施显存的占用量。以图 3 为例，每个设施上的输出矩阵大小是 V，但通过 reduce-scatter 之后每个设施上只须要 V/ p 大小的显存，也就是 (p−1)V/ p 的空间是冗余的，因为一共有 p 个设施，所以整个集群中有 (p-1)V 的显存是能够节省下来的。留神，每个设施冗余的显存恰好和每个设施的通信量统一，所有设施冗余的显存和所有设施的总通信量统一。

以图 4 为例，每个设施上的输出矩阵大小是 V /p，但通过 all-gather 之后每个设施上须要的显存是 V，而且每个设施上的矩阵的大小和数值都齐全一样，也就是通过 all-gather 之后，在设施之间产生了冗余，不同的设施存储了一些齐全一样的数据。同样， 每个设施冗余的显存恰好和每个设施的通信量统一，所有设施冗余的显存和所有设施的总通信量统一。

当然，冗余量和通信量之间的等价关系不是偶尔的，正是因为这些通信才造成了设施之间数据的冗余。

因而， 当放弃 V 不变时，增大设施数 p（咱们无妨称 p 为集群通信的并行宽度）时，所有设施之间的通信量是反比增长的，而且在所有设施上造成的冗余显存是正比例增长的。当然，实现一个特定的集群通信所须要的工夫根本和并行宽度 p 无关。

因而，减少并行宽度 p 是一个双刃剑，一方面它让每个设施解决的数据量更小，即 V /p，从而让计算的工夫更短，但另一方面，它会须要更多的通信带宽 (p-1)V，以及更多的显存空间 (p-1)V。

5

环状算法的最优性

咱们在后面提了一个问题：你能不能想出比环状算法更好的集群算法实现？答案是，实践上不可能有更好的算法了。

咱们曾经剖析过了要实现 reduce-scatter 和 all-gather 每个设施至多要向外发送（以及同时接管）的数据量是 (p−1)V/p，无论应用什么算法，这个数据量是不可能更少了。

在这个数据量下，起码须要多少工夫呢？进口带宽是 β，因而一张卡向外发送数据至多须要的工夫是 (p−1)V/pβ，这也正是环状算法须要的工夫。

当然，咱们这里的通信工夫只思考传输带宽，而没有思考每次传输都蕴含的提早（latency）。当数据量 V 比拟大时，提早项能够疏忽，上文的剖析就是成立的。

当 V 特地小，或者设施数 p 特地大时，带宽 β 就变得不重要了，反而是提早比拟要害，这时更好地实现就不是环状算法了，而应该应用树状通信。这也是为什么英伟达 NCCL 里既实现了 ring all-reduce，也实现了 double-tree all-reduce 算法（
https://developer.nvidia.com/…）。

欢送下载体验 OneFlow v0.7.0 最新版本：

https://github.com/Oneflow-In…