开这系列的文章不是哗众取宠，而是想跟大家分享下现实业务中的一些真正的算法落地。也是受了叶丁丁的teahour-94 - 与 Hawstein 和左程云聊算法和数据结构和刘未鹏-知其所以然（三）：为什么算法这么难的启发。
大家应该有一个普遍的认知-无论ACM还是leecode那些算法问题和正常业务中需要实现的算法都有很大的差异性。具体来讲有几点：

  1. 刷题或者打比赛甚至kaggle上的算法都是low-bound和up-bound有非常明确的边界（俗称干净）而业务中的算法需要更多的泛化性和冗余度（可扩展性比较好）
  2. 一般的算法都是单一求解，但是业务中真正落地的算法解决方案都是组合求解
  3. 一般算法都是面向证明，但业务算法是面向解决实际问题-这也带来一定的差异性，特别是POC阶段，你预先设计的方案中的算法没有办法同刷题中的算法严格匹配，顶多算相似性匹配。

所以我有一个想法就是把我看到的一些好的应用中的算法做一个系列。我在现实工作中的秉承原则也是”mind and hand”既动脑也动手。无论做管理岗位还是架构师都没有脱离这个原则。

翻译来源：gloo 用于多机训练的各种原语的集合通信库的核心算法

Gloo是一个统一的通讯类库。它附带了许多对机器学习应用有用的集成算法。其中包括屏障、广播和allreduce。
其实现了参与机器之间的数据传输被抽象，以便IP可以随时使用，或者在Finiband（或RoCE）可用时使用。在后一种情况下，如果使用InfiniBand传输，则可以使用GPUDirect加速跨机器GPU到GPU的内存传输。

具体算法实现：

Gloo提供的算法索引及其语义。
使用的变量：**
P： 进程/机器数
N： 每个进程的缓冲区数
S： 缓冲区大小

使用的术语：

  • 沟通步骤：沟通步骤的数量。根据传输的不同，每个通信步骤都有一定的延迟。因此，算法使用的步骤越少，就越适合于更高延迟的传输。低延迟传输可以更好地容忍更多的通信步骤。
  • 连线上的字节数：每个参与进程传输的字节总数。这个数字越高，算法就越快受到网络带宽的限制。
  • 在适用的情况下，算法有一个与系统内存缓冲区一起工作的实现，以及一个与NVIDIA GPU内存缓冲区一起工作的实现。在后一种情况下，不需要在主机和设备之间复制内存；这由算法实现负责。

All-reduce
跨P进程计算每个进程N个数组的用户指定缩减操作（例如总和）。这种计算是就地进行的；算法完成后，所有输入数组都包含结果缩减。

此算法的每个实现分为三个阶段：

  • N个缓冲区的局部约化
  • 进程之间的Allreduce
  • 将结果广播回N个缓冲区

Allreduce_ring

  • 沟通步骤：P-1
  • 传输线路上的字节数：P*S

第2阶段实施如下：

  1. 将本地结果传输到右侧邻居
  2. 从左侧邻居接收缓冲区并还原为本地结果
  3. 将传入缓冲区发送到右侧邻居
  4. 重复2-3，直到进程看到所有数据

allreduce_ring_chunked

  • 通讯步骤：4*P
  • 传输线路上的字节数：2*S

第2阶段分为2个子阶段：
首先，

  • 算法在局部约简上迭代，传输缓冲区的块并在每一步进行约简。
  • 块的数量等于2*P，允许使用双缓冲。这意味着总是有一个块在运行，同时对另一个块进行缩减。
  • 在这一阶段的末尾，每个进程P都持有缩减结果的1/P。

其次，
该算法再次迭代局部约简，现在广播局部结果。

通过2P块和两个子阶段，我们得到了4P通信步骤。
这些子阶段的实施如下（大致）：
第一：

  • 基于进程秩的局部缩减缓冲区偏移量计算
  • 将偏移量处的块传输到右侧邻居
  • 从左侧邻居在偏移量-1处接收数据块并将其还原为本地结果
  • 从偏移量中减去1，需要时进行数据封装
  • 重复2-4次，直到整个缓冲区的进程完成

第二：

  • 将偏移量+1处的块（包含全局缩减）传输到右侧邻居
  • 从左侧邻居处偏移接收块并复制到本地结果
  • 从偏移量中减去1，需要时进行数据封装
  • 重复1-3次，直到整个缓冲区的进程完成

allreduce_halving_doubling

  • 通讯步骤：2*lg（P）
  • 传输线路上的字节数：2*S

第2阶段分为两个子阶段：
首先，使用递归向量减半、距离加倍方法以lg（P）步执行减少散射。在该算法的第一步中，处理成对通信（秩0与1，秩2与3等），发送和接收其输入缓冲区的不同部分。例如，进程0将其缓冲区的后半部分发送到进程1，并从进程1接收和减少缓冲区的前半部分的数据。在进行下一通信步骤之前，对接收到的数据进行缩减，在下一通信步骤中，到目的地秩的距离加倍，而发送和接收的数据减半。在缩小散射相位完成后，每个处理都有最终缩小阵列的一部分。
阶段2的第二个子阶段执行全聚集。这再次使用递归算法来完成，从reduce scatter开始反向回溯通信步骤，但这次只是在每个步骤连接接收到的数据。在每个进程和步骤中，在allgather中接收在reduce散点中发送的缓冲区部分，现在发送在reduce散点中接收的部分。
在reduce散点的各个步骤中，数据被接收到不同的缓冲区中，不存在竞争条件。然而，reduce scatter和allgather的镜像步骤（例如reduce scatter的最后一步和allgather的第一步）写入相同的缓冲区。为了防止竞争条件，在reduce scatter子阶段处理数据后发送通知。在执行发送之前，在allgather子阶段处理此通知。在大多数情况下，这些通知消息将在处理它们的allgather步骤之前很久到达，因此它们对性能的影响应该是最小的。
当在两个进程的非幂次运行时，该算法将执行分为两个幂次的块，并在块内减少分散后进行块间通信。两种情况下的非功率与两种情况下的功率相比会有一定程度的负载不平衡，但大块数较少的情况（如8+4或16+8）仍应表现较好。
在（Thakur等人，MPICH中的集体通信操作优化，IJHPCA，2005）中描述和分析了减半加倍/二进制块算法。

allreducube_bcube
使用的其他变量：

  • B： 基本（每个步骤的最大对等点数）
  • 通讯步骤：2*log B（P）
  • 传输连线上的字节数：2*和（S/B^S）{S:0到日志B（P）-1}

这是另一个allreduce实现。Bcube是一种将节点分组的方案。在reduce-scatter阶段，在每个组中，一个节点与base-1其他节点对等。在第一步中，在组内的节点之间减少数据。在下一步中，组中的每个节点与来自其他完全不同组的base-1节点对等。因为每个节点都会从减少的与之通信的数据开始，所以它就像与上一步中的基本节点/组数通信一样。这个过程一直持续到所有组都被覆盖，并且能够做到算法将有对数（n）步数。每个步骤节点都会减少元素的总数（基本步骤）。在reduce scatter阶段的末尾，每个节点都会减少一块元素。现在，在所有的聚集中，我们遵循一个反向的减少散布过程，将减少的数据与其他节点进行通信。

cuda_allreduce_ring
基于CUDA的allreduce_-ring实现。在CPU上运行本地缩减之前，GPU端缓冲区并行复制到系统内存。阶段2完成后，CPU端的结果被并行复制回GPU端的缓冲区。

cuda_allreduce_ring_chunked
基于CUDA的allreduce-ring-chunked的实现。GPU侧缓冲区被缩减为GPU缓冲区0（使用NCCL）。结果被异步复制到系统内存中。阶段2完成后，CPU端的结果被复制回GPU缓冲区0，然后并行地广播到其他GPU缓冲区（使用NCCL）。
阶段1中的本地减少和阶段3中的广播都与需要或变得可用该数据的通信步骤流水线连接。

Cuda_allreduce_halving_doubling
基于CUDA的allreduce_halving_double的实现，在reduce/broadcast步骤和通信之间没有流水线。

cuda_allreduce_halving_double_pipelined
基于CUDA的allreduce_halving_double的实现，在本地缩减/广播步骤和通信之间使用流水线。本地缩减步骤分为两个步骤（因为第一个通信步骤发送一半的缓冲区大小）。最终广播通过lgP步骤进行流水线传输，每个步骤对应于allgather阶段的接收。

Reduce-Scatter
跨P进程计算每个进程N个数组的用户指定缩减操作（例如总和）。这种计算是适当的。结果被分散到用户指定的所有进程；算法完成后，所有输入数组都包含分散的结果。

此算法的每个实现分为三个阶段：

  • N个缓冲区的局部约化
  • 减少进程之间的Reduce-Scatter
  • 将结果广播回N个缓冲区

reduce-scatter_having_doubling

  • 沟通步骤：lg（P）
  • 数据传输连线上的字节数：S（用于在P进程之间均匀地分散结果）

第2阶段分为两个子阶段：

  • 首先，使用递归向量减半、距离加倍方法以lg（P）步执行减少散射。在该算法的第一步中，处理成对通信（秩0与1，秩2与3等），发送和接收其输入缓冲区的不同部分。例如，进程0将其缓冲区的后半部分发送到进程1，并从进程1接收和减少缓冲区的前半部分的数据。在进行下一通信步骤之前，对接收到的数据进行缩减，在下一通信步骤中，到目的地秩的距离加倍，而发送和接收的数据减半。

  • 在减少散射阶段结束后，最大二进制块中的每个进程都具有最终减少阵列的一部分。下一步是根据用户指定的分布进行分散/分布。注意，由于最大二进制块中递归减半算法的性质，块的顺序不正确。通过在进程p和p之间交换数据强制正确的重新排序，其中p’是p的位反转。

当在两个进程的非幂次运行时，该算法将执行分为两个幂次的块，并在块内减少分散后进行块间通信。两种情况下的非功率与两种情况下的功率相比会有一定程度的负载不平衡，但功率接近两种情况下（如16+2）仍应表现得相对较好。
在（Thakur等人，MPICH中的集体通信操作优化，IJHPCA，2005）中描述和分析了减半加倍/二进制块算法。
数据重新排序在（Sack等人，《通过非最小通信实现更快的拓扑感知集体算法》，PPoPP，2012）中描述。

Barrier
进程之间的同步点。

barrier_all_to_all

  • 沟通步骤：1
  • 传输线路上的字节数：P

每个进程都向其他每个进程发送通知。然后，它等待来自其他每个进程的通知。

barrier_all_to_one

  • 沟通步骤：2
  • 传输线路上的字节：1表示非根，P表示根

非根进程：向根发送通知，等待根通知。
根进程：等待P-1进程的通知，向P-1进程发送通知。

广播
将一个进程上的缓冲区内容广播到其他P-1进程。

broadcast_one_to_all

  • 沟通步骤：1
  • 传输线路上的字节数：P*S

非根进程：从根接收缓冲区。
根进程：向P-1进程发送缓冲区。

pairwise_exchange

  • 通信步骤：变量
  • 数据传输连线上的字节数：S

一种类似于减半加倍减少分散的通信模式，简化为基准测试目的。通信步骤的数目C（必须介于1和lg（P）之间）被指定为算法的输入。在每个步骤中，节点集被分成对，就像在相应的将加倍减少散射减半的步骤中一样。但是，与reduce散点不同，在每个步骤中发送的缓冲区大小是相同的（等于S/C）。