0 概述

近年来，深度学习技术已在语音识别^[1-2]、计算机视觉^[3-4]和自然语言处理^[5]等领域得到广泛应用并取得了众多研究成果。在深度学习任务中常使用梯度下降（Gradient Descent，GD）算法作为深度神经网络（Deep Neural Network，DNN）模型训练的主要算法^[6-7]，然而由于数据量的爆炸式增长，现有单机系统已无法满足梯度下降算法对计算资源的庞大需求。分布式技术通过多机协同计算的方式，使用多个计算节点扩充计算性能，可提供梯度下降算法所需的大量计算资源，因此研究梯度下降算法在分布式集群上的并行化计算非常必要^[8]。

目前，深度神经网络分布式训练中通常使用数据并行化方法，基于数据并行化的梯度下降算法包括同步随机梯度下降^[9]（Synchronized Stochastic Gradient Descent，SSGD）和异步随机梯度下降^[10]（Asynchronized Stochastic Gradient Descent，ASGD）两种算法。同步算法在每次迭代过程中通过同步各个节点的状态来保持状态一致，因此同步梯度下降能够保持和单机串行算法相同的收敛方向，从而导致其所需的通信量相对其他算法更多，容易受分布式集群中的通信瓶颈影响，同时计算节点之间需要相互等待传输梯度更新结果，从而造成了计算资源的浪费。异步算法则无需等待节点状态一致，每个节点在更新权值参数时不会检查其他节点的运行状态，独立地更新本地模型到全局模型上，并获取全局模型参数继续执行下一步计算，如果在该计算过程中又有其他节点更新了全局模型，那么该节点用于执行下一步计算的全局模型参数就不是最新的，该数据交互模式将导致梯度延迟问题^[11-12]，而梯度延迟问题又会导致每个节点用于执行下一步计算的全局模型不一致。在大规模分布式集群中，随着分布式集群中的节点数目增加，节点计算状态保持一致的概率越来越小，节点之间所需传输的信息量逐渐增多，因此无论同步或异步算法，都在大规模分布式集群中存在亟待解决的效率问题。本文提出基于分布式编码的同步随机梯度下降算法CSSGD，通过分布式编码策略^[13-14]降低分布式集群上的通信负载。

1 相关工作

近年来，分布式并行梯度下降算法得到了广泛应用，研究人员针对分布式神经网络训练开展了大量研究工作，这些工作主要围绕分布式异构计算和通信负载两方面展开。分布式集群是典型的异构计算平台，在该异构计算环境下，每个执行进程的执行速度和任务完成时间均不确定，在同步梯度下降算法中由于系统需要同步每一批次中各个计算节点的状态，因此最慢节点的速度成为限制分布式集群整体任务运行速度的主要因素。文献[15-16]通过对每个节点的计算和更新过程进行限时，使每个节点都在已有样本上进行逐样本迭代计算，以保证每个节点都能在任意时间内给出一个可用但不完整的中间梯度运算结果，降低了节点异构对整体任务的影响。文献[17-18]针对大矩阵乘法的并行化问题，提出纠缠多项式码，使用纠缠多项式码对矩阵乘法运算进行拆解，并对原始矩阵计算任务添加一定量的冗余以加快运算速度。

此外，并行梯度下降算法还需在各个计算节点之间进行密集地数据交换，因此分布式集群的通信性能也是影响分布式神经网络训练性能的主要问题。文献[19]提出1-Bit数值量化方案，使用Adagrad算法进行学习率迭代并结合误差累积回溯，在深度神经网络中得到一种低通信负载的分布式神经网络训练方案。文献[20]提出批次内并行化方法，使用较小的Block划分和基于动量的参数迭代方案提高了分布式神经网络的训练速度。文献[21]提出改进的并行梯度下降算法，在改进算法中每个节点不再将本地计算结果推送给分布式集群中的所有节点，而是随机选取一部分节点进行更新以降低通信负载。文献[22]结合MDS编码和分布式通信编码对分布式机器学习中的大矩阵乘法进行优化，有效解决了分布式系统慢节点和通信瓶颈问题，但其在编码过程中的冗余量较大。

上述文献分别从不同角度对分布式神经网络的训练过程进行分析与改进，然而在针对分布式通信瓶颈和分布式计算异构方面，使用量化或随机策略不可避免地会影响网络训练精确度，而利用MDS码则会引入更多的通信冗余。本文设计一种用于同步梯度下降算法的分布式编码策略，能够降低分布式集群上的通信负载，并保证分布式神经网络的训练精确度。

2 本文同步随机梯度下降算法

梯度下降算法是用于求解目标函数最小值的常用优化算法，当网络模型参数为$ w $、数据集为$ x\mathrm{和}y $、目标方程为$ F(w;x, y) $时，计算公式如式（1）所示，迭代过程的计算公式如式（2）所示，其中，$ \nabla F\left(w;x, y\right) $为目标函数的一阶导数，$ \eta $为迭代步长，又称为学习率，$ t $为迭代轮次。在分布式环境下，并行梯度下降算法在每个节点$ i $上求其部分样本的梯度，计算公式如式（3）所示，最终汇总至全局模型参数$ w\left(t\right) $上的计算公式如式（4）所示。

$ \underset{w}{\mathrm{m}\mathrm{i}\mathrm{n}}F\left(w;x, y\right) $

(1)

$ w\left(t\right)=w\left(t-1\right)-\eta \cdot \nabla F\left(w\left(t-1\right);x, y\right) $

(2)

$ ∆{w}_{i}\left(t\right)=\nabla F\left({w}_{i}\left(t-1\right);{x}_{i}, {y}_{i}\right) $

(3)

$ w\left(t\right)=w\left(t-1\right)-\eta \cdot \frac{1}{\left|x\right|}\sum\limits_{i}∆{w}_{i}\left(t\right) $

(4)

本文算法是同步梯度下降算法的一种改进形式，算法执行步骤为：1）将目标样本集合以预设批次大小进行划分，在添加冗余后将其平均分配到各个节点上；2）每个节点都在已有样本上执行反向传播算法，并对中间梯度结果进行编码，同时将中间梯度结果进行整合，实现数据分组交换；3）每个节点根据接收到的中间结果数据，解码出该节点所需的内容，继续执行训练过程。本文算法在任务分配时使用冗余分发策略，因此每个节点所需的中间结果数据可以从r个包含该数据的节点处获取，因此每个节点可以仅发送必要数据的1/r，由接收节点自行拼装完整结果，如图 1所示。同时，由于多个节点间存在冗余数据，因此一份数据可以被多个节点所共有，使用编码策略将需要发送的多个数据分片累加，将中间结果数据多播给多个节点，每个节点接收到累加结果后减去已知部分，即可得到所需部分的结果，如图 2所示。本文结合上述两种策略并将其扩展至梯度矩阵信息交换过程中，提出能够有效降低梯度下降算法通信负载的方案。

本文同步随机梯度下降算法的伪代码如算法1所示，具体过程为在给定的训练数据集$ F $和迭代次数$ T $的情况下获取当前最终模型参数$ {w}^{f} $。

算法1  本文同步随机梯度下降算法

输入  dataset $ F $，iteration $ T $

输出  final model parameter $ {w}^{f} $

1.initialize all $ {\mathrm{w}}^{\mathrm{f}} $ and $ {\mathrm{w}}_{\mathrm{i}}\left(0\right) $ to the same value for all $ \mathrm{i} $；

2.each node $ \mathrm{i} $ gets the dataset $ {\mathrm{D}}_{\mathrm{i}} $ using algorithm 2；

3.for $ \mathrm{t}=\mathrm{1, 2}, \dots , \mathrm{T} $ do

4.for each node $ \mathrm{i} $ in parallel，compute local update $ ∆{\mathrm{w}}_{\mathrm{i}}\left(\mathrm{t}\right) $ using step 3；

5.for each node，encode and push $ ∆{\mathrm{w}}_{\mathrm{i}}\left(\mathrm{t}\right) $ using algorithm 3；

6.for each node，receive and decode $ ∆\mathrm{w}\left(\mathrm{t}\right) $ using algorithm 4；

7. set $ {\mathrm{w}}_{\mathrm{i}}\left(\mathrm{t}\right)\leftarrow \mathrm{w}\left(\mathrm{t}\right) $ for all $ \mathrm{i} $，where $ \mathrm{w}\left(\mathrm{t}\right) $ is defined in step 4；//全局结果合并

8.update $ {\mathrm{w}}^{\mathrm{f}}\leftarrow \underset{\mathrm{w}\in \left\{{\mathrm{w}}^{\mathrm{f}}, \mathrm{w}\left(\mathrm{t}\right)\right\}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{F}\left(\mathrm{w}\right) $；

9.end for

10.return $ {\mathrm{w}}^{\mathrm{f}} $；

2.1 任务分配过程

本文设计一种任务分配算法，在有n个计算节点的集群上，将训练数据集F冗余r倍并平均分配到每个节点上，且每个节点上的样本组合不重复。上述分配过程可以描述为一个简单的排列组合过程，首先要实现$ r $倍冗余的分配，且每个节点上的数据组合互不重复，需要将每个样本的$ r $份拷贝发送到任意$ r $个不重复的计算节点上。其次要实现每个节点上的样本数量一致，将要分配的样本集合划分为$ {C}_{n}^{r} $份，每一份样本子集都可以对应一个唯一的分发路径，依照组合结果进行分发，每个节点可以接收到（$ r\cdot {C}_{n}^{r}/n $）个样本集合，完成任务的平均分配。任务分配算法的伪代码如算法2所示，具体过程为在给定训练数据集F、分布式节点集合$ U $和训练所用的批次大小b的情况下获取每个计算节点$ i $的本地样本$ {D}_{i} $，其中，$ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\left(U, r\right) $返回$ U $的$ r $倍所有可能的组合结果，$ \mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}\_\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\_\mathrm{b}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\left(F, b\right) $返回按照批次大小划分后的数据集，$ \mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}\left({F}_{j}, C.\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\right) $返回$ {F}_{j} $平均分为$ C.\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e} $后的结果集合。

算法2   任务分配算法

输入   dataset $ F $，node set $ U $，batch size $ b $

输出   data assignment $ D $ for each node $ i $

1.$ \mathrm{C}\leftarrow \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\left(\mathrm{U}, \mathrm{r}\right) $；//获取组合结果

2.$ \mathrm{F}\leftarrow \mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}\_\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\_\mathrm{b}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\left(\mathrm{F}, \mathrm{b}\right) $；//获取样本mini batch

3.$ \mathrm{D}\leftarrow \left\{{\mathrm{D}}_{\mathrm{i}}\right|{\mathrm{D}}_{\mathrm{i}}=\mathrm{\varnothing }\} $；//为每个节点初始化私有样本集合

4.for each $ {\mathrm{F}}_{\mathrm{j}} $ in $ \mathrm{F} $ do

5.$ \mathrm{P}\leftarrow \mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}\left({\mathrm{F}}_{\mathrm{j}}, \mathrm{C}.\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\right) $；//将$ {\mathrm{F}}_{\mathrm{j}} $均分为$ {\mathrm{C}}_{\mathrm{n}}^{\mathrm{r}} $份

6.for $ \mathrm{i}=\mathrm{1, 2}, \dots , \mathrm{C}.\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e} $ do

7.for each $ {\mathrm{N}}_{\mathrm{i}} $ in $ {\mathrm{C}}_{\mathrm{i}} $ do

8.$ {\mathrm{D}}_{\mathrm{i}}.\mathrm{a}\mathrm{d}\mathrm{d}\left({\mathrm{P}}_{\mathrm{i}}\right) $；

9.end for

10.end for

11.end for

12.return $ \mathrm{D} $；

为阐述算法2的执行过程，首先定义分布式集群中所有节点的集合为$ U $，如式（5）所示。取$ U $的$ r $倍组合结果记作$ C $，如式（6）所示，在$ C $中的元素个数为$ {C}_{n}^{r} $。

$ U\triangleq \left\{{N}_{i}\right|i=\mathrm{0, 1}, \cdots , n-1\} $

(5)

$ C\triangleq \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\left(U, r\right) $

(6)

同样地，将训练样本按照输入的批次大小$ b $划分为多个mini batch，并将每个mini batch $ {F}_{j} $平均分为$ {C}_{n}^{r} $份并记作$ P $。将$ {P}_{i} $和$ {C}_{i} $一对一配对，依次将每个$ {P}_{i} $发送至对应$ {C}_{i} $表示的节点集合上。此时，每个节点上存在的待处理样本块个数为$ \mu =r\cdot {C}_{n}^{r}/n $，且每个样本被拷贝并发送至$ r $个不同节点上。依照上述算法流程可将数据集$ F $平均分配到$ N $中的每个计算节点上，每个节点上的样本数据数目可根据节点的性能进行动态调整，且在一定限度内不会影响其他节点的负载。

2.2 编码过程

本文通过对中间结果矩阵进行编码，可压缩每个节点发送的数据量，同时实现数据多播以减少发送时间。由于在任务分配时使用冗余分发策略，因此每个节点所需的中间结果数据可以从$ r $个包含该数据的节点处获取，因此每个节点可以仅发送必要数据的$ 1/r $，由接收节点自行拼装完整结果。同时，由于多个节点间存在冗余数据，因此一份数据可以被多个节点共有，使用编码策略将要发送的多个数据分片累加，将中间结果数据多播给多个节点，每个节点接收到累加结果后减去已知部分，即可得到所需部分的结果。上述编码过程可在不影响计算速度的情况下有效降低发送的数据量，一般情况下该过程可将数据量降低至朴素方法的$ 1/n $。

数据传输编码算法的伪代码如算法3所示，具体过程为在给定所有中间结果矩阵的列表$ B $、当前节点$ N $和冗余度r的情况下获取中间结果集合$ \mathcal{C} $，其中，$ \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\_\mathrm{o}\mathrm{f}(\mathit{\boldsymbol G}, N) $返回在编码过程中节点$ N $获取梯度矩阵$ \mathit{\boldsymbol G} $的拆分子矩阵编号，$ \mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_\mathrm{i}\mathrm{d}\_\mathrm{o}\mathrm{f}\left(\mathit{\boldsymbol G}\right) $返回用于计算$ \mathit{\boldsymbol G} $所使用的样本块编号，$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{o}\mathrm{f}(\mathit{\boldsymbol G}, N) $返回在编码过程中节点$ N $应获取的对应$ \mathit{\boldsymbol G} $的拆分子矩阵，$ \mathrm{a}\mathrm{d}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{r}\mathrm{y}\_\mathrm{o}\mathrm{f}\left(\mathit{\boldsymbol G}\right) $返回不具有$ \mathit{\boldsymbol G} $的所有节点，$ \mathrm{g}\mathrm{e}\mathrm{t}\_\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{y}\left(T\right) $返回列表$ T $中只出现一次的元素，$ \mathrm{p}\mathrm{a}\mathrm{c}\mathrm{k}(M, P, J, T) $将内容$ M\mathrm{、}P\mathrm{、}J\mathrm{、}T $打包并等待发送。

算法3   数据传输编码算法

输入    list of all gradient matrix $ B $，current node $ N $，redundancy $ r $

输出   intermediate result set $ \mathcal{C} $

1.initialize $ \mathcal{C} $ as empty set；

2.for each $ \mathrm{R} $ in $ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\left(\mathrm{B}, \mathrm{r}\right) $ do

3.initialize $ \mathrm{M} \; \mathrm{ }\mathrm{a}\mathrm{s} \; \mathrm{ }0 $；

4.initialize $ \mathrm{P}, \mathrm{J} $ as empty set；

5.initialize $ \mathrm{T} $ as empty list；

6.for each $ \mathrm{G} $ in $ \mathrm{R} $ do

7.$ \mathrm{P}\leftarrow \mathrm{P}+\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\_\mathrm{o}\mathrm{f}(\mathrm{G}, \mathrm{ }\mathrm{N}) $；

8.$ \mathrm{J}\mathrm{ }\leftarrow \mathrm{J}+\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_\mathrm{i}\mathrm{d}\_\mathrm{o}\mathrm{f}\left(\mathrm{G}\right) $；

9.$ \mathrm{M}\leftarrow \mathrm{M}+\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{o}\mathrm{f}(\mathrm{G}, \mathrm{ }\mathrm{N}) $；

10.$ \mathrm{T}\leftarrow \mathrm{T}+\mathrm{a}\mathrm{d}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{r}\mathrm{y}\_\mathrm{o}\mathrm{f}\left(\mathrm{G}\right) $；

11.end for

12.$ \mathrm{T}\leftarrow \mathrm{g}\mathrm{e}\mathrm{t}\_\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{y}\left(\mathrm{T}\right) $；

13.$ \mathcal{C} $←$ \mathcal{C} $ $ +\mathrm{ }\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{k}(\mathrm{M}, \mathrm{ }\mathrm{P}, \mathrm{ }\mathrm{J}, \mathrm{ }\mathrm{T}) $；

14.end for

15.return $ \mathcal{C} $；

按照算法3的执行过程，定义编码的运算过程发生在节点$ {N}_{i} $、神经网络层$ {L}_{l} $、批次样本$ {F}_{j} $和批次样本中的块$ {P}_{q} $上，四元组$ \left(i, l, j, q\mathrm{ }\right) $表示运算过程发生的环境，例如，在节点$ {N}_{i} $和层$ {L}_{l} $上批次为$ {F}_{j} $且由全局编号为$ q $的样本块计算所得的梯度记作$ {\mathit{\boldsymbol G}}_{\left(i, l, j, q\mathrm{ }\right)} $。当某个对象的存在与某个下标对应的维度无关时，将其标记为数学中的任意符号$ \forall $，例如样本的存在与神经网络层数无关，因此在节点$ {N}_{i} $上批次为$ {F}_{j} $且全局编号为$ i $的样本块记作$ {F}_{\left(i, \forall l, j, q\right)} $。在样本块分发完毕后，每个节点在其接收到的样本块上执行前向传播和反向传播算法，计算以该样本块所得损失对网络参数$ {w}_{\left(i, l, j, q\right)} $的一阶梯度，一个块内所有样本的对应损失的梯度加和记作$ {\mathit{\boldsymbol G}}_{\left(i, l, j, q\right)} $。

将节点$ {N}_{i} $在任务分配阶段获得的$ \mu $个第$ j $批次样本块在层$ {\mathcal{L}}_{l} $上计算得到的梯度矩阵记作$ {\mathit{\boldsymbol G}}_{\left(i, l, j, \forall \right)} $，如式（7）所示。在$ {B}_{\left(i, l, j, \forall q\right)} $中取$ r $个元素进行组合，将包含$ {C}_{\mu }^{r} $个组合结果的结果集记作$ {R}_{\left(i, l, j, \forall q\right)} $，如式（8）所示。将$ {R}_{\left(i, l, j, \forall q\right)} $中的组合结果记作$ {R}_{\left(i, l, j, \forall q\right)}^{s} $，如式（9）所示。

$ {B}_{\left(i, l, j, \forall q\right)}\triangleq \left\{{\mathit{\boldsymbol G}}_{\left(i, l, j, {q}_{z}\right)}:z=\mathrm{1, 2}, \cdots , \mu \right\} $

(7)

$ {R}_{\left(i, l, j, \forall q\right)}\triangleq \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\left(B, r\right) $

(8)

$ \begin{array}{l}{R}_{\left(i, l, j, \forall q\right)}^{s}\triangleq \\ \left\{{\mathit{\boldsymbol G}}_{\left(i, l, j, {d}_{1}\right)}, {\mathit{\boldsymbol G}}_{\left(i, l, j, {d}_{2}\right)}, \cdots , {\mathit{\boldsymbol G}}_{\left(q, l, j, {d}_{r}\right)}:{d}_{1}<{d}_{2}<\cdots <{d}_{r}\right\}\mathrm{ }\end{array} $

(9)

本文依次获取$ {R}_{\left(i, l, j, \forall q\right)} $中的组合结果$ {R}_{\left(i, l, j, \forall q\right)}^{s} $，对于每一个组合结果$ {R}_{\left(i, l, j, \forall q\right)}^{s} $，将其编码成一个要发送的数据包，数据包中包含组合结果的所有块编号$ {P}_{\left(i, l, j, \forall q\right)}^{s} $、组合结果拆分位置$ {J}_{\left(i, l, j, \forall q\right)}^{s} $和组合结果内容$ {M}_{\left(i, l, j, \forall q\right)}^{s} $。初始化$ {P}_{\left(i, l, j, \forall q\right)}^{s} $、$ {J}_{\left(i, l, j, \forall q\right)}^{s} $、$ {M}_{\left(i, l, j, \forall q\right)}^{s} $及发送目的节点集合$ {T}_{\left(i, l, j, \forall q\right)}^{s} $为空。将集合$ {R}_{\left(i, l, j, \forall q\right)}^{s} $中的元素$ {\mathit{\boldsymbol G}}_{\left(i, l, j, d\mathrm{ }\right)} $进行拆分，通过按行向量或者按列向量进行拆分，梯度矩阵按列拆分的示例如图 3所示。

将梯度矩阵$ {\mathit{\boldsymbol G}}_{\left(i, l, j, d\mathrm{ }\right)} $拆分成$ r $份，每个拆分子矩阵记作$ {B}_{\left(i, l, j, d\right)}^{s, k}, k=\mathrm{0, 1}, \cdots , r-1 $。将拆分所得的结果集合记作$ {\mathcal{G}}_{\left(i, l, j, \forall i\mathrm{ }\right)}^{s} $，如式（10）所示。对每一个梯度矩阵$ {\mathit{\boldsymbol G}}_{\left(i, l, j, d\mathrm{ }\right)} $，根据其计算来源样本块$ {F}_{\left(i, l, j, d\mathrm{ }\right)} $，得到其在数据分发时对应的分发节点集合$ {C}_{i} $，如式（11）所示。

$ {\mathcal{G}}_{\left(i, l, j, \forall i\right)}^{s}\triangleq \left\{{B}_{\left(i, l, j, d\right)}^{s, k}:k=\mathrm{0, 1}, 5\cdots , r-1, d={d}_{1}, {d}_{2}, \cdots , {d}_{r}\right\} $

(10)

$ {C}_{i}\triangleq \left\{{N}_{{a}_{1}}, {N}_{{a}_{2}}, \cdots , {N}_{{a}_{r}}:{a}_{1}<{a}_{2}<\cdots <{a}_{r}\right\} $

(11)

将$ {C}_{i} $中的节点下标编号$ {a}_{q} $进行升序排序，获取当前下标节点$ {N}_{q} $在升序排列后的节点列表中的位置记作$ \alpha $，例如在节点组合$ \left\{{N}_{1}, {N}_{2}, {N}_{3}\right\} $中，节点$ {N}_{1} $对应的位置$ \alpha =0 $，节点$ {N}_{3} $对应的位置$ \alpha =2 $。获取位置信息$ {\alpha }_{i} $并将其添加至组合结果拆分位置信息$ {P}_{\left(i, l, j, \forall q\right)}^{s} $，同时将该块编号信息$ d $添加至块编号信息$ {J}_{\left(i, l, j, \forall q\right)}^{s} $。对应每个样本块都可获取一个该节点在该样本块分发列表中的位置$ {\alpha }_{i} $，那么可以由上述数据求得$ {M}_{\left(i, l, j, \forall q\right)}^{s} $，如式（12）所示。遍历编码$ {M}_{\left(i, l, j, \forall q\right)}^{s} $所用的编码梯度矩阵$ {\mathit{\boldsymbol G}}_{\left(i, l, j, \forall q\right)} $求解$ {A}_{i} $，如式（13）所示。叠加所有的$ {A}_{i} $并获取其中仅出现一次的节点，将其添加至编码包的发送目标列表$ {T}_{\left(i, l, j, \forall q\right)}^{s} $。

$ M_{\left( {i,l,j,\forall q} \right)}^s = \sum\limits_d {B_{\left( {i,l,j,d} \right)}^{s,{\alpha _d}}} $

(12)

$ {A}_{i}\triangleq U-{C}_{i} $

(13)

至此，就能获取编码包所需的$ {P}_{\left(i, l, j, \forall q\right)}^{s} $、$ {J}_{\left(i, l, j, \forall q\right)}^{s} $、$ {M}_{\left(i, l, j, \forall q\right)}^{s} $和$ {T}_{\left(i, l, j, \forall q\right)}^{s} $信息并将发送信息记作$ {C}_{\left(i, l, j, \forall q\right)}^{s} $，如式（14）所示。当$ {C}_{\left(i, l, j, \forall q\right)}^{s} $缓存至空闲网络时，多播上述信息至$ {T}_{\left(i, l, j, \forall q\right)}^{s} $所有节点上。

$ {C}_{\left(i, l, j, \forall q\right)}^{s}\triangleq \mathrm{p}\mathrm{a}\mathrm{c}\mathrm{k}\left({P}_{\left(i, l, j, \forall q\right)}^{s}, {J}_{\left(i, l, j, \forall q\right)}^{s}, {M}_{\left(i, l, j, \forall q\right)}^{s}, {T}_{\left(i, l, j, \forall q\right)}^{s}\right) $

(14)

2.3 解码过程

根据编码时的累加结果和分片规则，解码时应按照编码时的运算过程反向求取节点所需的内容。首先通过减法减去节点已知的数据内容，求取未知的数据内容，然后按照分片规则，还原中间结果矩阵，以获取完整的中间结果。数据传输解码算法的伪代码如算法4所示，主要功能为在给定所有中间结果矩阵列表B和接收到的编码数据包$ H $的情况下输出矩阵切片（$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t} $）、切片编号（$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{i}\mathrm{d} $）和切片位置（$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_ $ $ \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n} $），其中，$ \mathrm{c}\mathrm{a}\mathrm{n}\_\mathrm{g}\mathrm{e}\mathrm{t}\left(B, \mathrm{i}\mathrm{d}\right) $判断节点是否包含样本块编号为$ \mathrm{i}\mathrm{d} $所计算出的梯度矩阵，$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\_\mathrm{o}\mathrm{f}\left(B, \mathrm{i}\mathrm{d}, \mathrm{p}\mathrm{o}\mathrm{s}\right) $获取对应编号$ \mathrm{i}\mathrm{d} $的样本块计算出的梯度矩阵的第$ \mathrm{p}\mathrm{o}\mathrm{s} $个拆分子矩阵。

算法4   数据传输解码算法

输入    list of all gradient matrix $ B $，coded package $ H $

输出    $ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}, \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{i}\mathrm{d}, \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n} $

1.$ \mathrm{i}\mathrm{d}\mathrm{s}\leftarrow \mathrm{H}.\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_\mathrm{i}\mathrm{d}\mathrm{s} $；//获取H的块编号

2.$ \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{s}\leftarrow \mathrm{H}.\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s} $；//获取$ \mathrm{H} $中内容的位置编号

3.$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}\leftarrow \mathrm{H}.\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t} $；//获取$ \mathrm{H} $中包含的矩阵内容

4.for each $ (\mathrm{i}\mathrm{d}, \mathrm{p}\mathrm{o}\mathrm{s}) $ in $ (\mathrm{i}\mathrm{d}\mathrm{s}, \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{s}) $ do

5.if $ \mathrm{c}\mathrm{a}\mathrm{n}\_\mathrm{g}\mathrm{e}\mathrm{t}\left(\mathrm{B}, \mathrm{i}\mathrm{d}\right) $ then

6.$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}\leftarrow \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}-\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\_\mathrm{o}\mathrm{f}\left(\mathrm{B}, \mathrm{i}\mathrm{d}, \mathrm{p}\mathrm{o}\mathrm{s}\right) $；

7.else

8.$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{i}\mathrm{d}\leftarrow \mathrm{i}\mathrm{d} $；

9.$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\leftarrow \mathrm{p}\mathrm{o}\mathrm{s} $；

10.end if

11.end for

12.return $ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}, \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{i}\mathrm{d}, \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{s}\_\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n} $；

在编码包中已包含编码所用样本块编号和编码拆分矩阵的位置信息，依据发送规则可从编码包中提取节点$ {N}_{i} $缺失的信息，将发送编码包给节点$ {N}_{i} $的节点记作$ {N}_{{i}^{\text{'}}} $，将节点$ {N}_{{i}^{\text{'}}} $发送返回的信息记作$ {H}_{\left({i}^{\text{'}}, l, j, \forall q\right)}^{s} $。由于编码包中已包含样本块和拆分子矩阵位置信息，因此可利用节点$ {N}_{i} $已有的信息解码未知信息，如式（15）所示。根据任务分配算法，将节点$ {N}_{i} $缺失的样本块记作$ {F}_{\left(i, l, j, {q}_{v}\right)}, v=\mathrm{1, 2}, \cdots , {C}_{n}^{r}-\mu $，对应这些缺失样本所需的梯度中间结果记作$ {\mathit{G}}_{\left(i, l, j, {q}_{v}\right)}, v=\mathrm{1, 2}, \cdots , {C}_{n}^{r}-\mu $。当节点$ {N}_{q} $获取到所有缺失信息$ {M}_{\left(\forall i, l, j, {q}_{v}\right)}^{k} $后，将其依照拆分规则进行合并，如式（16）所示。当节点$ {N}_{q} $获取到所有样本块对应的缺失梯度时，使用式（16）和式（17）计算全局梯度，该全局梯度即进一步迭代所需的模型参数增量，如式（18）所示。

$ {M}_{\left(\forall i, l, j, {q}_{v}\right)}^{k}={H}_{\left({i}^{\text{'}}, l, j, \forall q\right)}^{s}-\sum\limits_{{q}_{z}, {q}_{z}\ne {q}_{v}}{B}_{\left(i, l, j, {q}_{z}\right)} $

(15)

$ {\mathit{\boldsymbol M}}_{\left(\forall i, l, j, {q}_{v}\right)}=\left(\begin{array}{c}{M}_{\left(\forall i, l, j, {q}_{v}\right)}^{0}\\ {M}_{\left(\forall i, l, j, {q}_{v}\right)}^{1}\\ \begin{array}{l}⋮\\ {M}_{\left(\forall i, l, j, {q}_{v}\right)}^{r}\end{array}\end{array}\right) $

(16)

$ {\mathit{\boldsymbol G}}_{\left(i, l, j, \forall \right)}=\frac{1}{\left|{F}_{j}\right|}\left[\sum\limits_{{i}_{v}}{\mathit{\boldsymbol M}}_{\left(i, l, j, {q}_{v}\right)}+\sum\limits_{{i}_{z}}{\mathit{\boldsymbol G}}_{\left(i, l, j, {q}_{z}\right)}\right] $

(17)

$ ∆{w}_{i}\left(t\right)\leftarrow {\mathit{\boldsymbol G}}_{\left(i, l, j, \forall \right)} $

(18)

2.4 通信负载计算

若假设本文同步随机梯度下降算法的通信负载为$ {L}_{\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}} $，传统不使用多播技术的梯度下降算法的通信负载为$ {L}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}} $，则两者存在式（19）所述的关系：

$ \frac{{L}_{\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}}}{{L}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}}}=\frac{{C}_{n}^{r+1}\cdot \left(r+1\right)\cdot \frac{1}{r}}{\left(n-1\right)\cdot {C}_{n}^{r}}=\frac{n-r}{n-1}\cdot \frac{1}{r} $

(19)

对上述关系进行证明，具体证明过程如下：使用编码策略进行任务分发和交换，节点数目为$ n $，数据分配冗余度为$ r $，每个划分占总批次大小为$ {a}_{1}, {a}_{2}, \cdots , {a}_{p} $，其中$ p={C}_{n}^{r} $，每个节点获取$ {a}_{1}, {a}_{2}, \cdots , {a}_{p} $中的$ {D}_{\mathrm{h}\mathrm{a}\mathrm{v}\mathrm{e}} $个样本块（如式（20）所示），并缺少其中的$ {D}_{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}} $个样本块（如式（21）所示）。将节点$ i $包含的所有样本块集合记作$ {\mathcal{D}}_{i} $，如式（22）所示。

$ {D}_{\mathrm{h}\mathrm{a}\mathrm{v}\mathrm{e}}\triangleq r\cdot {C}_{n}^{r}/n={C}_{n-1}^{r-1} $

(20)

$ {D}_{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}}\triangleq {C}_{n}^{r}-r\cdot {C}_{n}^{r}/n $

(21)

$ {\mathcal{D}}_{i}\triangleq \left\{{P}_{i}\right|{P}_{i}\mathrm{是}\mathrm{发}\mathrm{送}\mathrm{给}\mathrm{节}\mathrm{点}i\mathrm{的}\mathrm{样}\mathrm{本}\mathrm{块}\} $

(22)

对于$ n $个节点中任意$ r $个节点组成的节点子集，其中一定存在$ 1 $个样本块被这$ r $个节点所共有，因为样本块分发标签包含了所有节点编号可以形成的组合，所以任意$ r $个节点必然属于$ {C}_{n}^{r} $种选择中的一个节点，如式（23）所示。同理，对于任意$ r+1 $个节点组成的节点组至少存在$ {C}_{r+1}^{r} $个这样的样本块，如式（24）所示。在$ n $个节点组成的集群中共有$ {C}_{n}^{r+1} $个节点组，每个节点组选取其中$ {C}_{r+1}^{r} $个样本块$ {\mathcal{D}}_{\mathrm{e}\mathrm{x}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}} $进行数据交换，每个节点仅发送由样本块$ {\mathcal{D}}_{\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}} $计算所得的数据，如式（25）、式（26）所示。

$ \left|{\mathcal{D}}_{{i}_{1}}\bigcap {\mathcal{D}}_{{i}_{2}}\bigcap \cdots \bigcap {\mathcal{D}}_{{i}_{r}}\right|=1 $

(23)

$ \left|{\mathcal{D}}_{{i}_{1}}\bigcap {\mathcal{D}}_{{i}_{2}}\bigcap \cdots \bigcap {\mathcal{D}}_{{i}_{r+1}}\right|=r+1 $

(24)

$ {\mathcal{D}}_{\mathrm{e}\mathrm{x}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}\triangleq {\mathcal{D}}_{{i}_{1}}\bigcap {\mathcal{D}}_{{i}_{2}}\bigcap \cdots \bigcap {\mathcal{D}}_{{i}_{r+1}} $

(25)

$ {\mathcal{D}}_{\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}}\triangleq {\mathcal{D}}_{{i}_{1}}\bigcap {\mathcal{D}}_{{i}_{2}}\bigcap \cdots \bigcap {\mathcal{D}}_{{i}_{r}} $

(26)

每个包含$ {\mathcal{D}}_{\mathrm{e}\mathrm{x}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}} $的节点都互相不重复地将$ {\mathcal{D}}_{\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}} $的$ 1/r $信息多播给其他所有节点。因为任意一个样本块只可能被一个节点组完全包含，所以每个节点组内部沟通的信息是互不重复的。每个节点发送$ 1/r $的信息，在一次交互完成后，每个节点总能从其他节点发送的（$ r\cdot 1/r $）数据中获取一个完整的中间结果。取任意节点$ {N}_{i} $，节点$ {N}_{i} $能够参与到$ {C}_{n}^{r+1} $中的$ {C}_{n-1}^{r} $个节点组中进行数据交换，那么在$ {C}_{n-1}^{r} $次数据交换后，节点$ {N}_{i} $能够获得（$ r\cdot 1/r\cdot {C}_{n-1}^{r} $）份中间计算结果，其中：

$ r\cdot \frac{1}{r}\cdot {C}_{n-1}^{r}={C}_{n-1}^{r}={C}_{n}^{r}\cdot \left(\frac{n-r}{n}\right)={C}_{n}^{r}-\frac{r\cdot {C}_{n}^{r}}{n}={D}_{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}} $

(27)

由于节点$ {N}_{i} $完成所有分组交换后数据都不重复，因此其能够获得所有的$ {D}_{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}} $中间信息，使用$ {C}_{n}^{r+1} $个节点组进行完全分组信息交换后，总的多播通信量如式（28）所示。对于具有同样冗余度的传统通信方式，每个节点所需通信量如式（29）所示，本文中的冗余度是指在同一样本块上进行计算的节点数量。对于不使用冗余策略的普通通信方式，每个节点缺少的数据是相互独立的，所需的通信量如式（30）所示。综上，式（19）所述的编码策略通信负载与传统方法通信负载之间的关系得以证明。

$ {L}_{\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}}={C}_{n}^{r+1}\cdot \left(r+1\right)\cdot \frac{1}{r} $

(28)

$ {L}_{\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}}=n\cdot {D}_{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}}=\left(n-r\right)\cdot {C}_{n}^{r} $

(29)

$ {L}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}}=\left(n-1\right)\cdot {C}_{n}^{r} $

(30)

3 实验与结果分析 3.1 实验方法

本文通过神经网络对SSGD、ASGD和本文CSSGD算法进行分布式训练实验，对比在不同节点数目的情况下3种算法到达指定训练精确度所需物理时钟时间和数据传输量，并利用集群模拟对上述指标进行实验验证，实验中共使用10个计算节点，每个计算节点的配置信息如表 1所示。本文使用MNIST和CIFAR-10数据集在卷积神经网络（Convolutional Neural Network，CNN）和DNN上进行实验。表 2给出CNN和DNN在不限时单机执行环境下所得的测试精确度，以此测试精确度作为最优测试精确度，并在实验中对比3种算法的测试精确度。

为保证浮点数执行编码运算后的精确度，本文对计算产生的中间结果进行量化，使用32位整型保存运算所需的浮点数据，设置中间结果区间为[$ - $10，10]，取$ 0\mathrm{x}7\mathrm{F}\mathrm{F}\mathrm{F}\mathrm{F}\mathrm{F}\mathrm{F}\mathrm{F} $为10，取$ 0\mathrm{x}80000001 $为$ -10 $，等区间划分取值，并使用该量化结果进行运算和编码。本文在实验中对不同节点的网络使用不同的样本划分，在2个节点上只执行二分类，在3个节点上只执行三分类任务，以此类推，保证每次测试时每个节点都能够执行相同数据量的任务，分析由通信瓶颈导致的性能损失问题，同时以串行算法测试所得结果作为目标精确度。

3.2 实验结果

本文首先对CSSGD算法在DNN与CNN上的训练结果进行评估，然后使用SSGD、ASGD和CSSGD算法在MNIST数据集上训练DNN、在CIFAR-10数据集上训练CNN。在训练过程中，使用10个训练节点（ASGD算法额外使用一个参数服务器）并记录测试精确度的变化情况。由于CSSGD算法的目的是减少训练执行时间，因此实验着重讨论3种算法到达相同测试精确度的时间。

3.2.1 训练性能分析

DNN和CNN的训练结果如图 4和图 5所示，可以看出CSSGD、SSGD和ASGD算法在充足的训练时间下，均可达到最终的测试精确度。

本节实验着重分析3种算法训练所需的时间，在限定的测试精确度下比较算法执行所需的时间以评估算法执行效率。实验在CNN和DNN的原始训练结果中，在接近目标精确度附近选取一个相对3种算法差异最大的基准测试精确度进行后续实验。如图 6、图 7所示，对于使用MNIST数据集的DNN，其选取的基准测试精确度为82%，对于使用CIFAR-10数据集的CNN，其选取的基准测试精确度为70%。下文将针对这组基准测试精确度，比较3种算法的执行效率。

后续实验从3个方面详细分析了CSSGD算法的执行效率：1）由于ASGD算法无独占通信时间，因此在DNN和CNN训练过程中，对比使用CSSGD与SSGD算法在训练时间和通信总量上的差别；2）针对理论推导结果，通过实验验证不同冗余度设置下CSSGD算法的每批次训练时间；3）使用相同的样本数据集和神经网络在上述集群环境下，对比ASGD、SSGD和CSSGD算法训练至基准测试精确度所需的训练时间。

3.2.2 DNN实验结果分析

图 8展示了DNN训练中SSGD和CSSGD算法在MNIST数据集上达到82%测试精确度所需的时间，其中，SSGD Multicast和SSGD Unicast分别表示基于多播技术的SSGD算法和基于单播技术的SSGD算法，CSSGD r=2和CSSGD r=3分别表示冗余度为2的CSSGD算法和冗余度为3的CSSGD算法，可以看出CSSGD算法能够有效降低SSGD算法执行所需时间。图 9展示了DNN训练中SSGD Multicast和CSSGD算法占用的网络数据通信总量，可以看出CSSGD算法占用的网络数据通信总量相对SSGD算法更少。

3.2.3 CNN实验结果分析

图 10展示了CNN训练中SSGD与CSSGD算法在CIFAR-10数据集上达到70%测试精确度所需的时间。在DNN训练过程中产生的权值矩阵相对CNN更大，容易由于网络速度限制造成计算瓶颈，如果对该类别网络使用CSSGD算法，则可以有效缓解通信瓶颈问题。在CNN中执行计算所需时间比DNN更多，因此其对通信瓶颈的影响相对DNN更小，在使用CSSGD算法进行编码梯度下降时，其所能获得的测试精确度相对DNN更低。图 11展示了CNN训练中SSGD Multicast和CSSGD算法占用的网络数据通信总量，可以看出CSSGD算法在CNN和DNN训练中都能够有效降低中间结果的通信总量，但是CNN计算中数据通信所占时间相较DNN更少，因此数据通信优化对总体执行性能的影响较小。

3.2.4 冗余度分析

根据上文对编码过程的理论推导可以得出，当所需通信时间与数据通信总量呈线性相关时，CSSGD算法单一批次训练所需时间$ {T}_{\mathrm{C}\mathrm{S}\mathrm{S}\mathrm{G}\mathrm{D}} $可表示为每批次计算时间和每批次通信时间之和，假设SSGD多播算法中一个批次计算所需时间为$ {T}_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}} $、中间结果传输所需时间为$ {T}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}} $，则$ {T}_{\mathrm{C}\mathrm{S}\mathrm{S}\mathrm{G}\mathrm{D}} $可表示为$ {T}_{\mathrm{C}\mathrm{S}\mathrm{S}\mathrm{G}\mathrm{D}}=r·{T}_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}}+1/r·{T}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}} $，可以看出，当$ {T}_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}} $和$ {T}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}} $为定值时存在一个确定的冗余度使得$ {T}_{\mathrm{C}\mathrm{S}\mathrm{S}\mathrm{G}\mathrm{D}} $最小。本文在8个计算节点的情况下对不同冗余度的CSSGD算法单一批次迭代所需时间进行实验，结果如图 12、图 13所示，可以看出在DNN和CNN训练中的最佳冗余度分别为3和$ 2 $。由实验结果可以得出和理论推导相同的结论，即在固定的计算时间和传输时间下，每个节点都存在确定的冗余度，当冗余度为$ r $时整个分布式集群单一批次的训练时间最短。

3.2.5 训练时间分析

本节对比ASGD、SSGD Multicast和最优冗余度下的CSSGD（CSSGD Optimal）算法的实际训练时间，如图 14和图 15所示，由于ASGD算法异步执行过程导致其执行状态难以确定，最终收敛所需次数也存在一定的随机性，因此对ASGD算法进行10次实验取训练时间的平均值。可以看出，在通信瓶颈问题较严重的DNN训练过程中，CSSGD算法相对于SSGD和ASGD算法可取得明显的效率提升，在DNN的分布式训练中，相对SSGD和ASGD平均能减少53.97%和26.89%的训练时间。在CNN训练过程中由于计算执行过程占总执行时间的比例较高，因此通过添加冗余编码来降低通信负载的CSSGD算法效率提升较少，但是ASGD算法需要更多的计算开销来消除梯度延迟问题带来的干扰，因此CSSGD算法相对SSGD和ASGD算法效率依然有一定的提升，在CNN分布式训练中，相对SSGD和ASGD平均能减少39.11%和26.37%的训练时间。实验中给出10个计算节点以内的训练时间结果，可以看出，ASGD和CSSGD算法在分布式系统上的性能不能随节点数目线性提升，随着节点数目的增多，ASGD算法的理论同步更新概率会越来越小，迭代所需时间会继续增加，CSSGD算法也会受到额外通信负载和多播带宽拥塞的影响，但是其在更多节点加入后可更新其最优冗余度参数配置，能够达到更好的训练效果。

4 结束语

本文针对异步随机梯度下降算法的高通信负载问题，提出一种基于分布式编码计算的同步梯度下降算法，通过冗余分发策略降低通信负载并消除通信瓶颈对分布式集群的影响。实验结果表明，当配置合适的超参数时，与SSGD和ASGD算法相比，该算法在DNN分布式训练中能平均减少53.97%和26.89%的训练时间，在CNN分布式训练中能平均减少39.11%和26.37%的训练时间，降低了分布式集群上的通信负载。下一步将研究并行梯度下降算法在分布式集群上的应用，并分析数值量化误差对最终损失函数收敛性能的影响。