---
title: RHD
description: "当组网增大时，例如增大至4K个rank的场景，Mesh很难组成4K个rank的全连接网络（全连接一个时钟周期就可以完成操作），且资源开销（链路资源，交换资源，同步资源）太大，还可能存在算力和资源开销不匹配的问题。Ring在这种情况下虽然节省资源（只用左手卡和右手卡进行一次收发），但是环内要做太多次，流转太慢。大型规模集群运算有服务器内数据量庞大、Ring环极长的特点，Ring的这种切分数据块的方式就不再占优势。"
url: https://www.hiascend.com/document/detail/zh/canncommercial/latest/API/hcclug/hcclug_000118.html
sourcePath: /source/zh/canncommercial/900/API/hcclug/hcclug_000118.html
indexId: 3fa6d39c12cbfd85ed7a130d5a95e27e970d89eafb7351c45f172e7adf90dbfe59
---
# RHD

#### 算法描述

当组网增大时，例如增大至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算法同样适用于“星型”或“胖树”拓扑互联，算法的时间复杂度是。


#### 耗时计算

Recursive Halving-Doubling为递归二分和倍增算法，对于2的整数次幂，使用Vector/Distance Halving/Doubling策略，对于非2的整数次幂，划分为2r（part1）和p-2r两部分（），先将part1部分合并为r，使得剩余的rank之和为p-r（block），再执行2的整数次幂的HD（Halving-Doubling）算法，最后再在part1部分恢复出2r，得到最终结果。


**表1 Recursive Halving-Doubling算法中各操作计算耗时**

| 操作 | 耗时 |
| --- | --- |
| Broadcast | 根据root rank的奇偶，决定part1部分参与block的为奇数rank还是偶数rank，在block内先执行Distance Halving，再向剩余rank发送一次，总耗时为： |
| ReduceScatter | 使Vector Doubling + Distance Halving（保证Scatter的顺序） 2的整数次幂 非2的整数次幂 第一步（Reduce）: 第二步（非均匀分片的ReduceScatter，某些rank持有2份数据） 需要做次通信 每次交换的最大数据量为： ， 总耗时为： 该步计算比较复杂，这里尝试给出下限和上限 下限： 上限： 第三步（Scatter）: |
| AllGather | 耗时同ReduceScatter，无γ相关部分。 |
| AllReduce | ReduceScatter + AllGather：这里的拆分是不完全的ReduceScatter和AllGather，不需要scatter到所有rank，并且可以采用Vector Halving + Distance Doubling（分层网络下耗时会小，但是无法保证顺序，拆分中也不需要保证顺序） 2的整数次幂 非2的整数次幂 第一步（Reduce）: ReduceScatter: AllGather: 最后一步: 总耗时： |
| Reduce | 当前实现为ReduceScatter + Gather 2的整数次幂: 非2的整数次幂 第一步（Reduce）: ReduceScatter: Gather: 总耗时： |