RHD
【免费下载链接】hccl集合通信库（Huawei Collective Communication Library，简称HCCL）是基于昇腾AI处理器的高性能集合通信库，为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl
算法描述
当组网增大时，例如增大至4K个rank的场景，Mesh很难组成4K个rank的全连接网络（全连接一个时钟周期就可以完成操作），且资源开销（链路资源，交换资源，同步资源）太大，还可能存在算力和资源开销不匹配的问题。Ring在这种情况下虽然节省资源（只用左手卡和右手卡进行一次收发），但是环内要做太多次，流转太慢。大型规模集群运算有服务器内数据量庞大、Ring环极长的特点，Ring的这种切分数据块的方式就不再占优势。
RHD（Recursive Halving-Doubling）算法通过递归加倍及递归折半方式完成NPU间的数据交换，相对Mesh资源消耗较小，相对Ring效率会更高。
RHD算法的实现流程如上图所示，假设有5（22+1）个rank，首先将rank1的数据合并到rank0，变成4（22）个rank，然后将这4个rank的数据两两对半交换数据并求和，即ReduceScatter操作。下一阶段，将这4个rank的数据两两拼接，即AllGather操作。最后，将rank0的数据复制到rank1，至此每个rank都具有所有rank的全量数据之和。
RHD算法同样适用于“星型”或“胖树”拓扑互联，算法的时间复杂度是$\lceil log_{2}N \rceil$。
耗时计算
Recursive Halving-Doubling为递归二分和倍增算法，对于2的整数次幂，使用Vector/Distance Halving/Doubling策略，对于非2的整数次幂，划分为2r（part1）和p-2r两部分（$r=p-2^{\lfloor log(p) \rfloor} $），先将part1部分合并为r，使得剩余的rank之和为p-r（block），再执行2的整数次幂的HD（Halving-Doubling）算法，最后再在part1部分恢复出2r，得到最终结果。
表 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}(\alpha+\frac{1}{p}\lceil \frac{p}{2^i} \rceil n\beta+\frac{1}{p}\lceil \frac{p}{2^i} \rceil n\gamma)=\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，无$\gamma$相关部分。 |
| Allreduce | ReduceScatter + AllGather：这里的拆分是不完全的ReduceScatter和AllGather，不需要scatter到所有rank，并且可以采用Vector Halving + Distance Doubling（分层网络下耗时会小，但是无法保证顺序，拆分中也不需要保证顺序）。 2的整数次幂: $2log(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的整数次幂: $2log(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}$ |
【免费下载链接】hccl集合通信库（Huawei Collective Communication Library，简称HCCL）是基于昇腾AI处理器的高性能集合通信库，为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
