HCCL RHDRecursive Halving-Doubling算法深度解析递归二分倍增集合通信原理、适用场景与耗时模型【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl本篇技术指南聚焦华为集合通信库 HCCLHuawei Collective Communication Library中用于 Server 间与超节点间集合通信的 RHDRecursive Halving-Doubling递归二分倍增算法。文章从大型集群组网下 Mesh 与 Ring 的瓶颈切入详解 RHD 的递归折半/加倍通信流程与链路关系计算并给出各集合通信算子的 α–β 耗时模型计算公式帮助读者理解 HCCL 为何在 2 的整数次幂节点规模下优先选用 RHD以及如何通过HCCL_ALGO环境变量按需启用。为什么大规模组网需要 RHD在集合通信算法的选型中Mesh全连接、Ring环与RHD递归二分倍增代表了三种不同的权衡思路各自适用于不同的网络规模与数据量场景。Mesh 算法节点两两全互联理论上一个时钟周期即可完成操作通信步数最少、时延最低。但当组网规模增大到 4K 个 rank 级别时Mesh 几乎无法构建全连接网络——链路资源、交换资源与同步资源的开销呈平方级增长甚至可能出现算力和资源开销不匹配的问题。Ring 算法每个 rank 只与左手卡和右手卡各做一次收发通信关系简单、资源占用小数据流转呈线性步数。但环内要完成太多次流转速度慢且大规模集群中服务器内数据量庞大、Ring 环极长的特点使 Ring 切分数据块的方式不再占优。RHD 算法通过**递归加倍Doubling与递归折半Halving**完成 NPU 间的数据交换。通信步数呈对数复杂度$O(\log N)$相对 Mesh 资源消耗小得多相对 Ring 效率更高是 Mesh 与 Ring 之间兼顾资源与性能的折中方案。从 HCCL 的自适应算法选择策略看详见 算法简介RHD 定位为 Server 间/超节点间算法典型适用场景为通信域内 Server或超节点个数是 2 的整数次幂且 Pipeline 算法不适用或节点个数不是 2 的整数次幂但通信数据量较小的场景。算法描述递归折半与加倍的核心流程RHD 算法的执行流程可用一个 5 rank$2^{2}1$的例子直观说明其核心思想是先把非 2 的整数次幂规模归并成 2 的整数次幂再在 2 的整数次幂子集内递归折半归约、递归加倍拼接最后把结果扩散到被归并的 rank。假设共有 5 个 rankrank0 ~ rank4以 AllReduce 为例归并阶段将 rank1 的数据合并到 rank0得到 4$2^{2}$个有效 rank 的通信子集ReduceScatter 阶段将 4 个 rank 的数据两两对半交换并求和完成数据块在 rank 间的分布归约AllGather 阶段将这 4 个 rank 的数据两两拼接使每个 rank 都持有完整归约结果的一部分副本扩散阶段将 rank0 的数据复制到 rank1至此每个 rank 都持有所有 rank 数据的全量之和。RHD 算法同样适用于星型或胖树拓扑互联其算法时间复杂度为 $\lceil \log_{2}N \rceil$即通信步数与节点数的对数成正比这正是其在大规模组网下相比 Ring 线性步数的核心优势。源码视角RHD 链路关系计算在 HCCL 源码中RHD 的通信模式被抽象为HalvingDoublingType枚举定义于 alg_template_base.henum class HalvingDoublingType { BINARY_BLOCK_HALVING_DOUBLING, RECURSIVE_HALVING_DOUBLING, RESERVED_ALGORITHM_TYPE };其中RECURSIVE_HALVING_DOUBLING即本文所述的 RHD 模式。算法模板基类AlgTemplateBase通过以下静态方法为每个 rank 计算其在递归折半/加倍过程中的链路关系CalcLinksRelation(rank, rankSize, rootRank, algorithmType)对外统一入口默认即采用RECURSIVE_HALVING_DOUBLING见 alg_template_base.hCalcRecursiveHalvingDobuleLinkReleation(rank, rankSize, rootRank, linkRelation)计算 rank 在整个 RHD 过程中的逐轮通信伙伴见 alg_template_base.hCalcRecursiveHdLinkRelationForFirstScene与CalcRecursiveHdLinkRelationForSecondScene分别处理非 2 的整数次幂场景下先归并part1 合并再执行整数次幂 HD两个阶段的链路关系见 alg_template_base.h。从源码结构可以看出RHD 对非 2 的整数次幂规模的处理正是原文档耗时计算中先合并 part1、再对 2 的整数次幂子集做 HD、最后恢复 part1的三段式流程二者在实现层面完全对应。此外RunStage枚举RUN_REDUCE_SCATTER/RUN_ALLGATHER/RUN_ALLREDUCE见 alg_template_base.h也印证了 RHD 在 AllReduce 中被拆解为 ReduceScatter AllGather 两个阶段执行。RHD 在 HCCL 中的定位与启用方式算法定位Server 间 / 超节点间算法HCCL 通常按节点内/节点间/超节点间分级执行集合通信不同层级的链路带宽不同详见 分级通信原理。RHD 属于Server 间level1与超节点间level2的通信算法HCCL 默认开启自适应算法选择会依据产品形态、数据量与节点个数自动决定是否启用 RHD用户默认无需配置。通过 HCCL_ALGO 环境变量手动指定当需要手工指定 Server 间/超节点间算法时可通过环境变量 HCCL_ALGO 配置其中 RHD 的取值名为H-D_R。全局配置方式如下export HCCL_ALGOlevel0:NA;level1:algo;level2:algolevel0Server 内通信算法当前仅支持配置为NAlevel1Server 间通信算法RHD 对应取值H-D_Rlevel2超节点间通信算法RHD 同样对应取值H-D_R。也可按算子类型粒度配置/分隔多个算子的配置项export HCCL_ALGOop0level0:NA;level1:algo0;level2:algo1/op1level0:NA;level1:algo3;level2:algo4注意事项源自 HCCL_ALGO.md一旦通过HCCL_ALGO指定算法自适应算法选择功能即不再生效以用户指定为准某些通信算子在使用特定类型 AI 处理器且数据量较小时算法仍由 HCCL 自适应选择不受该环境变量控制对 Atlas 训练系列产品910 系列当通信域内 Server 个数为非 2 的整数次幂时默认使用ring其他场景默认使用H-D_R超节点间level2不配置时当超节点个数小于 8 且不是 2 的整数次幂采用ring其他场景默认采用H-D_Rlevel2配置当前仅适用于 Ascend 950PR/Ascend 950DT仅 NHR与 Atlas A3 训练/推理系列产品AI_CPU 展开模式展开模式由 HCCL_OP_EXPANSION_MODE 控制各产品对 RHD 支持的算子范围可查阅 Server间通信算法支持度列表 与 超节点间通信算法支持度列表。耗时计算α–β 模型下的 RHD 性能分析HCCL 采用α–β 模型Hockney 模型进行性能评估变量定义见 算法简介α节点间固定时延s由通信硬件与底层软件栈决定β每 byte 数据传输耗时s/Byte由通信链路能力决定n节点间通信的数据大小Byte由通信算法决定γ每 byte 数据归约计算耗时s/Byte由计算硬件能力决定p通信域节点个数影响通信步数。单步传输并归约 n byte 数据的耗时为 $D \alpha n\beta n\gamma$。对于 2 的整数次幂规模RHD 使用Vector/Distance Halving/Doubling策略对于非 2 的整数次幂规模则划分为 2rpart1与 p-2r剩余 block两部分其中 $r p - 2^{\lfloor \log(p) \rfloor}$先将 part1 部分合并为 r使剩余 rank 之和为 p-rblock再对 block 执行 2 的整数次幂 HD 算法最后在 part1 部分恢复出 2r得到最终结果。各操作计算耗时汇总下表完整列出 RHD 算法中各集合通信操作的耗时公式源自 RHD.md表1Recursive Halving-Doubling 算法中各操作计算耗时操作耗时Broadcast根据 root rank 的奇偶决定 part1 部分参与 block 的是奇数 rank 还是偶数 rank在 block 内先执行 Distance Halving再向剩余 rank 发送一次总耗时为$\lceil \log(p) \rceil(\alpha n\beta)$ReduceScatter使用 Vector Doubling Distance Halving保证 Scatter 的顺序。2 的整数次幂时耗时计算公式为$\log(p)\alpha \frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂时第一步Reduce$\alpha n\beta n\gamma$第二步非均匀分片的 ReduceScatter某些 rank 持有 2 份数据需要做 $k \lfloor \log(p) \rfloor$ 次通信每次交换的最大数据量为 $n_i \lceil \frac{p}{2^{k-i1}} \rceil \frac{n}{p}\quad (i1,2,...,k)$总耗时为$\sum_{i1}^{k}\left(\alpha \frac{1}{p}\lceil \frac{p}{2^i} \rceil n\beta \frac{1}{p}\lceil \frac{p}{2^i} \rceil n\gamma\right) \lfloor \log(p) \rfloor\alpha \frac{n\beta}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil \frac{n\gamma}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil$该步计算较复杂给出下限与上限下限$k\alpha (k 2^{k} - 1)\frac{n\beta}{p} (k 2^{k} - 1)\frac{n\gamma}{p}$上限$k\alpha (2^{k1} - 2)\frac{n\beta}{p} (2^{k1} - 2)\frac{n\gamma}{p}$第三步Scatter$\alpha \frac{1}{p}n\beta$AllGather耗时同 ReduceScatter无 γ 相关部分AllreduceReduceScatter AllGather这里的拆分是不完全的 ReduceScatter 和 AllGather不需要 scatter 到所有 rank且可以采用 Vector Halving Distance Doubling分层网络下耗时会小但无法保证顺序拆分中也不需要保证顺序。2 的整数次幂$2\log(p)\alpha 2\frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂第一步Reduce$\alpha n\beta n\gamma$ReduceScatter$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta \frac{p^{\prime}-1}{p^{\prime}}n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$AllGather$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$最后一步$\alpha n\beta$总耗时$(2\lfloor \log(p) \rfloor 2)\alpha (2\frac{p^{\prime}-1}{p^{\prime}} 2)n\beta (\frac{p^{\prime}-1}{p^{\prime}} 1)n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$Reduce当前实现为 ReduceScatter Gather。2 的整数次幂$2\log(p)\alpha 2\frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂第一步Reduce$\alpha n\beta n\gamma$ReduceScatter$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta \frac{p^{\prime}-1}{p^{\prime}}n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$Gather$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$总耗时$(2\lfloor \log(p) \rfloor 1)\alpha (2\frac{p^{\prime}-1}{p^{\prime}} 1)n\beta (\frac{p^{\prime}-1}{p^{\prime}} 1)n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$耗时模型解读从公式中可以读出 RHD 的几条关键性质对数级时延优势无论哪种操作时延项α 的系数都只与 $\lfloor \log(p) \rfloor$ 成正比而非像 Ring 那样随 p 线性增长这正是 RHD 在大规模组网如 4K rank下性能占优的根本原因。非 2 次幂的额外开销非 2 的整数次幂规模下第一步 Reduce 的 $\alpha n\beta n\gamma$ 与最后一步 Scatter/Gather 的 $\alpha \frac{1}{p}n\beta$ 会引入额外通信量这也对应了算法简介中非 2 次幂节点规模下会引入额外的通信量的说明——因此 HCCL 在非 2 次幂场景通常只在数据量较小时才选用 RHD。计算与传输的对称性ReduceScatter 阶段 β 与 γ 的系数完全相同每次交换既传输又归约而 AllGather 只做拼接、无归约计算故耗时中无 γ 项。与分级通信的配合在如 AllReduce 的三级通信中RHD 承担 Server 间或超节点间一级的通信Server 内仍由 Mesh/Ring 等完成参见 分级通信原理 中的阶段划分Server 内 ReduceScatter → Server 间 AllReduce → Server 内 AllGather从而最大化利用各层级链路能力。总结RHDRecursive Halving-Doubling是 HCCL 在 Server 间与超节点间通信中的关键算法之一以对数级通信步数在 Mesh 与 Ring 之间取得了资源消耗与通信效率的平衡适用规模2 的整数次幂节点规模下优势最明显非 2 次幂规模会引入额外通信量仅在数据量较小时值得选用实现机制通过递归折半Halving完成归约分布、递归加倍Doubling完成结果拼接非 2 次幂规模采用先归并 part1 → 整数次幂 HD → 恢复 part1的三段式流程与源码 alg_template_base.h 中CalcRecursiveHalvingDobuleLinkReleation等实现一一对应性能模型α–β 模型下各操作耗时均以 $\lceil \log_2 p \rceil$ 为时延阶数公式汇总见上文表1启用方式默认由 HCCL 自适应选择也可通过export HCCL_ALGOlevel0:NA;level1:H-D_R;...手动指定详见 HCCL_ALGO。读者如需深入了解 RHD 与其他算法Mesh、Ring、NHR、NB、Pipeline、Pairwise、AHC的选型差异可继续阅读 算法简介 及各算法独立文档如 Ring.md、Mesh.md、NHR.md。【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 HCCL RHD（Recursive Halving-Doubling）算法深度解析：递归二分倍增集合通信原理、适用场景与耗时模型
HCCL RHDRecursive Halving-Doubling算法深度解析递归二分倍增集合通信原理、适用场景与耗时模型【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl本篇技术指南聚焦华为集合通信库 HCCLHuawei Collective Communication Library中用于 Server 间与超节点间集合通信的 RHDRecursive Halving-Doubling递归二分倍增算法。文章从大型集群组网下 Mesh 与 Ring 的瓶颈切入详解 RHD 的递归折半/加倍通信流程与链路关系计算并给出各集合通信算子的 α–β 耗时模型计算公式帮助读者理解 HCCL 为何在 2 的整数次幂节点规模下优先选用 RHD以及如何通过HCCL_ALGO环境变量按需启用。为什么大规模组网需要 RHD在集合通信算法的选型中Mesh全连接、Ring环与RHD递归二分倍增代表了三种不同的权衡思路各自适用于不同的网络规模与数据量场景。Mesh 算法节点两两全互联理论上一个时钟周期即可完成操作通信步数最少、时延最低。但当组网规模增大到 4K 个 rank 级别时Mesh 几乎无法构建全连接网络——链路资源、交换资源与同步资源的开销呈平方级增长甚至可能出现算力和资源开销不匹配的问题。Ring 算法每个 rank 只与左手卡和右手卡各做一次收发通信关系简单、资源占用小数据流转呈线性步数。但环内要完成太多次流转速度慢且大规模集群中服务器内数据量庞大、Ring 环极长的特点使 Ring 切分数据块的方式不再占优。RHD 算法通过**递归加倍Doubling与递归折半Halving**完成 NPU 间的数据交换。通信步数呈对数复杂度$O(\log N)$相对 Mesh 资源消耗小得多相对 Ring 效率更高是 Mesh 与 Ring 之间兼顾资源与性能的折中方案。从 HCCL 的自适应算法选择策略看详见 算法简介RHD 定位为 Server 间/超节点间算法典型适用场景为通信域内 Server或超节点个数是 2 的整数次幂且 Pipeline 算法不适用或节点个数不是 2 的整数次幂但通信数据量较小的场景。算法描述递归折半与加倍的核心流程RHD 算法的执行流程可用一个 5 rank$2^{2}1$的例子直观说明其核心思想是先把非 2 的整数次幂规模归并成 2 的整数次幂再在 2 的整数次幂子集内递归折半归约、递归加倍拼接最后把结果扩散到被归并的 rank。假设共有 5 个 rankrank0 ~ rank4以 AllReduce 为例归并阶段将 rank1 的数据合并到 rank0得到 4$2^{2}$个有效 rank 的通信子集ReduceScatter 阶段将 4 个 rank 的数据两两对半交换并求和完成数据块在 rank 间的分布归约AllGather 阶段将这 4 个 rank 的数据两两拼接使每个 rank 都持有完整归约结果的一部分副本扩散阶段将 rank0 的数据复制到 rank1至此每个 rank 都持有所有 rank 数据的全量之和。RHD 算法同样适用于星型或胖树拓扑互联其算法时间复杂度为 $\lceil \log_{2}N \rceil$即通信步数与节点数的对数成正比这正是其在大规模组网下相比 Ring 线性步数的核心优势。源码视角RHD 链路关系计算在 HCCL 源码中RHD 的通信模式被抽象为HalvingDoublingType枚举定义于 alg_template_base.henum class HalvingDoublingType { BINARY_BLOCK_HALVING_DOUBLING, RECURSIVE_HALVING_DOUBLING, RESERVED_ALGORITHM_TYPE };其中RECURSIVE_HALVING_DOUBLING即本文所述的 RHD 模式。算法模板基类AlgTemplateBase通过以下静态方法为每个 rank 计算其在递归折半/加倍过程中的链路关系CalcLinksRelation(rank, rankSize, rootRank, algorithmType)对外统一入口默认即采用RECURSIVE_HALVING_DOUBLING见 alg_template_base.hCalcRecursiveHalvingDobuleLinkReleation(rank, rankSize, rootRank, linkRelation)计算 rank 在整个 RHD 过程中的逐轮通信伙伴见 alg_template_base.hCalcRecursiveHdLinkRelationForFirstScene与CalcRecursiveHdLinkRelationForSecondScene分别处理非 2 的整数次幂场景下先归并part1 合并再执行整数次幂 HD两个阶段的链路关系见 alg_template_base.h。从源码结构可以看出RHD 对非 2 的整数次幂规模的处理正是原文档耗时计算中先合并 part1、再对 2 的整数次幂子集做 HD、最后恢复 part1的三段式流程二者在实现层面完全对应。此外RunStage枚举RUN_REDUCE_SCATTER/RUN_ALLGATHER/RUN_ALLREDUCE见 alg_template_base.h也印证了 RHD 在 AllReduce 中被拆解为 ReduceScatter AllGather 两个阶段执行。RHD 在 HCCL 中的定位与启用方式算法定位Server 间 / 超节点间算法HCCL 通常按节点内/节点间/超节点间分级执行集合通信不同层级的链路带宽不同详见 分级通信原理。RHD 属于Server 间level1与超节点间level2的通信算法HCCL 默认开启自适应算法选择会依据产品形态、数据量与节点个数自动决定是否启用 RHD用户默认无需配置。通过 HCCL_ALGO 环境变量手动指定当需要手工指定 Server 间/超节点间算法时可通过环境变量 HCCL_ALGO 配置其中 RHD 的取值名为H-D_R。全局配置方式如下export HCCL_ALGOlevel0:NA;level1:algo;level2:algolevel0Server 内通信算法当前仅支持配置为NAlevel1Server 间通信算法RHD 对应取值H-D_Rlevel2超节点间通信算法RHD 同样对应取值H-D_R。也可按算子类型粒度配置/分隔多个算子的配置项export HCCL_ALGOop0level0:NA;level1:algo0;level2:algo1/op1level0:NA;level1:algo3;level2:algo4注意事项源自 HCCL_ALGO.md一旦通过HCCL_ALGO指定算法自适应算法选择功能即不再生效以用户指定为准某些通信算子在使用特定类型 AI 处理器且数据量较小时算法仍由 HCCL 自适应选择不受该环境变量控制对 Atlas 训练系列产品910 系列当通信域内 Server 个数为非 2 的整数次幂时默认使用ring其他场景默认使用H-D_R超节点间level2不配置时当超节点个数小于 8 且不是 2 的整数次幂采用ring其他场景默认采用H-D_Rlevel2配置当前仅适用于 Ascend 950PR/Ascend 950DT仅 NHR与 Atlas A3 训练/推理系列产品AI_CPU 展开模式展开模式由 HCCL_OP_EXPANSION_MODE 控制各产品对 RHD 支持的算子范围可查阅 Server间通信算法支持度列表 与 超节点间通信算法支持度列表。耗时计算α–β 模型下的 RHD 性能分析HCCL 采用α–β 模型Hockney 模型进行性能评估变量定义见 算法简介α节点间固定时延s由通信硬件与底层软件栈决定β每 byte 数据传输耗时s/Byte由通信链路能力决定n节点间通信的数据大小Byte由通信算法决定γ每 byte 数据归约计算耗时s/Byte由计算硬件能力决定p通信域节点个数影响通信步数。单步传输并归约 n byte 数据的耗时为 $D \alpha n\beta n\gamma$。对于 2 的整数次幂规模RHD 使用Vector/Distance Halving/Doubling策略对于非 2 的整数次幂规模则划分为 2rpart1与 p-2r剩余 block两部分其中 $r p - 2^{\lfloor \log(p) \rfloor}$先将 part1 部分合并为 r使剩余 rank 之和为 p-rblock再对 block 执行 2 的整数次幂 HD 算法最后在 part1 部分恢复出 2r得到最终结果。各操作计算耗时汇总下表完整列出 RHD 算法中各集合通信操作的耗时公式源自 RHD.md表1Recursive Halving-Doubling 算法中各操作计算耗时操作耗时Broadcast根据 root rank 的奇偶决定 part1 部分参与 block 的是奇数 rank 还是偶数 rank在 block 内先执行 Distance Halving再向剩余 rank 发送一次总耗时为$\lceil \log(p) \rceil(\alpha n\beta)$ReduceScatter使用 Vector Doubling Distance Halving保证 Scatter 的顺序。2 的整数次幂时耗时计算公式为$\log(p)\alpha \frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂时第一步Reduce$\alpha n\beta n\gamma$第二步非均匀分片的 ReduceScatter某些 rank 持有 2 份数据需要做 $k \lfloor \log(p) \rfloor$ 次通信每次交换的最大数据量为 $n_i \lceil \frac{p}{2^{k-i1}} \rceil \frac{n}{p}\quad (i1,2,...,k)$总耗时为$\sum_{i1}^{k}\left(\alpha \frac{1}{p}\lceil \frac{p}{2^i} \rceil n\beta \frac{1}{p}\lceil \frac{p}{2^i} \rceil n\gamma\right) \lfloor \log(p) \rfloor\alpha \frac{n\beta}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil \frac{n\gamma}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil$该步计算较复杂给出下限与上限下限$k\alpha (k 2^{k} - 1)\frac{n\beta}{p} (k 2^{k} - 1)\frac{n\gamma}{p}$上限$k\alpha (2^{k1} - 2)\frac{n\beta}{p} (2^{k1} - 2)\frac{n\gamma}{p}$第三步Scatter$\alpha \frac{1}{p}n\beta$AllGather耗时同 ReduceScatter无 γ 相关部分AllreduceReduceScatter AllGather这里的拆分是不完全的 ReduceScatter 和 AllGather不需要 scatter 到所有 rank且可以采用 Vector Halving Distance Doubling分层网络下耗时会小但无法保证顺序拆分中也不需要保证顺序。2 的整数次幂$2\log(p)\alpha 2\frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂第一步Reduce$\alpha n\beta n\gamma$ReduceScatter$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta \frac{p^{\prime}-1}{p^{\prime}}n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$AllGather$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$最后一步$\alpha n\beta$总耗时$(2\lfloor \log(p) \rfloor 2)\alpha (2\frac{p^{\prime}-1}{p^{\prime}} 2)n\beta (\frac{p^{\prime}-1}{p^{\prime}} 1)n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$Reduce当前实现为 ReduceScatter Gather。2 的整数次幂$2\log(p)\alpha 2\frac{p-1}{p}n\beta \frac{p-1}{p}n\gamma$非 2 的整数次幂第一步Reduce$\alpha n\beta n\gamma$ReduceScatter$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta \frac{p^{\prime}-1}{p^{\prime}}n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$Gather$\lfloor \log(p) \rfloor\alpha \frac{p^{\prime}-1}{p^{\prime}}n\beta,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$总耗时$(2\lfloor \log(p) \rfloor 1)\alpha (2\frac{p^{\prime}-1}{p^{\prime}} 1)n\beta (\frac{p^{\prime}-1}{p^{\prime}} 1)n\gamma,\quad p^{\prime} 2^{\lfloor \log(p) \rfloor}$耗时模型解读从公式中可以读出 RHD 的几条关键性质对数级时延优势无论哪种操作时延项α 的系数都只与 $\lfloor \log(p) \rfloor$ 成正比而非像 Ring 那样随 p 线性增长这正是 RHD 在大规模组网如 4K rank下性能占优的根本原因。非 2 次幂的额外开销非 2 的整数次幂规模下第一步 Reduce 的 $\alpha n\beta n\gamma$ 与最后一步 Scatter/Gather 的 $\alpha \frac{1}{p}n\beta$ 会引入额外通信量这也对应了算法简介中非 2 次幂节点规模下会引入额外的通信量的说明——因此 HCCL 在非 2 次幂场景通常只在数据量较小时才选用 RHD。计算与传输的对称性ReduceScatter 阶段 β 与 γ 的系数完全相同每次交换既传输又归约而 AllGather 只做拼接、无归约计算故耗时中无 γ 项。与分级通信的配合在如 AllReduce 的三级通信中RHD 承担 Server 间或超节点间一级的通信Server 内仍由 Mesh/Ring 等完成参见 分级通信原理 中的阶段划分Server 内 ReduceScatter → Server 间 AllReduce → Server 内 AllGather从而最大化利用各层级链路能力。总结RHDRecursive Halving-Doubling是 HCCL 在 Server 间与超节点间通信中的关键算法之一以对数级通信步数在 Mesh 与 Ring 之间取得了资源消耗与通信效率的平衡适用规模2 的整数次幂节点规模下优势最明显非 2 次幂规模会引入额外通信量仅在数据量较小时值得选用实现机制通过递归折半Halving完成归约分布、递归加倍Doubling完成结果拼接非 2 次幂规模采用先归并 part1 → 整数次幂 HD → 恢复 part1的三段式流程与源码 alg_template_base.h 中CalcRecursiveHalvingDobuleLinkReleation等实现一一对应性能模型α–β 模型下各操作耗时均以 $\lceil \log_2 p \rceil$ 为时延阶数公式汇总见上文表1启用方式默认由 HCCL 自适应选择也可通过export HCCL_ALGOlevel0:NA;level1:H-D_R;...手动指定详见 HCCL_ALGO。读者如需深入了解 RHD 与其他算法Mesh、Ring、NHR、NB、Pipeline、Pairwise、AHC的选型差异可继续阅读 算法简介 及各算法独立文档如 Ring.md、Mesh.md、NHR.md。【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考