网上都没有人仔细讲一讲 Double Binary Tree 具体怎么操作的我来简单讲解一下。具体的细节大家还是需要去看代码。本文还汇总了各种Reduce方法只想看 Double Binary Tree 可以直接跳转目录前置知识Reduce BroadcastRecursive Halving and DoublingButterflyRing Reduce分层Ring AllReduce2D-TorusDouble Binary TreeReduceBroadcastAll其它一些参考连接NVIDIA NCCL 源码学习十二- double binary tree-CSDN博客AllReduce 算法的前世今生 – remaperhttps://zhuanlan.zhihu.com/p/79030485Massively Scale Your Deep Learning Training with NCCL 2.4 | NVIDIA Technical Blog前置知识Allreduce 操作现在是分布式训练中不可或缺的一步操作。Allreduce 操作可以分解为 Reduce 和 Broadcast 两个操作所以绝大部分算法中只需要分别考虑这两个操作怎么进行的即可。Reduce 和 Broadcast 的传输时间都是几乎一样的所以在计算时间时能看到很多系数2只是Reduce 在不考虑别的优化情况如pingpong下会多出一个计算的时间以深度学习模型训练中的数据并行为例需要对梯度进行AllReduce操作因为要汇总梯度再在所以设备上同步。Reduce 就是将所有GPUs上的梯度相加求均值Broadcast 就是分发给所有 GPUs 同步参数。图中实线是实际发生了通信虚线是示意并没有实际通信。公式中使用的变量Reduce Broadcast直接reduce汇总在一个节点上再由该节点 Broadcast缺点计算和传输的负荷全部都在d上且随节点数线性增加啊Recursive Halving and Doubling (Tree)非常普通的树状每次都会传输大小为S的数据Reduce和Broadcast都需要次缺点就是带宽利用不充分。比如Reduce时叶节点只发送数据不接收因此只利用了带宽的一半。有一半的节点没有进行接收操作。比如图中第一步a-bc-d发送数据的时候b和d节点的发送带宽没有被利用起来。同理Broadcast时叶节点只接收数据不发送。并且每一步都需要传输完整的数据块如图的树是不好对数据分块的。比如d在接受c的第二块数据时b同时传来了第一块数据没有办法同时进行Butterfly相当于传输和接收一起进行的tree。值得注意的是该方法不需要再Broadcast了充分利用了接收和发送的带宽但是每一步都需要传输完整的数据块和Tree一样不好切块Ring ReduceRingReduce的讲解太多了我就不仔细分析了第一阶段reduce数据第二阶段broadcast数据两个阶段都需要进行次分层Ring AllReducehttps://arxiv.org/pdf/1807.11205组内reduce-组间AllRuduce-组内broadcastn :组内的节点个数m :组的个数Nnm第一阶段组内普通的reduce论文中一共16个GPU每个组4个直接使用Reduce Broadcast组内节点少带宽大第二阶段组间Ring Reduce第三阶段组内Broadcast总的时间2D-Torushttps://arxiv.org/pdf/1811.05233主要思想也是分层是组内reduce-组间allreduce-组内broadcast。相当于两个ring组间ring组内ringn :组内的节点个数m :组的个数Nnm第一阶段scatter-reduce通信步数n-1第二阶段allreduce是m个节点的RingReduce第三阶段allgather通信步数n-1整体耗时大概是Double Binary Tree基于 double binary tree 的 AllReduce《Two-Tree Algorithms for Full BandwidthBroadcast, Reduction and Scan》double binary tree 于 2009 年在 MPI 中引入并随后在 NCCL2.4 中也引入了此实现https://developer.nvidia.com/blog/massively-scale-deep-learning-training-nccl-2-4/内容基础知识朴素的树状 Reduce 带宽利用不充分broadcast时叶节点只接收数据不发送。reduce时叶节点只发送数据不接收。并且每一步都需要传输完整的数据块Double Binary Tree 分别构造两棵树。Tree1和Tree2会同时运行这样使得双向带宽能被同时利用不难看出Tree1中的叶节点/中间节点在Tree2中变成了中间节点/叶节点。这样就能保证所有节点既是叶节点也是中间节点因此不会出现一棵树时的情况 (所以收发带宽都能用上)如图将Tree1和Tree2的边按一定规律染成红色或者黑色如上图从而有如下很好的性质不会有节点在Tree1和Tree2中连到父节点的边的颜色相同比如node0在Tree1中通过红色的边连到父节点那Tree2中node0一定通过黑色的边连到父节点。不会有节点连到子节点的边颜色相同比如node3在Tree1中是中间节点如果node3通过红色的边连到右子节点那么node3一定通过黑色的边连到左子节点根据上述性质就有了两棵树的工作流程在每一步中从父节点中收数据并将上一步中收到的数据发送给他的一个子节点比如在偶数步骤中使用红色边奇数步骤中使用黑色边这样的话在一个步骤中可以同时收发从而利用了双向带宽。操作在每一个通信步中Node x从两棵树中其中一个父节点接受数据Node x给其作为中间节点的树中的一个子节点传输之前的数据从哪个父节点和给哪个子节点都是一个固定好的scheduleBroadcast需要将node i的数据传输给所有的节点开始时node i 的操作将node i 的数据分为两块可以记为黑色数据和红色数据第一时刻node i 将黑色数据据沿着黑色边传递给子节点第二时刻node i 将红色数据据沿着红色边传递给子节点任意时刻的所有节点注意需要对数据分块流水起来才有这个效果从黑色边的父节点接受黑色数据 i1沿黑色边给子节点传输黑色数据 i从红色边的父节点接受红色数据 i1沿红色边给子节点传输红色数据 i重复1和2耗时Reducereduce相当于就是反向的broadcast子给父节点传数据。假设node i需要汇聚所有节点的结果Tree1把一半的的数据加上同时Tree2 加另一半的数据如果将数据切分为2k块Broadcast如果将数据切分为2k块AllReduce和Broadcast都最多需要执行2h2k次将带入上式这个值是论文中给的可得普通的树耗时因为充分利用了带宽可以明显看到比普通的树在数据传输上耗时少很多直接与卡的数量无关了。计算的耗时也少了很多。其它基于 spanningtree的 AllReduce《Blink: Fast and Generic Collectives for Distributed ML》2D-MeshTPU节点可以同时进行2路send和2路recv而我们普通的服务器都是只有一张网卡只能同时进行1路send和1路recv在TPU上耗时2*(mn-2)*( αS/BS*C)。BlueConnect (3D-Torus)基于异构环境下、拓扑感知的 AllReduce 框架 BlueConnect《BlueConnect: Decomposing All-Reduce for Deep Learning on Heterogeneous Network Hierarchy》 详解 Double Binary Tree、Ring Reduce、2D-Torus Reduce、Butterfly Reduce 时间消耗
网上都没有人仔细讲一讲 Double Binary Tree 具体怎么操作的我来简单讲解一下。具体的细节大家还是需要去看代码。本文还汇总了各种Reduce方法只想看 Double Binary Tree 可以直接跳转目录前置知识Reduce BroadcastRecursive Halving and DoublingButterflyRing Reduce分层Ring AllReduce2D-TorusDouble Binary TreeReduceBroadcastAll其它一些参考连接NVIDIA NCCL 源码学习十二- double binary tree-CSDN博客AllReduce 算法的前世今生 – remaperhttps://zhuanlan.zhihu.com/p/79030485Massively Scale Your Deep Learning Training with NCCL 2.4 | NVIDIA Technical Blog前置知识Allreduce 操作现在是分布式训练中不可或缺的一步操作。Allreduce 操作可以分解为 Reduce 和 Broadcast 两个操作所以绝大部分算法中只需要分别考虑这两个操作怎么进行的即可。Reduce 和 Broadcast 的传输时间都是几乎一样的所以在计算时间时能看到很多系数2只是Reduce 在不考虑别的优化情况如pingpong下会多出一个计算的时间以深度学习模型训练中的数据并行为例需要对梯度进行AllReduce操作因为要汇总梯度再在所以设备上同步。Reduce 就是将所有GPUs上的梯度相加求均值Broadcast 就是分发给所有 GPUs 同步参数。图中实线是实际发生了通信虚线是示意并没有实际通信。公式中使用的变量Reduce Broadcast直接reduce汇总在一个节点上再由该节点 Broadcast缺点计算和传输的负荷全部都在d上且随节点数线性增加啊Recursive Halving and Doubling (Tree)非常普通的树状每次都会传输大小为S的数据Reduce和Broadcast都需要次缺点就是带宽利用不充分。比如Reduce时叶节点只发送数据不接收因此只利用了带宽的一半。有一半的节点没有进行接收操作。比如图中第一步a-bc-d发送数据的时候b和d节点的发送带宽没有被利用起来。同理Broadcast时叶节点只接收数据不发送。并且每一步都需要传输完整的数据块如图的树是不好对数据分块的。比如d在接受c的第二块数据时b同时传来了第一块数据没有办法同时进行Butterfly相当于传输和接收一起进行的tree。值得注意的是该方法不需要再Broadcast了充分利用了接收和发送的带宽但是每一步都需要传输完整的数据块和Tree一样不好切块Ring ReduceRingReduce的讲解太多了我就不仔细分析了第一阶段reduce数据第二阶段broadcast数据两个阶段都需要进行次分层Ring AllReducehttps://arxiv.org/pdf/1807.11205组内reduce-组间AllRuduce-组内broadcastn :组内的节点个数m :组的个数Nnm第一阶段组内普通的reduce论文中一共16个GPU每个组4个直接使用Reduce Broadcast组内节点少带宽大第二阶段组间Ring Reduce第三阶段组内Broadcast总的时间2D-Torushttps://arxiv.org/pdf/1811.05233主要思想也是分层是组内reduce-组间allreduce-组内broadcast。相当于两个ring组间ring组内ringn :组内的节点个数m :组的个数Nnm第一阶段scatter-reduce通信步数n-1第二阶段allreduce是m个节点的RingReduce第三阶段allgather通信步数n-1整体耗时大概是Double Binary Tree基于 double binary tree 的 AllReduce《Two-Tree Algorithms for Full BandwidthBroadcast, Reduction and Scan》double binary tree 于 2009 年在 MPI 中引入并随后在 NCCL2.4 中也引入了此实现https://developer.nvidia.com/blog/massively-scale-deep-learning-training-nccl-2-4/内容基础知识朴素的树状 Reduce 带宽利用不充分broadcast时叶节点只接收数据不发送。reduce时叶节点只发送数据不接收。并且每一步都需要传输完整的数据块Double Binary Tree 分别构造两棵树。Tree1和Tree2会同时运行这样使得双向带宽能被同时利用不难看出Tree1中的叶节点/中间节点在Tree2中变成了中间节点/叶节点。这样就能保证所有节点既是叶节点也是中间节点因此不会出现一棵树时的情况 (所以收发带宽都能用上)如图将Tree1和Tree2的边按一定规律染成红色或者黑色如上图从而有如下很好的性质不会有节点在Tree1和Tree2中连到父节点的边的颜色相同比如node0在Tree1中通过红色的边连到父节点那Tree2中node0一定通过黑色的边连到父节点。不会有节点连到子节点的边颜色相同比如node3在Tree1中是中间节点如果node3通过红色的边连到右子节点那么node3一定通过黑色的边连到左子节点根据上述性质就有了两棵树的工作流程在每一步中从父节点中收数据并将上一步中收到的数据发送给他的一个子节点比如在偶数步骤中使用红色边奇数步骤中使用黑色边这样的话在一个步骤中可以同时收发从而利用了双向带宽。操作在每一个通信步中Node x从两棵树中其中一个父节点接受数据Node x给其作为中间节点的树中的一个子节点传输之前的数据从哪个父节点和给哪个子节点都是一个固定好的scheduleBroadcast需要将node i的数据传输给所有的节点开始时node i 的操作将node i 的数据分为两块可以记为黑色数据和红色数据第一时刻node i 将黑色数据据沿着黑色边传递给子节点第二时刻node i 将红色数据据沿着红色边传递给子节点任意时刻的所有节点注意需要对数据分块流水起来才有这个效果从黑色边的父节点接受黑色数据 i1沿黑色边给子节点传输黑色数据 i从红色边的父节点接受红色数据 i1沿红色边给子节点传输红色数据 i重复1和2耗时Reducereduce相当于就是反向的broadcast子给父节点传数据。假设node i需要汇聚所有节点的结果Tree1把一半的的数据加上同时Tree2 加另一半的数据如果将数据切分为2k块Broadcast如果将数据切分为2k块AllReduce和Broadcast都最多需要执行2h2k次将带入上式这个值是论文中给的可得普通的树耗时因为充分利用了带宽可以明显看到比普通的树在数据传输上耗时少很多直接与卡的数量无关了。计算的耗时也少了很多。其它基于 spanningtree的 AllReduce《Blink: Fast and Generic Collectives for Distributed ML》2D-MeshTPU节点可以同时进行2路send和2路recv而我们普通的服务器都是只有一张网卡只能同时进行1路send和1路recv在TPU上耗时2*(mn-2)*( αS/BS*C)。BlueConnect (3D-Torus)基于异构环境下、拓扑感知的 AllReduce 框架 BlueConnect《BlueConnect: Decomposing All-Reduce for Deep Learning on Heterogeneous Network Hierarchy》