HCCL RHD（Recursive Halving-Doubling）算法深度解析：递归二分倍增集合通信原理、适用场景与耗时模型-育师

HCCL RHD（Recursive Halving-Doubling）算法深度解析：递归二分倍增集合通信原理、适用场景与耗时模型

【免费下载链接】hccl集合通信库（Huawei Collective Communication Library，简称HCCL）是基于昇腾AI处理器的高性能集合通信库，为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl

本篇技术指南聚焦华为集合通信库 HCCL（Huawei Collective Communication Library）中用于 Server 间与超节点间集合通信的 RHD（Recursive 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 个 rank（rank0 ~ 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.h：

enum 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.h）；
CalcRecursiveHalvingDobuleLinkReleation(rank, rankSize, rootRank, linkRelation)：计算 rank 在整个 RHD 过程中的逐轮通信伙伴（见 alg_template_base.h）；
CalcRecursiveHdLinkRelationForFirstScene与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_ALGO="level0:NA;level1:<algo>;level2:<algo>"

level0：Server 内通信算法，当前仅支持配置为NA；
level1：Server 间通信算法，RHD 对应取值H-D_R；
level2：超节点间通信算法，RHD 同样对应取值H-D_R。

也可按算子类型粒度配置（/分隔多个算子的配置项）：

export HCCL_ALGO="<op0>=level0:NA;level1:<algo0>;level2:<algo1>/<op1>=level0: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_R；
level2配置当前仅适用于 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 的整数次幂规模，则划分为 2r（part1）与 p-2r（剩余 block）两部分，其中 $r = p - 2^{\lfloor \log(p) \rfloor}$：先将 part1 部分合并为 r，使剩余 rank 之和为 p-r（block），再对 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-i+1}} \rceil \frac{n}{p}\quad (i=1,2,...,k)$，总耗时为： $\sum_{i=1}^{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_{i=1}^{k}\lceil \frac{p}{2^i} \rceil + \frac{n\gamma}{p}\sum_{i=1}^{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^{k+1} - 2)\frac{n\beta}{p} + (2^{k+1} - 2)\frac{n\gamma}{p}$ 第三步（Scatter）：$\alpha + \frac{1}{p}n\beta$
AllGather	耗时同 ReduceScatter，无 γ 相关部分
Allreduce	ReduceScatter + 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），从而最大化利用各层级链路能力。

总结

RHD（Recursive 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_ALGO="level0:NA;level1:H-D_R;..."手动指定（详见 HCCL_ALGO）。

读者如需深入了解 RHD 与其他算法（Mesh、Ring、NHR、NB、Pipeline、Pairwise、AHC）的选型差异，可继续阅读算法简介及各算法独立文档（如 Ring.md、Mesh.md、NHR.md）。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考