当前位置：首页 > news >正文

【NCCL】DBT算法(double binary tree，双二叉树)

news 来源：原创 2025/8/3 19:25:43

前言

ring 不足，需要 tree

朴素二叉tree只利用了一半带宽，需要双二叉 tree

双二叉树的构造

ringvs 双二叉树测试

ring和tree的选择

nccl tree

tree搜索

基本概念解释

最大化局部性构建二叉树的方式

这种构建方式的好处

示例说明

前言

参考：万卡集群通信优化算法双二叉树：https://www.bilibili.com/video/BV1zSpnezEB8

3.1 NCCL源码二叉树构建算法：https://www.bilibili.com/video/BV1DErsYwEhc/

Massively Scale Your Deep Learning Training with NCCL 2.4 | NVIDIA Technical Blog

"double binary tree" 在并行计算/NCCL语境中特指一种用于高效集合通信的树形拓扑结构，由两个并行的二叉树组成。

从 ring 算法到 tree 算法，把时间复杂度从 n 提升到了 logn

ring-->tree-->db tree

ring 不足，需要 tree

ring算法适合小规模集群，能够充分利用上行和下行的带宽。但是环越大，延迟线性增加，不适合大规模集群。

为了解决这个问题，线引入二维环算法，但仍然无法完全解决该问题，最后由引入了Tree算法

朴素二叉tree只利用了一半带宽，需要双二叉 tree

朴素二叉树（native binary tree）

缺点:叶子节点只接收不发送数据，只利用了带宽的一半，浪费了大量的（叶子节点的）带宽。

假设root节点要broadcast一个消息M给所有节点，root会将M发送给他的子节点，其他所有的节点收到消息M后再发送给子节点，叶节点因为没有子节点，所以叶结点只会接收M。这个过程可以将M切分为k个block，从而可以流水线起来。

双二叉树（Double Binary Tree）

为了解决朴素二叉树只利用了带宽的一半的缺点，引入双二叉树，算法介绍：

双二叉树的构造

构造双二叉树有两种方法：shift位移法和mirror(镜像)法，

shift位移法：也就是先按正常序号构造T1，然后将每个节点的序号移一位，然后构造第T2。

mirror(镜像)法：既先按正常序号构造T1，然后将全部节点序号反转，然后构造第T2。

英伟达的双二叉树算法

NCCL 中，使用最大化局部性(见附录说明)的模式来构建二叉树，

英伟达通过反转T1树的方式构建双二叉树的T2：

ringvs 双二叉树测试

相比ring，双二叉树的优化效果测试：

ring和tree的选择

NVIDIA NCCL 源码学习（十二）- double binary tree-CSDN博客

nccl tree

nccl中的tree只用于节点之间，节点内是一条链，2.7.8版本使用的pattern为NCCL_TOPO_PATTERN_SPLIT_TREE，假设为4机32卡，对于T2后边再介绍，T1如下所示：

由于allreduce可以拆分为reduce和broadcast两个过程，所以nccl tree allreduce先执行reduce，数据按照图中箭头方向流动，称为上行阶段，从rank15，rank31，rank23，rank7开始一直reduce到rank 0，rank0拿到全局reduce的结果之后再按照箭头反方向开始流动，称为下行阶段，broadcast到所有卡。

tree搜索

如上所述，节点内为链，因此机内tree搜索的过程和ring搜索很像，指定pattern为NCCL_TOPO_PATTERN_SPLIT_TREE，然后执行ncclTopoCompute。

附录：

基本概念解释

局部性：在计算机系统中，局部性原理是指程序和数据倾向于集中访问某些区域。在多 GPU 系统中，局部性通常指 GPU 之间的物理接近性或者通信延迟的接近性。例如，同一服务器内的 GPU 之间的通信延迟往往比不同服务器之间的 GPU 通信延迟要小，这种物理和延迟上的接近性就是局部性的体现。

最大化局部性构建二叉树的方式

物理位置优先：优先考虑将物理位置接近的 GPU 连接在一起。例如，在一个包含多个服务器的集群中，每个服务器上有多个 GPU，构建二叉树时会先把同一服务器内的 GPU 相互连接，形成子树，然后再将这些子树连接起来。这样可以减少跨服务器的数据传输，因为跨服务器的通信通常伴随着更高的延迟和更低的带宽。
通信延迟最小化：除了物理位置，还会考虑 GPU 之间的实际通信延迟。通过测量不同 GPU 对之间的通信延迟，将延迟较小的 GPU 优先连接在一起。例如，某些 GPU 可能通过高速的 NVLink 互连，而有些则通过 PCIe 总线连接，NCCL 会尽量利用 NVLink 这种低延迟、高带宽的连接来构建二叉树。

这种构建方式的好处

减少通信开销：通过最大化局部性，大部分的数据传输可以在低延迟、高带宽的通道上进行，从而减少了通信延迟和数据传输时间。例如，在 All - Reduce 操作中，数据可以在局部子树内先进行规约，然后再将结果向上传递，避免了大量数据在高延迟的通道上传输。
提高并行性：局部性好的二叉树结构可以让更多的 GPU 同时进行数据传输和计算，提高了整个系统的并行性。例如，同一子树内的 GPU 可以并行地进行数据交换，而不会相互干扰。

示例说明

假设一个系统中有 8 个 GPU，分布在 2 个服务器上，每个服务器有 4 个 GPU。使用最大化局部性的模式构建二叉树时，会先在每个服务器内部构建一个包含 4 个 GPU 的子树，然后再将这两个子树连接起来。这样在进行集体通信操作时，每个服务器内的 4 个 GPU 可以先在本地完成部分数据处理，然后再在两个服务器之间进行数据交换，从而减少了跨服务器的通信开销。

前言

ring 不足，需要 tree

朴素二叉tree只利用了一半带宽，需要 双二叉 tree

双二叉树的构造

ringvs 双二叉树 测试

ring和tree的选择

nccl tree

tree搜索

附录：

基本概念解释

最大化局部性构建二叉树的方式

这种构建方式的好处

示例说明

相关文章：

朴素二叉tree只利用了一半带宽，需要双二叉 tree

ringvs 双二叉树测试