CANN/hccl AHC非对称层次化拼接算法

AHC

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

算法描述

当集群网络存在层次化特征且层次间存在带宽收敛时，集合通信面临两大技术挑战：一是由于不同区域间存在带宽收敛问题，传统的单层集合通信算法性能下降；二是不同区域的计算单元数量不同（即卡数非对称），这使得常规的层次化算法不再适用。例如，在一个集群中，同一通信域可能横跨两个超节点，且两个超节点中的卡数量不一致（比如一个超节点中有64 张卡，另一个则有128张卡），这种情况对集合通信算法的性能带来巨大挑战。

图 1AHC基于逻辑同号卡实现AllReduce过程 （5个rank， 2+3两个分组） ![](https://raw.gitcode.com/cann/hccl/raw/20ed5a0bc0d136005da3f0581544829bd02123b8/docs/user_guide/coll_algo_intro/figures/ahc_allreduce_5rank_flow.png "AHC基于逻辑同号卡实现AllReduce过程-（5个rank-2+3两个分组）"?utm_source=gitcode_repo_files)

本算法的核心思想是基于拓扑将通信域内NPU及各NPU上的数据重新分组，组内充分利用高速网络带宽，组间实现基于“逻辑同号卡”的非对称拼接。具体流程参考上图，实现分为如下三个步骤：

1. 基于物理拓扑对计算单元分组。临近的NPU划分为一个group，各group内卡数无需一致，group间带宽相比group内可能存在收敛。

   1. 求解所有分组数的最小公倍数LCM，若G个分组则将数据划分为LCM*G个切片。如上图所示，分组为2和3、则LCM=6、G=2，将数据切分成12份切片。
   2. 每个分组内并行执行标准的ReduceScatter。

2. 划分“逻辑同号卡”，基于逻辑同号卡实现组间allreduce。

   1. 将每个group中待执行reduce操作的数据，按照group内各NPU卡间的数据边界进行切分，形成若干不均匀的数据块。
   2. 每个group中的每份数据，在其他所有group中各有一份对应的、大小相同的数据。按照数据对应关系，group间的NPU也存在对应关系。我们称存在对应关系的NPU为“逻辑同号卡”。
   3. 在逻辑同号卡间执行AllReduce操作。

3. 各group内的NPU之间执行AllGather操作。

具体的组内和组间的ReduceScatter、AllGather 、AllReduce等操作，其实现算法可以是任意已知的算法，如NB、NHR 、Ring等，当前AHC算法内部根据具体场景和策略选择性能更优的拼接算法类型。

耗时计算

当组内和组间都采用NB算法时，AllReduce算子的算法耗时如下：

表 1AHC算法耗时

操作	耗时
ReduceScatter	$2(\lceil log(m+d)\rceil + \lceil log(G)\rceil)\alpha + 2(\frac{m+d−1}{m+d}+ \frac{(G-1)*C}{Gm}n\beta + (\frac{m+d-1}{m+d} + \frac{G-1}{Gm})n\gamma$ 其中m为最小分组数、m+d为最大分组数、G为分组数、C为组间带宽相对于组内带宽的收敛比。

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