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，得到最终结果。
|
操作 |
耗时 |
|---|---|
|
Broadcast |
根据root rank的奇偶，决定part1部分参与block的为奇数rank还是偶数rank，在block内先执行Distance Halving，再向剩余rank发送一次，总耗时为：
|
|
ReduceScatter |
使Vector Doubling + Distance Halving（保证Scatter的顺序）
|
|
AllGather |
耗时同ReduceScatter，无γ相关部分。 |
|
AllReduce |
ReduceScatter + AllGather：这里的拆分是不完全的ReduceScatter和AllGather，不需要scatter到所有rank，并且可以采用Vector Halving + Distance Doubling（分层网络下耗时会小，但是无法保证顺序，拆分中也不需要保证顺序）
|
|
Reduce |
当前实现为ReduceScatter + Gather
|
