当前位置: article > 正文

[机器学习] 常用并行计算算子原理_ring算法 halving-doubling算法 bruck算法 hybrid算法各自的算法原理

作者：小舞很执着 | 2024-07-13 13:00:06

踩

ring算法 halving-doubling算法 bruck算法 hybrid算法各自的算法原理以及优劣势

一、概述

在大规模机器学习中，需要应对巨大的训练数据及计算量。当单机遇到性能瓶颈时需要通过多台机器并行训练来弥补计算能力与内存的不足。采用并行方式进行机器学习时，常常分为模型并行与数据并行。模型并行是将模型拆分成多个分片，由几个计算节点分别持有，共同协作完成训练，适用于模型规模非常大的情形。数据并行是将数据拆分为不同的部分，分别存放在不同的计算节点上，同时每个计算节点都维护一个相同的模型。数据并行方式的训练过程中，每个计算节点只对自己存放的数据进行计算得到局部结果，然后再对局部结果进行全局归约。每个计算节点得到全局值之后，再进行模型更新。以下分别介绍并行计算中常用的归约算子，同时结合LightGBM的源码分析几个常用算子的实现方式。

二、并行计算中常用算子的主流实现方式剖析

在并行计算中，数值归约是非常重要且使用频率非常高的一种操作。数值归约算法实现方式的好坏直接影响整个计算过程的速度。常用的一些归约算子包括：Allreduce、Reduce、Allgather、Broadcast、ReduceScatter等。下面分别对这几种算子进行介绍。

一些定义：N---计算节点的总数； Ri --- 第i个计算节点； Vi --- 第i个计算节点的局部数值； root --- 树状网络的根节点；k --- $2^{k}$ <= N的最大整数； remain = N - $2^{k}$ ； reducer --- 归约操作；

2.1 Reduce

Reduce操作的目的是对所有计算节点上的数值进行归约操作，并将归约后的结果保存到主节点上。

Reduce 就是将多个进程中的数据按照指定的映射函数进行运算得到最后的结果存在一个进程中

例如下面两个图中的归约操作都是求和，将4个不同进程的数据归约求和后存在了第一个进程中

主流实现方式有Binomial Tree Algorithm以及Rabenseifner提出的算法[2]。

2.1.1 Binomial Tree Algorithm

采用二叉树的方式，类似于Broadcast过程的逆过程。首先需要对所有的计算节点按照二叉树建立网络连接。然后从叶子开始，将本地数据发送到父节点，父节点在接收到数据后，按照给定的归约函数执行一次归约操作，再将归约后的结果发送到其父节点，重复这一过程直到根节点。最终根节点上的值就是Reduce之后的结果。

2.2.2 Rabenseifner's Algorithm

该算法适用于数据块较大的情形，首先进行一次ReduceScatter操作，然后再进行一次Gather操作。

2.2 Allreduce

All-reduce 与reduce的区别就在于后者最后的结果是只保存在一个进程中，而All-reduce需要每个进程都有同样的结果。

所以All-reduce一般包含scatter操作，所以有时候也会看到reduce-scatter这种说法，其实reduce-scatter可以看成是all reduce的一种实现方式

Allreduce操作的目的是对所有计算节点上的数值进行归约操作，同时每一个计算节点均获得归约后的结果。

主流实现方式有Binomial Tree Algorithm以及Recursive Doubling。

Binomial Tree Algorithm

如果采用二叉树算法，可以通过2.4.1介绍的Reduce + 2.2.1介绍的Broadcast两次操作完成。如下图所示。

这种方式包括push up和pull down两个过程，push up是将本地数值进行上发，同时在接收端进行归约操作并且将得到归约后的结果继续上发。pull down是在root节点上得到了全局归约值之后的一个Broadcast过程。

Recursive Doubling

上图中描述了使用Recursive Doubling算法进行Allreduce操作的过程。具体步骤如下：

第一步：首先对N个计算节点两两分组，如R0与 $R_{0+2^{0}}$ 一组。每组之间的计算节点相互发送数据，接收方将数据存放到缓存区(step1 → step2)；

第二步：每一个计算节点，对缓存区数据与本地数据做一次归约函数操作reducer(Vi, Vrecived)(step2 → step3)；

第三步：再重新两两分组，如R0与 $R_{0+2^{1}}$ 一组。每组之间的计算节点相互发送数据，接收方将数据存放到缓存区(step3 → step4)；

第四步：依此重复执行k次之后，每个节点上的结果就是最终的归约结果；

这种方式的Allreduce要求N为2的整数倍，完成整个操作需要的的通信次数为log(N)。当N非2的整数倍时，可以采用2.6.2的方式执行一个辅助步骤再进行。

2015年NCCL开始实现AllReduce

openMPI的算法在2009年就都已经成熟并开源了，而英伟达在2015年下半年首次公开发布NCCL。

既然openmpi已经实现了这么多AllReduce算法，为什么英伟达还要开发NCCL？

从openMPI的源码里我们能看到，其完全没有考虑过深度学习的场景，基本没有考虑过GPU系统架构。很明显的一点，MPI中各个工作节点基本视为等同，并没有考虑节点间latency和带宽的不同，所以并不能充分发挥异构场景下的硬件性能。

而NCCL的优势就在于完全贴合英伟达自己的硬件，能充分发挥性能。但是基本的算法原理其实相比openmpi里实现的ring算法是没有变化的。

NCCL1.x只能在单机内部进行通信，NCCL2.0开始支持多节点（2017年Q2）。所以在NCCL2之前大家还会依赖MPI来进行集合通信。

2016年百度在深度学习中引入Ring AllReduce

openMPI代码中2007年就有ring算法了，为什么会有Baidu在2016年提出Ring Allreduce的说法？

其实在baidu的论文题目里就说得很清楚了，他们是“Bringing HPC Techniques to Deep Learning”，ring算法是早就有了，但是应用到深度学习领域确实是他们首创的。Baidu还开源了他们基于TensorFlow修改的源码，把TF里原来进行梯度规约的地方替换成了mpi实现的ring allreduce。

具体代码在tensorflow/contrib/mpi_collectives/ring.h中

可以看到实现的是常规ring，而不是segmented ring。并且里面使用MPI_Sendrecv MPI_Irecv MPI_Send这些mpi通信原语来实现，和具体mpi库无关（无论是openmpi还是MPICH2）。也没有直接用MPI_AllReduce原语，因为按照openMPI的实现它很可能跑去用其它非ring算法了。

TensorFlow里的AllReduce

在tf早期版本中，分布式训练只有PS架构。

在2017年后，开始逐步支持多种allreduce算法，其中的ring-allreduce实现正是baidu贡献的。

NCCL2.0之后，TensorFlow/Baidu里的allreduce算法集成了NCCL来做GPU间通信，而不是依赖MPI了。

MPI和NCCL的关系

是不是从此我们只要NCCL，不再需要MPI了呢？NO

Nvidia的策略还是比较聪明，不和MPI竞争，只结合硬件做MPI没做好的通信性能优化。在多机多卡分布式训练中，MPI还是广泛用来做节点管理。当红炸子鸡Horovod也是这么做的，NCCL只做实际的规约通信。

2.3 Gather

Gather 就是把多个进程的数据拼凑在一起

Gather操作的目的是将所有计算节点上的数据集合到主节点上。也可以采用Binomial Tree Algorithm算法。各个计算节点的网络连接如上图。

第一步：从叶子节点开始，将本地数据发送到其父节点；

第二步：第一步中的父节点接收到数据后，继续将本地数据以及接收到的数据往上发，最终根节点上的数据就是所有节点数据Gather之后的结果了；

Binomial Tree Algorithm的实现方式通信次数为log(N)。

2.4 Allgather

Allgather操作的目的是将计算节点的本地数据Vi同步到其他所有的计算节点，使得每一个节点都拥有一份 $v_{0}$ - $v_{N-1}$ 的值。

主流的实现方式有Recursive Doubling、Bruck Algorithm。

Recursive Doubling

上图描述了Recursive Doubling算法的工作过程。

第一步：在每一个节点上开辟sizeof(V0) + sizeof(V1) + sizeof(V2) + sizeof(V3)的内存，并且将本地的数据拷备到对应的起始位置；

第二步：如图所示，step-1时，节点与其相距20的节点进行数据互发；

第三步：step-2时，节点与其相距21的节点进行数据互发，发送的数据包括节点自身的数据以及之前接收的数据；

依此方式执行k步，最终所有的计算节点都拥有一份全局的数据了。

Recursive Doubling方式要求N为2的整数倍，计算节点收集到所有数据的通信次数为log(N)。

Bruck Algorithm

上图描述了Bruck Algorithm算法的工作过程。

第一步：如图，R1将数据发给R0, R2将数据发给R1,......., R0将数据发给R4，发送一个数据块；

第二步：重复k步，第k步时，Ri将数据发送给 $R_{i-2^{k}}$ ，发送个数据块min( $2^{k}$ , N-sum_block)；sum_block为计算节点上已有数据块大小。

第三步：调整数据块的顺序，调整方法在4.1节代码中介绍；

以上这种方式不要求N一定为2的整数倍，计算节点收集到所有数据的通信次数为ceil(log(N))。

2.5 Broadcast

Broadcast 看名字就很好理解了，其实就是把同一份数据分发广播给所有人，目的是将主节点的数值广播到其他所有的计算节点。

主流的实现方式有Binomial Tree Algorithm、Geijin Algorithm。

Binomial Tree Algorithm

上图描述了Binomial Tree Algorithm算法的工作过程，一般需要做broadcast操作时都有一个主节点设为R0。各个计算节点的网络连接如上图。

第一步：R0将本地值发送给左右孩子节点R1和R2，同时将R1和R2设置为root，再往它们的左右孩子节点发送；

第二步：第i步，Ri将本地值发送给 $R_{2*i+1}$ 和 $R_{2*i+2}$ ，同时将 $R_{2*i+1}$ 和 $R_{2*i+2}$ 设为root，再重复这一过程，直到该节点没有孩子节点；

Binomial Tree Algorithm这种广播方式，每一次发送的数据块为整个数据块的大小，在数据块较小时比较适用。但当数据块较大时，以下介绍的Geijin Algorithm会更加适用。

Geijin Algorithm

Geijin Algorithm适用于大的数据块。主要思想是：

第一步：将需要Broadcast的数据分成N块，同时Scatter到各个计算节点上；

第二步：对各个计算节点分发到的子数据块执行Allgather，即可完成操作；

Geijin Algorithm相比于Binomial Tree Algorithm增加了通信次数，但是每次收发的数据块小了，对于大数据块更能降低带宽消耗。

2.6 ReduceScatter

Scatter 不同于Broadcast， scatter可以将不同数据分发给不同的进程。

ReduceScatter操作的目的也是对所有计算节点上的数值进行归约操作，但是各个节点只保留归约后的部分结果。以下介绍Recursive Halving的实现方式。

当workers数量为2的k次方时，以下以8个workers为例进行介绍：

最初，每一个worker都将数据分成8个数据块，每个数据块用Fi表示。本例中ReduceScatter的目的是使R0得到reducer(0_F0, ...., 7_F0)的结果、R1得到reducer(0_F1, ...., 7_F1)....。

上图中描述了使用Recursive Halving算法进行ReduceScatter操作的过程。以R0为例具体步骤如下：

第一步：先计算每一个节点需要获得数据块哪一部分的归约结果，并将数据块切分成N个子块；

第二步：第一次通信，R0将4-7子块发送给R4，并接收R4发送过来的0-3子块，然后在本地对自身的数据以及接收到的数据进行归约操作；

第三步：第二次通信，R0将2-3子块发送给R2，并接收R2发送过来的0-1子块，然后在本地对自身的数据以及接收到的数据进行归约操作；

第四步：依次执行，最终每个节点在对应的位置都得到了分配给其的结果，如图中红色位置；

这种方式的ReduceScatter要求N为2的整数倍，完成整个操作需要的的通信次数为log(N)

当workers数量非2的k次方时，可以采用以下方法：

第一步：小于2*remain的节点中，Ri为偶数的节点，将它需要做ReduceScatter的所有数据发送给Ri+1；

第二步：设置一个virtual_rank(VR)。VR的计算：第一步中偶数计算节点设置为-1，奇数的设置为0开始依次递增。大于2*remain的计算节点VR=R-remain。详细做法见4.2代码；

第三步：virtual_rank非-1的节点按照2.6.1的Recursive Halving方法进行操作即可；

这种方法相比于2的k次方时多了第一步的所有数据的发送步骤。

三、总结

本文主要是通过对MPI中主流归约算子的理解，进行归纳并且通过实例化的形式进行总结。一般并行计算中的归约算子很多，并且每个算子都有多种实现方式，各种不同的实现适用于不同的场景，有些在小数据块时效率高，有些在大数据块时更有优势，如何进行选择需要根据业务场景甚至通过实验对比来确定。

参考

Generalisation of Recursive Doubling for AllReduce
Optimization of Collective Communication Operations in MPICH
https://github.com/Microsoft/LightGBM
https://www.zhihu.com/question/37057945
https://zhuanlan.zhihu.com/p/100012827
AllReduce算法的前世今生

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/819600

[机器学习] 常用并行计算算子原理_ring算法 halving-doubling算法 bruck算法 hybrid算法 各自的算法原理