Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3595802
  • 博文数量: 208
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7375
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-23 18:56
个人简介

将晦涩难懂的技术讲的通俗易懂

文章分类

全部博文(208)

文章存档

2024年(10)

2023年(9)

2022年(4)

2021年(12)

2020年(8)

2019年(18)

2018年(19)

2017年(9)

2016年(26)

2015年(18)

2014年(54)

2013年(20)

分类: 高性能计算

2024-09-22 20:37:10

AllReduce 算法

AllReduce 有不同的实现算法,比如基于 Ring AllReduce 和基于 Tree AllReduce。它们之间有各自不同的场景和优劣。

Ring AllReduce:是一种环形拓扑结构的 AllReduce 算法,假设有 N 个节点参与

l  通信过程:

1.       Reduce-Scatter 阶段

2.       AllGather 阶段

优点:带宽利用率高,因为在每个通信步骤中,所有节点都在同时发送和接收数据。

缺点:延迟较高,尤其是当节点数量较多时,由于需要进行 2*(N-1) 次通信。

Tree AllReduce:采用树状拓扑结构进行通信

l  通信过程

1.       Reduce阶段:从叶子节点开始向根节点汇聚数据,根节点{BANNED}{BANNED}最佳佳终得到完整的结果。

2.       Broadcast 阶段:根节点将汇总的结果沿树结构向下广播给所有节点。

优点:通信步骤少,通常为 2*log(N),因此在大规模节点时延迟较低。

缺点:在每一步中,只有部分节点参与通信,带宽利用率相对较低。

总体来说:

Ring AllReduce 更适合在高带宽、低延迟的网络环境下使用,特别是当节点数量较小时,它能更好地利用带宽资源。

Tree AllReduce 更适合在节点数量较多或网络延迟较高的情况下使用,因为它的通信延迟随节点数量增长的速度较慢。

下面就逐个具体分析这两个算法和实现。

Ring AllReduce

AllReduce 是集合通信中常见的分布式计算操作,主要用于需要在多个设备(如多台服务器或多个 GPU)之间聚合数据的场景,可以包含 SumMinMax 等操作。以 AllReduceSum 为例,假设有 K 个 设备,每个设备上有 N 个数据,则 AllReduce 后每个设备上的 out[i] = in0[i] + in1 [i] + … + in(k-1)[i]。如下图所示:

其实等效与一个Reduce + Broadcast。但为了更多的利用当前GPU和多轨道网络的环形(ring)拓扑,一个基于 Ring AllReduce 操作更多拆解为一个 ReduceScatter 一个 AllGather 操作,如下图所示:

我们先来回顾一下ReduceScatter操作:每个节点先做Scatter,再做ReduceScatter操作表示一种散播行为,将主节点的数据进行划分并散布至其他指定的节点。

Reduce,从多个sender那里接收数据,{BANNED}最佳终combine到一个节点上。

Reduce Scatter操作会将个进程的输入先进行求和,然后在第0维度按卡数切分,将数据分发到对应的卡上。

然后我们看下具体基于RingReduceScatter 操作如下,每个节点发送一部分数据给下一个节点,同时接收上一个节点的数据并累加,这个过程进行 N-1 步。ReduceScatter 后每个设备都包含一部分数据的 Sum

具体的 AllGather 操作如下,每个节点将其持有的部分结果发送给下一个节点,同时接收上一个节点的部分结果,逐步汇集完整的结果。AllGather 后,每个设备都包含全量的数据:

 

AllReduce 带宽

如上所示,AllReduce 操作可以分成 ReduceScatter AllGather 操作,假设 GPU 数量为 K,则每一个阶段的通信量为 (K-1) * T * sizeof(dtype),假设每个 GPU 的总线带宽为 busBW,则 AllReduce 对应的理论通信时延为:

然而,实际的总线带宽并不能达到理论总线带宽,如下图所示,4*V100 通过 NVLink 互联(没有 NVSwitch),每两个 GPU 之间两个 NVLink 连接,理论双向带宽为 100GB/s,实际测试也可以达到 97GB/s,如果 Disable NVLink,则对应的带宽只有 16GB/s

AllReduce 通常更关注的是总线带宽 busBW,对于 4*V100 NVLink 互联(没有 NVSwitch),NCCL 通过如下的方式可以创建 3 个双向环,其中每个颜色都是 1 个双向环。因为每个环的单向通信带宽为 4*25GB/s,通信带宽的理论上限为 6*(4*25GB/s)=600GB/s(也可以用 12 NVLink * 50GB/s 得到),那么平均每个 GPU busBW 150GB/s

然而,实际总线带宽也与理论总线带宽有一定差距,这和数据量GPU 连接方式、使用的通信算法、NCCL 版本等有关。如下图所示为使用 NCCL 测试出的 AllReduce 总线带宽,可以看出,当数据量比较小时,比如小于 1MB(106B),测试的 busBW 很低,不到 30GB/s。当通信的数据量达到 128MB ,相应的 busBW 达到 130GB/s,基本接近极限的 150GB/s。如果没有 NVLink,则实测的 busBW 只有 10GB/s 左右。

Halving-Doubling

另一种常见的AllReduce实现算法是Halving-Doubling阿里巴巴的通信库ACCL采用了这种算法,该算法每次选择节点距离倍增的节点相互通信,每次通信量倍减(或倍增),过程图示如下:

该算法的优点是通信步骤较少,只有 2*log2次(其中N表示参与通信的节点数)通信即可完成,所以其有更低的延迟。相比之下Ring算法的通信步骤是 2*(N-1) 次;缺点是每一个步骤相互通信的节点均不相同,链接来回切换会带来额外开销。

 

double binary tree

上节我们以ring allreduce为例看到了集合通信的过程,但是随着训练任务中使用的个数的扩展,ring allreduce的延迟会线性增长,为了解决这个问题,NCCL引入了tree算法,即double binary tree

朴素的tree算法将所有机器节点构造成一棵二叉树,支持broadcastreduce,前缀和。假设root节点要broadcast一个消息M给所有节点,root会将M发送给他的子节点,其他所有的节点收到消息M后再发送给子节点,叶节点因为没有子节点,所以叶结点只会接收M。这个过程可以将M切分为kblock,从而可以流水线起来。

但这个朴素算法有一个问题,叶节点只接收数据,不发送,因此只利用了带宽的一半,为了解决这个问题,MPI提出了double binary tree算法,假设一共有N个节点,MPI会构建两个大小为N的树T1T2T1的中间节点在T2中是叶节点,T1T2同时运行,各自负责消息M的一半,这样每个节点的双向带宽可以都被利用到。以十台机器为例,构建出的结构如下:

T2的构造有两种方式,一种是shift,将rank向左shift一位,比如rank10变成rank9,然后通过和T1一样的方式构造,这种构造方式下T1T2的树结构完全一致;另外一种是mirror,将rank号镜像一下,比如rank0镜像为rank9,这种构造方式下T1T2树结构是镜像对称的,不过mirror的方式只能用于机器数为偶数的场景,否则会存在节点在两棵树中都是叶节点。

如上图,T1T2的边可以被染成红色或者黑色,从而有如下很好的性质:

l  不会有节点在T1T2中连到父节点的边的颜色相同,比如node AT1中通过红色的边连到父节点,那T2A一定通过黑色的边连到父节点。

l  不会有节点连到子节点的边颜色相同,比如node AT1中是中间节点,如果A通过红色的边连到左子节点,那么A一定通过黑色的边连到右子节点

根据上述性质,就有了两棵树的工作流程,在每一步中从父节点中收数据,并将上一步中收到的数据发送给他的一个子节点,比如在偶数步骤中使用红色边,奇数步骤中使用黑色边,这样的话在一个步骤中可以同时收发,从而利用了双向带宽。

nccl中的tree只用于节点之间,节点内是一条链,2.7.8版本使用的patternNCCL_TOPO_PATTERN_SPLIT_TREE,假设为432卡,对于T2后边再介绍,T1如下所示:

由于allreduce可以拆分为reducebroadcast两个过程,所以nccl tree allreduce先执行reduce,数据按照图中箭头方向流动,称为上行阶段,从rank15rank31rank23rank7开始一直reducerank 0rank0拿到全局reduce的结果之后再按照箭头反方向开始流动,称为下行阶段,broadcast到所有卡。

SHARP

之前我们看到了基于ringtree的两种allreduce算法,对于ring allreduce,一块数据在reduce scatter阶段需要经过所有的rankallgather阶段又需要经过所有rank;对于tree allreduce,一块数据数据在reduce阶段要上行直到根节点,在broadcast阶段再下行回来,整个流程比较长。

IB SHARP

因此基于这一点,mellanox提出了SHARP,将计算offload到了IB switch,每个节点只需要发送一次数据,这块数据会被完成规约,然后每个节点再接收一次就得到了完整结果。下图展示了一个胖树物理网络拓扑,其中绿色节点为交换机,黄色节点的为host

下图展示了基于上图的物理网络拓扑,这些host节点执行SHARP初始化后得到的SHARP treeSHARP tree是个逻辑概念,并不要求物理拓扑一定是胖树。

值得注意的是:

l  其中一个交换机可以位于{BANNED}最佳多64SHARP tree中,

l  一个SHARP tree可以建立大量的groupgroup指的是基于现有的host创建的一个子集

l  支持数百个集合通信api的并发执行

NVLink SHARP

进一步的,Hopper架构机器中引入了第三代NVSwitch,就像机间IB SHARP一样,机内可以通过NVSwitch执行NVLink SHARP,简称nvls

阅读(459) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~