RHD【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl算法描述当组网增大时例如增大至4K个rank的场景Mesh很难组成4K个rank的全连接网络全连接一个时钟周期就可以完成操作且资源开销链路资源交换资源同步资源太大还可能存在算力和资源开销不匹配的问题。Ring在这种情况下虽然节省资源只用左手卡和右手卡进行一次收发但是环内要做太多次流转太慢。大型规模集群运算有服务器内数据量庞大、Ring环极长的特点Ring的这种切分数据块的方式就不再占优势。RHDRecursive Halving-Doubling算法通过递归加倍及递归折半方式完成NPU间的数据交换相对Mesh资源消耗较小相对Ring效率会更高。RHD算法的实现流程如上图所示假设有5221个rank首先将rank1的数据合并到rank0变成422个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的整数次幂划分为2rpart1和p-2r两部分$rp-2^{\lfloor log(p) \rfloor} $先将part1部分合并为r使得剩余的rank之和为p-rblock再执行2的整数次幂的HDHalving-Doubling算法最后再在part1部分恢复出2r得到最终结果。表 1Recursive Halving-Doubling算法中各操作计算耗时操作耗时Broadcast根据root rank的奇偶决定part1部分参与block的为奇数rank还是偶数rank在block内先执行Distance Halving再向剩余rank发送一次总耗时为$\lceil log(p) \rceil(\alphan\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 $\alphan\betan\gamma$第二步非均匀分片的ReduceScatter某些rank持有2份数据需要做$k\lfloor log(p) \rfloor$次通信每次交换的最大数据量为$n_i\lceil \frac{p}{2^{k-i1}} \rceil\frac{n}{p}\quad i1,2,...k$总耗时为$\sum_{i1}^{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_{i1}^{k}\lceil \frac{p}{2^i} \rceil\frac{n\gamma}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil$该步计算比较复杂这里尝试给出下限和上限:下限$k\alpha(k2^k-1)\frac{n\beta}{p}(k2^k-1)\frac{n\gamma}{p}$上限$k\alpha(2^{k1}-2)\frac{n\beta}{p}(2^{k1}-2)\frac{n\gamma}{p}$第三步Scatter: $\alpha\frac{1}{p}n\beta$AllGather耗时同ReduceScatter无$\gamma$相关部分。AllreduceReduceScatter AllGather这里的拆分是不完全的ReduceScatter和AllGather不需要scatter到所有rank并且可以采用Vector Halving Distance Doubling分层网络下耗时会小但是无法保证顺序拆分中也不需要保证顺序。2的整数次幂:$2log(p)\alpha2\frac{p-1}{p}n\beta\frac{p-1}{p}n\gamma$非2的整数次幂:第一步Reduce: $\alphan\betan\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^\prime2^{\lfloor log(p) \rfloor}$AllGather: $\lfloor log(p) \rfloor\alpha\frac{p^\prime-1}{p^\prime}n\beta,\quad p^\prime2^{\lfloor log(p) \rfloor}$最后一步: $\alphan\beta$总耗时$(2\lfloor log(p) \rfloor2)\alpha(2\frac{p^\prime-1}{p^\prime}2)n\beta(\frac{p^\prime-1}{p^\prime}1)n\gamma,\quad p^\prime2^{\lfloor log(p) \rfloor}$Reduce当前实现为ReduceScatter Gather。2的整数次幂: $2log(p)\alpha2\frac{p-1}{p}n\beta\frac{p-1}{p}n\gamma$非2的整数次幂:第一步Reduce: $\alphan\betan\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^\prime2^{\lfloor log(p) \rfloor}$Gather: $\lfloor log(p) \rfloor\alpha\frac{p^\prime-1}{p^\prime}n\beta,\quad p^\prime2^{\lfloor log(p) \rfloor}$总耗时$(2\lfloor log(p) \rfloor1)\alpha(2\frac{p^\prime-1}{p^\prime}1)n\beta(\frac{p^\prime-1}{p^\prime}1)n\gamma,\quad p^\prime2^{\lfloor log(p) \rfloor}$【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
CANN/HCCL的RHD通信算法
RHD【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl算法描述当组网增大时例如增大至4K个rank的场景Mesh很难组成4K个rank的全连接网络全连接一个时钟周期就可以完成操作且资源开销链路资源交换资源同步资源太大还可能存在算力和资源开销不匹配的问题。Ring在这种情况下虽然节省资源只用左手卡和右手卡进行一次收发但是环内要做太多次流转太慢。大型规模集群运算有服务器内数据量庞大、Ring环极长的特点Ring的这种切分数据块的方式就不再占优势。RHDRecursive Halving-Doubling算法通过递归加倍及递归折半方式完成NPU间的数据交换相对Mesh资源消耗较小相对Ring效率会更高。RHD算法的实现流程如上图所示假设有5221个rank首先将rank1的数据合并到rank0变成422个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的整数次幂划分为2rpart1和p-2r两部分$rp-2^{\lfloor log(p) \rfloor} $先将part1部分合并为r使得剩余的rank之和为p-rblock再执行2的整数次幂的HDHalving-Doubling算法最后再在part1部分恢复出2r得到最终结果。表 1Recursive Halving-Doubling算法中各操作计算耗时操作耗时Broadcast根据root rank的奇偶决定part1部分参与block的为奇数rank还是偶数rank在block内先执行Distance Halving再向剩余rank发送一次总耗时为$\lceil log(p) \rceil(\alphan\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 $\alphan\betan\gamma$第二步非均匀分片的ReduceScatter某些rank持有2份数据需要做$k\lfloor log(p) \rfloor$次通信每次交换的最大数据量为$n_i\lceil \frac{p}{2^{k-i1}} \rceil\frac{n}{p}\quad i1,2,...k$总耗时为$\sum_{i1}^{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_{i1}^{k}\lceil \frac{p}{2^i} \rceil\frac{n\gamma}{p}\sum_{i1}^{k}\lceil \frac{p}{2^i} \rceil$该步计算比较复杂这里尝试给出下限和上限:下限$k\alpha(k2^k-1)\frac{n\beta}{p}(k2^k-1)\frac{n\gamma}{p}$上限$k\alpha(2^{k1}-2)\frac{n\beta}{p}(2^{k1}-2)\frac{n\gamma}{p}$第三步Scatter: $\alpha\frac{1}{p}n\beta$AllGather耗时同ReduceScatter无$\gamma$相关部分。AllreduceReduceScatter AllGather这里的拆分是不完全的ReduceScatter和AllGather不需要scatter到所有rank并且可以采用Vector Halving Distance Doubling分层网络下耗时会小但是无法保证顺序拆分中也不需要保证顺序。2的整数次幂:$2log(p)\alpha2\frac{p-1}{p}n\beta\frac{p-1}{p}n\gamma$非2的整数次幂:第一步Reduce: $\alphan\betan\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^\prime2^{\lfloor log(p) \rfloor}$AllGather: $\lfloor log(p) \rfloor\alpha\frac{p^\prime-1}{p^\prime}n\beta,\quad p^\prime2^{\lfloor log(p) \rfloor}$最后一步: $\alphan\beta$总耗时$(2\lfloor log(p) \rfloor2)\alpha(2\frac{p^\prime-1}{p^\prime}2)n\beta(\frac{p^\prime-1}{p^\prime}1)n\gamma,\quad p^\prime2^{\lfloor log(p) \rfloor}$Reduce当前实现为ReduceScatter Gather。2的整数次幂: $2log(p)\alpha2\frac{p-1}{p}n\beta\frac{p-1}{p}n\gamma$非2的整数次幂:第一步Reduce: $\alphan\betan\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^\prime2^{\lfloor log(p) \rfloor}$Gather: $\lfloor log(p) \rfloor\alpha\frac{p^\prime-1}{p^\prime}n\beta,\quad p^\prime2^{\lfloor log(p) \rfloor}$总耗时$(2\lfloor log(p) \rfloor1)\alpha(2\frac{p^\prime-1}{p^\prime}1)n\beta(\frac{p^\prime-1}{p^\prime}1)n\gamma,\quad p^\prime2^{\lfloor log(p) \rfloor}$【免费下载链接】hccl集合通信库Huawei Collective Communication Library简称HCCL是基于昇腾AI处理器的高性能集合通信库为计算集群提供高性能、高可靠的通信方案项目地址: https://gitcode.com/cann/hccl创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
