原文地址： https://andrew.gibiansky.com/blog/machine-learning/baidu-allreduce/
Allreduce 其实一直是HPC领域很常见的一个技术，所以百度这篇论文其实讲的也是如何将Allreduce从HPC引入到深度学习领域，通过Allreduce算法，大大的提高了深度学习的模型训练速度
简介
过去几年中，神经网络规模不断扩大，而训练可能需要大量的数据和计算资源。 为了提供所需的计算能力，我们使用高性能计算（HPC）常用的技术将模型缩放到数十个GPU，但在深度学习中却没有充分使用。 这种ring allreduce技术减少了在不同GPU之间进行通信所花费的时间，从而使他们可以将更多的时间花费在进行有用的计算上。 在百度的硅谷AI实验室（SVAIL）中，我们成功地使用了这些技术来训练最先进的语音识别模型。 我们很高兴将Ring Allreduce的实现发布为TensorFlow的库和补丁程序，并希望通过发布这些库，我们可以使深度学习社区更有效地扩展其模型。
Introduction
在过去的几年中，神经网络已被证明是解决各种问题的非常有效的工具，并且在规模和计算需求方面迅速增长。 2012年，用于图像识别的SuperVision卷积网络通过两个星期的GPU和6000万个参数在对象识别方面取得了长足的进步。 2016年，研究人员在网络上进行语言建模方面取得了突破，该网络具有在32个GPU上进行了为期三周的训练的十亿多个参数。 在百度研究院的硅谷AI实验室中，2014年，我们的Deep Speech语音识别系统的第一次迭代大约有1100万个参数，而一年后的下一次迭代已增长到1亿个参数。
随着神经网络的参数数量和计算需求的增长，在许多节点和许多GPU上有效并行化神经网络训练变得越来越重要，因为等待大型网络训练数月会减慢实验速度并限制进一步的发展。 在此博客文章中，我们介绍了一种来自高性能计算（HPC）领域的技术，并演示了如何将其应用于深度学习以在神经网络训练中获得显着的性能提升。
通信问题
在将神经网络的训练并行化到许多GPU上时，必须选择如何将不同的操作分配到可用的不同GPU上。 在这里，我们重点介绍一种称为数据并行随机梯度下降（SGD）的技术。 与标准SGD中一样，梯度下降是对数据子集（mini-batch）进行的，需要进行多次迭代才能遍历整个数据集。 但是，在数据并行训练中，每个GPU都具有整个神经网络模型的完整副本，并且对于每次迭代，mini-batch中仅分配了样本的子集。 对于每次迭代，每个GPU都会在其数据上进行网络的正向传播，然后进行错误反向传播，以计算相对于网络参数的损耗梯度。 最后，GPU彼此通信以平均不同GPU计算的梯度，将平均梯度应用于权重以获得新的权重。 所有GPU都以锁定步长(lock-step)进行迭代，一旦GPU完成迭代，它就必须等待所有其他GPU完成迭代，才能正确地更新权重。 这等效于在单个GPU上执行SGD，但是我们通过在多个GPU之间分配数据并并行进行计算来获得加速。
当您只有两个GPU且参数以兆字节数据度量时，这些GPU的通信方式可能并不十分重要。 但是，当您的模型具有数十亿个参数时，梯度可能会占用数GB的空间（因为每个参数都有一个梯度值），并且您要协调数十个GPU，因此通信机制至关重要。例如，考虑可能的最直接的通信机制。 每个GPU都会在其mini-batch的子集上计算梯度。 然后，每个GPU都将其梯度发送到单个GPU，后者获取所有梯度的平均值，然后将平均值发送回所有其他GPU。
与单个Reducer GPU之间的数据传输
需要发送的数据越多，发送数据所需的时间就越长。 每个通信通道都具有最大吞吐量（带宽）。 例如，良好的Internet连接可以提供每秒15兆字节的带宽，而千兆以太网连接可以提供每秒125兆字节的带宽。HPC群集上的专用网络硬件（例如Infiniband）可以在节点之间提供每秒几GB的带宽。在直接从单个GPU发送和接收数据的直接机制中，单个GPU必须从所有GPU接收所有参数，并将所有参数发送到所有GPU。 系统中的GPU越多，通信成本就越高。
让我们评估一下这种交流策略如何在真实模型上发挥作用，例如以百度的Deep Speech 2（具有3亿个可训练参数）为模型的语音识别网络。 3亿个参数（每个参数四个字节）大约为1.2 GB的数据。 假设您系统上的网络硬件可以支持每秒1 GB的带宽； 在这种情况下，如上所述将系统并行化为两个GPU将使每次迭代速度降低1.2秒。 在十个GPU上并行进行训练将使每次迭代速度降低10.8秒； 随着GPU数量的增长，每次迭代所需的时间呈线性增长。 即使每次迭代花费几秒钟，通信成本的这种线性增长也很快使进一步的并行化变得不切实际，并降低了训练效率。
一种替代方案是放弃训练算法的同步特性，并消除所有GPU在梯度下降迭代中以锁定步长前进（lock-step)的约束。 但是，尽管这样做可以更轻松地并行化模型，但消除此约束的算法（异步SGD的变体）可能难以调试，并且对于某些模型可以收敛到低于标准的结果，因此，出于此目的，我们不考虑它们。相反，我们可以通过使用高性能计算领域中的分布式归约算法并利用带宽最优ring allreduce来解决通信问题。
The Ring Allreduce
上述简化通信策略的主要问题是通信成本随系统中GPU的数量线性增加。 相反，ring allreduce是一种算法，其通信成本是恒定的，并且与系统中GPU的数量无关，并且仅由系统中GPU之间最慢的连接确定； 实际上，如果仅将带宽作为通信成本的一个因素（并忽略延迟），则ring allreduce是一种最佳的通信算法。（当您的模型很大，并且需要少量发送大量数据时，这是对通信成本的一个很好的估计。）ring allreduce的GPU排列成一个逻辑环。 每个GPU应该有一个左邻居和一个右邻居； 它只会向右邻居发送数据，而从左邻居接收数据。
GPUs arranged in a logical ring
该算法分两个步骤进行：首先是scatter reduce，然后是all gather。 在scatter reduce步骤中，GPU将交换数据，以使每个GPU最终获得最终结果的一部分。 在all gather步骤中，GPU将交换这些块，以使所有GPU最终获得完整的最终结果。
The Scatter-Reduce
为了简单起见，我们假设目标是按元素逐个汇总一个大型浮点数数组中的所有元素； 系统中有N个GPU，每个GPU都有一个相同大小的数组，并且在all reduce结束，每个GPU都应具有相同大小的数组，其中包含原始数组中数字的总和。
首先，GPU将阵列划分为N个较小的块（其中N是环中GPU的数量）。
Partitioning of an array into N chunks
接下来，GPU将执行scatter reduce的N-1次迭代； 在每次迭代中，GPU都会将其块之一发送到其右邻居，并从其左邻居接收一个块，并累积到该块中。 每个GPU发送和接收的块在每次迭代中都不同。 第n个GPU从发送块n和接收块n – 1开始，然后从那里向后进行，每次迭代都发送在上一次迭代中接收到的块。
例如，在第一次迭代中，上图中的五个GPU将发送和接收以下块：
Data transfers in the first iteration of scatter-reduce
在第一个发送和接收完成之后，每个GPU将具有一个块，该块由两个不同GPU上相同块的总和组成。 例如，第二个GPU上的第一个块将是来自第二个GPU和第一个GPU的那个块中的值之和。
Itermediate sums after the first iteration of scatter-reduce is complete
在接下来的迭代中，该过程继续进行，到最后，每个GPU将具有一个块，其中包含所有GPU中该块中所有值的总和。 下图显示了所有数据传输和中间结果，从第一次迭代开始一直持续到scatter reduce完成为止。
Final state after all scatter-reduce transfers
The Allgather
scatter reduce步骤完成后，每个GPU都有一个值数组，其中某些值（每个GPU一个块）是最终值，其中包括来自所有GPU的贡献。 为了完成减少，GPU必须交换这些块，以便所有GPU都具有所有必需的值。
ring allgather与scatter reduce相同（发送和接收进行N-1次迭代）相同，除了它们不累积GPU接收的值，而是简单地覆盖块。 第n个GPU首先发送第n + 1个块并接收第n个块，然后在以后的迭代中始终发送它刚接收的块。
例如，在我们的五个GPU设置的第一个迭代中，GPU将发送和接收以下块：
Data transfers in the first iteration of the allgather
第一次迭代完成后，每个GPU将具有最终阵列的两个块。
在接下来的迭代中，该过程继续进行，最后，每个GPU将具有整个阵列的完全累加值。 下图显示了所有数据传输和中间结果，从第一次迭代开始一直持续到allgather完成为止。
Final state after all allgather transfers
Allreduce Communication Cost
回想一下，对于介绍中描述的简单通信算法，通信成本随GPU数量线性增长。
在我们描述的系统中，N个GPU中的每一个将分别发送和接收N-1次scatter reduce值和N-1次all gather的值。 每次，GPU将发送K / N个值，其中K是在不同GPU之间求和的数组中值的总数。 因此，往返每个GPU的数据传输总量为
上述公式与GPU的数量无关。
由于所有传输都是同步发生的，因此减少的速度受到环中相邻GPU之间最慢（最低带宽）连接的限制。 如果为每个GPU选择了正确的邻居，则该算法是带宽最佳的，并且是减少带宽的最快算法（假设与带宽相比，延迟成本可以忽略不计）4。 通常，如果节点上的所有GPU在环中彼此相邻，则该算法的效果最佳。 这样可以最大程度地减少网络争用的数量，否则可能会大大降低GPU-GPU连接的有效带宽。
Applying the Allreduce to Deep Learning
ring allreduce是高性能计算领域中的一种众所周知的算法，但是在深度学习中却很少得到使用。 在我们的实验室中，我们设法使用此工具作为所有数据并行培训的基础，从而使我们可以有效地将培训扩展到数十个GPU。
为了最小化通信开销，我们可以利用神经网络的结构。 在每次迭代中，每个GPU都运行正向传播以计算误差，然后运行反向传播以计算神经网络的每个参数的梯度。 反向传播计算从输出层开始并向输入层移动，这意味着输出层参数的梯度在较早层的梯度之前明显可用。 由于Allreduce一次可以对网络参数的一个子集进行操作，因此我们可以在输出层参数上开始Allreduce，而其他梯度仍在计算中。 这样做会使通信与反向传播步骤中的其余计算重叠，从而减少了每个GPU最终等待通信完成的总时间。
例如，考虑一种类似于deep speech的语言模型，但是具有大约3亿可学习的参数（因此总梯度大小为1.2 GB）。 使用allreduce，每个GPU必须发送和接收大约2.4 GB的数据。 使用支持CUDA的MPI实现（例如OpenMPI），我们可以使用GPUDirect RDMA在GPU之间传输数据，带宽大约为每秒10 GB。 但是，集群中节点之间的连接速度较慢，Infiniband提供的带宽约为每秒6 GB。 由于限制因素是Infiniband连接，因此单次迭代大约需要
由于deep network中层数较深的层首先具有可用的梯度，因此我们可以在完成整个反向传播过程之前就开始进行数据传输，因此实际开销可能少于400毫秒； 通信和计算之间的重叠可能会根据要优化的神经网络的性质而有所不同。
我们实现了上述语言模型，并测试了从单个GPU（无通信开销）扩展到40个GPU时每次迭代所花费的时间。 这40个GPU分为5个节点，每个节点有8个GPU，并通过Infiniband连接。 我们将语言模型运行了300次迭代，批处理大小为32，并计算了每秒处理的样本数。
可以看到，整个系统的吞吐量与GPU的数量呈线性比例关系，添加更多的GPU不会导致每次迭代的速度显着降低。 在40个GPU上运行模型每次迭代大约需要650 – 700毫秒，而在单个GPU上运行大约需要370毫秒。 由于根据我们的估计，通信将花费400毫秒，因此通过将反向传播与数据传输重叠，可以使每次迭代节省70至120毫秒。
Conclusion
ring allreduce是一种高性能计算领域的技术，它使我们能够有效地平均许多设备和许多节点上的神经网络中的梯度。 通过在训练期间使用此带宽最佳算法，您可以大大减少通信开销并扩展到更多设备，同时仍保留同步随机梯度下降的确定性和可预测的收敛特性。 该算法与网络体系结构和深度学习框架无关，可为数据并行训练的效率提供切实而直接的好处，同时也相当简单明了且易于实现。
为了让您更轻松地利用这些技术，今天我们发布了baidu-allreduce，这是一个C库，演示了allreduce算法，您可以将其嵌入到任何启用了MPI的应用程序中。 此外，优步（Uber）出色的Horovod库采用了我们在这里开创的技术。
我们希望其他深度学习框架将在适当的情况下利用类似的技术，并且借助这些工具，您将能够轻松，高效地将神经网络模型扩展到许多机器，而与您选择的框架无关。