李博文，謝在鵬，毛鶯池，徐媛媛，朱曉瑞，張 基

（河海大學(xué)計(jì)算機(jī)與信息學(xué)院，南京 211100）

0 概述

近年來，深度學(xué)習(xí)技術(shù)已在語(yǔ)音識(shí)別［1-2］、計(jì)算機(jī)視覺［3-4］和自然語(yǔ)言處理［5］等領(lǐng)域得到廣泛應(yīng)用并取得了眾多研究成果。在深度學(xué)習(xí)任務(wù)中常使用梯度下降（Gradient Descent，GD）算法作為深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）模型訓(xùn)練的主要算法［6-7］，然而由于數(shù)據(jù)量的爆炸式增長(zhǎng)，現(xiàn)有單機(jī)系統(tǒng)已無(wú)法滿足梯度下降算法對(duì)計(jì)算資源的龐大需求。分布式技術(shù)通過多機(jī)協(xié)同計(jì)算的方式，使用多個(gè)計(jì)算節(jié)點(diǎn)擴(kuò)充計(jì)算性能，可提供梯度下降算法所需的大量計(jì)算資源，因此研究梯度下降算法在分布式集群上的并行化計(jì)算非常必要［8］。

目前，深度神經(jīng)網(wǎng)絡(luò)分布式訓(xùn)練中通常使用數(shù)據(jù)并行化方法，基于數(shù)據(jù)并行化的梯度下降算法包括同步隨機(jī)梯度下降［9］（Synchronized Stochastic Gradient Descent，SSGD）和異步隨機(jī)梯度下降［10］（Asynchronized Stochastic Gradient Descent，ASGD）兩種算法。同步算法在每次迭代過程中通過同步各個(gè)節(jié)點(diǎn)的狀態(tài)來保持狀態(tài)一致，因此同步梯度下降能夠保持和單機(jī)串行算法相同的收斂方向，從而導(dǎo)致其所需的通信量相對(duì)其他算法更多，容易受分布式集群中的通信瓶頸影響，同時(shí)計(jì)算節(jié)點(diǎn)之間需要相互等待傳輸梯度更新結(jié)果，從而造成了計(jì)算資源的浪費(fèi)。異步算法則無(wú)需等待節(jié)點(diǎn)狀態(tài)一致，每個(gè)節(jié)點(diǎn)在更新權(quán)值參數(shù)時(shí)不會(huì)檢查其他節(jié)點(diǎn)的運(yùn)行狀態(tài)，獨(dú)立地更新本地模型到全局模型上，并獲取全局模型參數(shù)繼續(xù)執(zhí)行下一步計(jì)算，如果在該計(jì)算過程中又有其他節(jié)點(diǎn)更新了全局模型，那么該節(jié)點(diǎn)用于執(zhí)行下一步計(jì)算的全局模型參數(shù)就不是最新的，該數(shù)據(jù)交互模式將導(dǎo)致梯度延遲問題［11-12］，而梯度延遲問題又會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)用于執(zhí)行下一步計(jì)算的全局模型不一致。在大規(guī)模分布式集群中，隨著分布式集群中的節(jié)點(diǎn)數(shù)目增加，節(jié)點(diǎn)計(jì)算狀態(tài)保持一致的概率越來越小，節(jié)點(diǎn)之間所需傳輸?shù)男畔⒘恐饾u增多，因此無(wú)論同步或異步算法，都在大規(guī)模分布式集群中存在亟待解決的效率問題。本文提出基于分布式編碼的同步隨機(jī)梯度下降算法CSSGD，通過分布式編碼策略［13-14］降低分布式集群上的通信負(fù)載。

1 相關(guān)工作

近年來，分布式并行梯度下降算法得到了廣泛應(yīng)用，研究人員針對(duì)分布式神經(jīng)網(wǎng)絡(luò)訓(xùn)練開展了大量研究工作，這些工作主要圍繞分布式異構(gòu)計(jì)算和通信負(fù)載兩方面展開。分布式集群是典型的異構(gòu)計(jì)算平臺(tái)，在該異構(gòu)計(jì)算環(huán)境下，每個(gè)執(zhí)行進(jìn)程的執(zhí)行速度和任務(wù)完成時(shí)間均不確定，在同步梯度下降算法中由于系統(tǒng)需要同步每一批次中各個(gè)計(jì)算節(jié)點(diǎn)的狀態(tài)，因此最慢節(jié)點(diǎn)的速度成為限制分布式集群整體任務(wù)運(yùn)行速度的主要因素。文獻(xiàn)［15-16］通過對(duì)每個(gè)節(jié)點(diǎn)的計(jì)算和更新過程進(jìn)行限時(shí)，使每個(gè)節(jié)點(diǎn)都在已有樣本上進(jìn)行逐樣本迭代計(jì)算，以保證每個(gè)節(jié)點(diǎn)都能在任意時(shí)間內(nèi)給出一個(gè)可用但不完整的中間梯度運(yùn)算結(jié)果，降低了節(jié)點(diǎn)異構(gòu)對(duì)整體任務(wù)的影響。文獻(xiàn)［17-18］針對(duì)大矩陣乘法的并行化問題，提出糾纏多項(xiàng)式碼，使用糾纏多項(xiàng)式碼對(duì)矩陣乘法運(yùn)算進(jìn)行拆解，并對(duì)原始矩陣計(jì)算任務(wù)添加一定量的冗余以加快運(yùn)算速度。

此外，并行梯度下降算法還需在各個(gè)計(jì)算節(jié)點(diǎn)之間進(jìn)行密集地?cái)?shù)據(jù)交換，因此分布式集群的通信性能也是影響分布式神經(jīng)網(wǎng)絡(luò)訓(xùn)練性能的主要問題。文獻(xiàn)［19］提出1-Bit 數(shù)值量化方案，使用Adagrad算法進(jìn)行學(xué)習(xí)率迭代并結(jié)合誤差累積回溯，在深度神經(jīng)網(wǎng)絡(luò)中得到一種低通信負(fù)載的分布式神經(jīng)網(wǎng)絡(luò)訓(xùn)練方案。文獻(xiàn)［20］提出批次內(nèi)并行化方法，使用較小的Block 劃分和基于動(dòng)量的參數(shù)迭代方案提高了分布式神經(jīng)網(wǎng)絡(luò)的訓(xùn)練速度。文獻(xiàn)［21］提出改進(jìn)的并行梯度下降算法，在改進(jìn)算法中每個(gè)節(jié)點(diǎn)不再將本地計(jì)算結(jié)果推送給分布式集群中的所有節(jié)點(diǎn)，而是隨機(jī)選取一部分節(jié)點(diǎn)進(jìn)行更新以降低通信負(fù)載。文獻(xiàn)［22］結(jié)合MDS 編碼和分布式通信編碼對(duì)分布式機(jī)器學(xué)習(xí)中的大矩陣乘法進(jìn)行優(yōu)化，有效解決了分布式系統(tǒng)慢節(jié)點(diǎn)和通信瓶頸問題，但其在編碼過程中的冗余量較大。

上述文獻(xiàn)分別從不同角度對(duì)分布式神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程進(jìn)行分析與改進(jìn)，然而在針對(duì)分布式通信瓶頸和分布式計(jì)算異構(gòu)方面，使用量化或隨機(jī)策略不可避免地會(huì)影響網(wǎng)絡(luò)訓(xùn)練精確度，而利用MDS 碼則會(huì)引入更多的通信冗余。本文設(shè)計(jì)一種用于同步梯度下降算法的分布式編碼策略，能夠降低分布式集群上的通信負(fù)載，并保證分布式神經(jīng)網(wǎng)絡(luò)的訓(xùn)練精確度。

2 本文同步隨機(jī)梯度下降算法

梯度下降算法是用于求解目標(biāo)函數(shù)最小值的常用優(yōu)化算法，當(dāng)網(wǎng)絡(luò)模型參數(shù)為w、數(shù)據(jù)集為x和y、目標(biāo)方程為F(w；x，y)時(shí)，計(jì)算公式如式（1）所示，迭代過程的計(jì)算公式如式（2）所示，其中，?F(w；x，y)為目標(biāo)函數(shù)的一階導(dǎo)數(shù)，η為迭代步長(zhǎng)，又稱為學(xué)習(xí)率，t為迭代輪次。在分布式環(huán)境下，并行梯度下降算法在每個(gè)節(jié)點(diǎn)i上求其部分樣本的梯度，計(jì)算公式如式（3）所示，最終匯總至全局模型參數(shù)w(t) 上的計(jì)算公式如式（4）所示。

本文算法是同步梯度下降算法的一種改進(jìn)形式，算法執(zhí)行步驟為：1）將目標(biāo)樣本集合以預(yù)設(shè)批次大小進(jìn)行劃分，在添加冗余后將其平均分配到各個(gè)節(jié)點(diǎn)上；2）每個(gè)節(jié)點(diǎn)都在已有樣本上執(zhí)行反向傳播算法，并對(duì)中間梯度結(jié)果進(jìn)行編碼，同時(shí)將中間梯度結(jié)果進(jìn)行整合，實(shí)現(xiàn)數(shù)據(jù)分組交換；3）每個(gè)節(jié)點(diǎn)根據(jù)接收到的中間結(jié)果數(shù)據(jù)，解碼出該節(jié)點(diǎn)所需的內(nèi)容，繼續(xù)執(zhí)行訓(xùn)練過程。本文算法在任務(wù)分配時(shí)使用冗余分發(fā)策略，因此每個(gè)節(jié)點(diǎn)所需的中間結(jié)果數(shù)據(jù)可以從r個(gè)包含該數(shù)據(jù)的節(jié)點(diǎn)處獲取，因此每個(gè)節(jié)點(diǎn)可以僅發(fā)送必要數(shù)據(jù)的1/r，由接收節(jié)點(diǎn)自行拼裝完整結(jié)果，如圖1 所示。同時(shí)，由于多個(gè)節(jié)點(diǎn)間存在冗余數(shù)據(jù)，因此一份數(shù)據(jù)可以被多個(gè)節(jié)點(diǎn)所共有，使用編碼策略將需要發(fā)送的多個(gè)數(shù)據(jù)分片累加，將中間結(jié)果數(shù)據(jù)多播給多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)接收到累加結(jié)果后減去已知部分，即可得到所需部分的結(jié)果，如圖2所示。本文結(jié)合上述兩種策略并將其擴(kuò)展至梯度矩陣信息交換過程中，提出能夠有效降低梯度下降算法通信負(fù)載的方案。

圖1 冗余分發(fā)策略Fig.1 Redundant distribution strategy

圖2 編碼策略Fig.2 Coding strategy

本文同步隨機(jī)梯度下降算法的偽代碼如算法1所示，具體過程為在給定的訓(xùn)練數(shù)據(jù)集F和迭代次數(shù)T的情況下獲取當(dāng)前最終模型參數(shù)wf。

算法1本文同步隨機(jī)梯度下降算法

2.1 任務(wù)分配過程

本文設(shè)計(jì)一種任務(wù)分配算法，在有n個(gè)計(jì)算節(jié)點(diǎn)的集群上，將訓(xùn)練數(shù)據(jù)集F冗余r倍并平均分配到每個(gè)節(jié)點(diǎn)上，且每個(gè)節(jié)點(diǎn)上的樣本組合不重復(fù)。上述分配過程可以描述為一個(gè)簡(jiǎn)單的排列組合過程，首先要實(shí)現(xiàn)r倍冗余的分配，且每個(gè)節(jié)點(diǎn)上的數(shù)據(jù)組合互不重復(fù)，需要將每個(gè)樣本的r份拷貝發(fā)送到任意r個(gè)不重復(fù)的計(jì)算節(jié)點(diǎn)上。其次要實(shí)現(xiàn)每個(gè)節(jié)點(diǎn)上的樣本數(shù)量一致，將要分配的樣本集合劃分為份，每一份樣本子集都可以對(duì)應(yīng)一個(gè)唯一的分發(fā)路徑，依照組合結(jié)果進(jìn)行分發(fā)，每個(gè)節(jié)點(diǎn)可以接收到（r?）個(gè)樣本集合，完成任務(wù)的平均分配。任務(wù)分配算法的偽代碼如算法2 所示，具體過程為在給定訓(xùn)練數(shù)據(jù)集F、分布式節(jié)點(diǎn)集合U和訓(xùn)練所用的批次大小b的情況下獲取每個(gè)計(jì)算節(jié)點(diǎn)i的本地樣本Di，其中，combinations(U，r) 返回U的r倍所有可能的組合結(jié)果，split_into_batch(F，b) 返回按照批次大小劃分后的數(shù)據(jù)集，split(Fj，C.size)返回Fj平均分為C.size 后的結(jié)果集合。

算法2任務(wù)分配算法

為闡述算法2 的執(zhí)行過程，首先定義分布式集群中所有節(jié)點(diǎn)的集合為U，如式（5）所示。取U的r倍組合結(jié)果記作C，如式（6）所示，在C中的元素個(gè)數(shù)為。

同樣地，將訓(xùn)練樣本按照輸入的批次大小b劃分為多個(gè)mini batch，并將每個(gè)mini batchFj平均分為份并記作P。將Pi和Ci一對(duì)一配對(duì)，依次將每個(gè)Pi發(fā)送至對(duì)應(yīng)Ci表示的節(jié)點(diǎn)集合上。此時(shí)，每個(gè)節(jié)點(diǎn)上存在的待處理樣本塊個(gè)數(shù)為μ=r?/n，且每個(gè)樣本被拷貝并發(fā)送至r個(gè)不同節(jié)點(diǎn)上。依照上述算法流程可將數(shù)據(jù)集F平均分配到N中的每個(gè)計(jì)算節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)上的樣本數(shù)據(jù)數(shù)目可根據(jù)節(jié)點(diǎn)的性能進(jìn)行動(dòng)態(tài)調(diào)整，且在一定限度內(nèi)不會(huì)影響其他節(jié)點(diǎn)的負(fù)載。

2.2 編碼過程

本文通過對(duì)中間結(jié)果矩陣進(jìn)行編碼，可壓縮每個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)量，同時(shí)實(shí)現(xiàn)數(shù)據(jù)多播以減少發(fā)送時(shí)間。由于在任務(wù)分配時(shí)使用冗余分發(fā)策略，因此每個(gè)節(jié)點(diǎn)所需的中間結(jié)果數(shù)據(jù)可以從r個(gè)包含該數(shù)據(jù)的節(jié)點(diǎn)處獲取，因此每個(gè)節(jié)點(diǎn)可以僅發(fā)送必要數(shù)據(jù)的1/r，由接收節(jié)點(diǎn)自行拼裝完整結(jié)果。同時(shí)，由于多個(gè)節(jié)點(diǎn)間存在冗余數(shù)據(jù)，因此一份數(shù)據(jù)可以被多個(gè)節(jié)點(diǎn)共有，使用編碼策略將要發(fā)送的多個(gè)數(shù)據(jù)分片累加，將中間結(jié)果數(shù)據(jù)多播給多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)接收到累加結(jié)果后減去已知部分，即可得到所需部分的結(jié)果。上述編碼過程可在不影響計(jì)算速度的情況下有效降低發(fā)送的數(shù)據(jù)量，一般情況下該過程可將數(shù)據(jù)量降低至樸素方法的1/n。

數(shù)據(jù)傳輸編碼算法的偽代碼如算法3 所示，具體過程為在給定所有中間結(jié)果矩陣的列表B、當(dāng)前節(jié)點(diǎn)N和冗余度r的情況下獲取中間結(jié)果集合C，其中，position_of(G，N)返回在編碼過程中節(jié)點(diǎn)N獲取梯度矩陣G的拆分子矩陣編號(hào)，block_id_of(G)返回用于計(jì)算G所使用的樣本塊編號(hào)，content_of(G，N)返回在編碼過程中節(jié)點(diǎn)N應(yīng)獲取的對(duì)應(yīng)G的拆分子矩陣，adversary_of(G)返回不具有G的所有節(jié)點(diǎn)，get_singularity(T)返回列表T中只出現(xiàn)一次的元素，pack(M，P，J，T)將內(nèi)容M、P、J、T打包并等待發(fā)送。

算法3數(shù)據(jù)傳輸編碼算法

按照算法3 的執(zhí)行過程，定義編碼的運(yùn)算過程發(fā)生在節(jié)點(diǎn)Ni、神經(jīng)網(wǎng)絡(luò)層Ll、批次樣本Fj和批次樣本中的塊Pq上，四元組(i，l，j，q)表示運(yùn)算過程發(fā)生的環(huán)境，例如，在節(jié)點(diǎn)Ni和層Ll上批次為Fj且由全局編號(hào)為q的樣本塊計(jì)算所得的梯度記作G(i，l，j，q)。當(dāng)某個(gè)對(duì)象的存在與某個(gè)下標(biāo)對(duì)應(yīng)的維度無(wú)關(guān)時(shí)，將其標(biāo)記為數(shù)學(xué)中的任意符號(hào)?，例如樣本的存在與神經(jīng)網(wǎng)絡(luò)層數(shù)無(wú)關(guān)，因此在節(jié)點(diǎn)Ni上批次為Fj且全局編號(hào)為i的樣本塊記作F(i，?l，j，q)。在樣本塊分發(fā)完畢后，每個(gè)節(jié)點(diǎn)在其接收到的樣本塊上執(zhí)行前向傳播和反向傳播算法，計(jì)算以該樣本塊所得損失對(duì)網(wǎng)絡(luò)參數(shù)w(i，l，j，q)的一階梯度，一個(gè)塊內(nèi)所有樣本的對(duì)應(yīng)損失的梯度加和記作G(i，l，j，q)。

將節(jié)點(diǎn)Ni在任務(wù)分配階段獲得的μ個(gè)第j批次樣本塊在層Ll上計(jì)算得到的梯度矩陣記作G(i，l，j，?)，如式（7）所示。在B(i，l，j，?q)中取r個(gè)元素進(jìn)行組合，將包含個(gè)組合結(jié)果的結(jié)果集記作R(i，l，j，?q)，如式（8）所示。將R(i，l，j，?q)中的組合結(jié)果記作，如式（9）所示。

圖3 梯度矩陣按列拆分的示例Fig.3 Example for splitting a gradient matrix by column

將Ci中的節(jié)點(diǎn)下標(biāo)編號(hào)aq進(jìn)行升序排序，獲取當(dāng)前下標(biāo)節(jié)點(diǎn)Nq在升序排列后的節(jié)點(diǎn)列表中的位置記作α，例如在節(jié)點(diǎn)組合{N1，N2，N3}中，節(jié)點(diǎn)N1對(duì)應(yīng)的位置α=0，節(jié)點(diǎn)N3對(duì)應(yīng)的位置α=2。獲取位置信息αi并將其添加至組合結(jié)果拆分位置信息，同時(shí)將該塊編號(hào)信息d添加至塊編號(hào)信息。對(duì)應(yīng)每個(gè)樣本塊都可獲取一個(gè)該節(jié)點(diǎn)在該樣本塊分發(fā)列表中的位置αi，那么可以由上述數(shù)據(jù)求得，如式（12）所示。遍歷編碼所用的編碼梯度矩陣G(i，l，j，?q)求解Ai，如式（13）所示。疊加所有的Ai并獲取其中僅出現(xiàn)一次的節(jié)點(diǎn)，將其添加至編碼包的發(fā)送目標(biāo)列表。

2.3 解碼過程

根據(jù)編碼時(shí)的累加結(jié)果和分片規(guī)則，解碼時(shí)應(yīng)按照編碼時(shí)的運(yùn)算過程反向求取節(jié)點(diǎn)所需的內(nèi)容。首先通過減法減去節(jié)點(diǎn)已知的數(shù)據(jù)內(nèi)容，求取未知的數(shù)據(jù)內(nèi)容，然后按照分片規(guī)則，還原中間結(jié)果矩陣，以獲取完整的中間結(jié)果。數(shù)據(jù)傳輸解碼算法的偽代碼如算法4 所示，主要功能為在給定所有中間結(jié)果矩陣列表B和接收到的編碼數(shù)據(jù)包H的情況下輸出矩陣切片（content）、切片編號(hào)（parts_id）和切片位置（parts_ position），其中，can_get(B，id) 判斷節(jié)點(diǎn)是否包含樣本塊編號(hào)為id 所計(jì)算出的梯度矩陣，part_of(B，id，pos) 獲取對(duì)應(yīng)編號(hào)id 的樣本塊計(jì)算出的梯度矩陣的第pos 個(gè)拆分子矩陣。

算法4數(shù)據(jù)傳輸解碼算法

在編碼包中已包含編碼所用樣本塊編號(hào)和編碼拆分矩陣的位置信息，依據(jù)發(fā)送規(guī)則可從編碼包中提取節(jié)點(diǎn)Ni缺失的信息，將發(fā)送編碼包給節(jié)點(diǎn)Ni的節(jié)點(diǎn)記作Ni，，將節(jié)點(diǎn)Ni，發(fā)送返回的信息記作。由于編碼包中已包含樣本塊和拆分子矩陣位置信息，因此可利用節(jié)點(diǎn)Ni已有的信息解碼未知信息，如式（15）所示。根據(jù)任務(wù)分配算法，將節(jié)點(diǎn)Ni缺失的樣本塊記作-μ，對(duì)應(yīng)這些缺失樣本所需的梯度中間結(jié)果記作G(i，l，j，qv)，v=1，2，…，-μ。當(dāng)節(jié)點(diǎn)Nq獲取到所有缺失信息后，將其依照拆分規(guī)則進(jìn)行合并，如式（16）所示。當(dāng)節(jié)點(diǎn)Nq獲取到所有樣本塊對(duì)應(yīng)的缺失梯度時(shí)，使用式（16）和式（17）計(jì)算全局梯度，該全局梯度即進(jìn)一步迭代所需的模型參數(shù)增量，如式（18）所示。

2.4 通信負(fù)載計(jì)算

若假設(shè)本文同步隨機(jī)梯度下降算法的通信負(fù)載為L(zhǎng)coding，傳統(tǒng)不使用多播技術(shù)的梯度下降算法的通信負(fù)載為L(zhǎng)normal，則兩者存在式（19）所述的關(guān)系：

對(duì)上述關(guān)系進(jìn)行證明，具體證明過程如下：使用編碼策略進(jìn)行任務(wù)分發(fā)和交換，節(jié)點(diǎn)數(shù)目為n，數(shù)據(jù)分配冗余度為r，每個(gè)劃分占總批次大小為a1，a2，…，ap，其中p=，每個(gè)節(jié)點(diǎn)獲取a1，a2，…，ap中的Dhave個(gè)樣本塊（如式（20）所示），并缺少其中的Dleft個(gè)樣本塊（如式（21）所示）。將節(jié)點(diǎn)i包含的所有樣本塊集合記作Di，如式（22）所示。

對(duì)于n個(gè)節(jié)點(diǎn)中任意r個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)子集，其中一定存在1 個(gè)樣本塊被這r個(gè)節(jié)點(diǎn)所共有，因?yàn)闃颖緣K分發(fā)標(biāo)簽包含了所有節(jié)點(diǎn)編號(hào)可以形成的組合，所以任意r個(gè)節(jié)點(diǎn)必然屬于種選擇中的一個(gè)節(jié)點(diǎn)，如式（23）所示。同理，對(duì)于任意r+1 個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)組至少存在個(gè)這樣的樣本塊，如式（24）所示。在n個(gè)節(jié)點(diǎn)組成的集群中共有個(gè)節(jié)點(diǎn)組，每個(gè)節(jié)點(diǎn)組選取其中個(gè)樣本塊Dexchange進(jìn)行數(shù)據(jù)交換，每個(gè)節(jié)點(diǎn)僅發(fā)送由樣本塊Dsend計(jì)算所得的數(shù)據(jù)，如式（25）、式（26）所示。

由于節(jié)點(diǎn)Ni完成所有分組交換后數(shù)據(jù)都不重復(fù)，因此其能夠獲得所有的Dleft中間信息，使用個(gè)節(jié)點(diǎn)組進(jìn)行完全分組信息交換后，總的多播通信量如式（28）所示。對(duì)于具有同樣冗余度的傳統(tǒng)通信方式，每個(gè)節(jié)點(diǎn)所需通信量如式（29）所示，本文中的冗余度是指在同一樣本塊上進(jìn)行計(jì)算的節(jié)點(diǎn)數(shù)量。對(duì)于不使用冗余策略的普通通信方式，每個(gè)節(jié)點(diǎn)缺少的數(shù)據(jù)是相互獨(dú)立的，所需的通信量如式（30）所示。綜上，式（19）所述的編碼策略通信負(fù)載與傳統(tǒng)方法通信負(fù)載之間的關(guān)系得以證明。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)方法

本文通過神經(jīng)網(wǎng)絡(luò)對(duì)SSGD、ASGD和本文CSSGD算法進(jìn)行分布式訓(xùn)練實(shí)驗(yàn)，對(duì)比在不同節(jié)點(diǎn)數(shù)目的情況下3 種算法到達(dá)指定訓(xùn)練精確度所需物理時(shí)鐘時(shí)間和數(shù)據(jù)傳輸量，并利用集群模擬對(duì)上述指標(biāo)進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)中共使用10 個(gè)計(jì)算節(jié)點(diǎn)，每個(gè)計(jì)算節(jié)點(diǎn)的配置信息如表1 所示。本文使用MNIST 和CIFAR-10數(shù)據(jù)集在卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）和DNN 上進(jìn)行實(shí)驗(yàn)。表2 給出CNN 和DNN 在不限時(shí)單機(jī)執(zhí)行環(huán)境下所得的測(cè)試精確度，以此測(cè)試精確度作為最優(yōu)測(cè)試精確度，并在實(shí)驗(yàn)中對(duì)比3 種算法的測(cè)試精確度。

表1 計(jì)算節(jié)點(diǎn)配置信息Table 1 Configuration information of computing node

表2 實(shí)驗(yàn)數(shù)據(jù)集上的測(cè)試精確度Table 2 Test accuracy on the experimental dataset

為保證浮點(diǎn)數(shù)執(zhí)行編碼運(yùn)算后的精確度，本文對(duì)計(jì)算產(chǎn)生的中間結(jié)果進(jìn)行量化，使用32 位整型保存運(yùn)算所需的浮點(diǎn)數(shù)據(jù)，設(shè)置中間結(jié)果區(qū)間為［-10，10］，取0x7FFFFFFF 為10，取0x80000001 為-10，等區(qū)間劃分取值，并使用該量化結(jié)果進(jìn)行運(yùn)算和編碼。本文在實(shí)驗(yàn)中對(duì)不同節(jié)點(diǎn)的網(wǎng)絡(luò)使用不同的樣本劃分，在2 個(gè)節(jié)點(diǎn)上只執(zhí)行二分類，在3 個(gè)節(jié)點(diǎn)上只執(zhí)行三分類任務(wù)，以此類推，保證每次測(cè)試時(shí)每個(gè)節(jié)點(diǎn)都能夠執(zhí)行相同數(shù)據(jù)量的任務(wù)，分析由通信瓶頸導(dǎo)致的性能損失問題，同時(shí)以串行算法測(cè)試所得結(jié)果作為目標(biāo)精確度。

3.2 實(shí)驗(yàn)結(jié)果

本文首先對(duì)CSSGD 算法在DNN 與CNN 上的訓(xùn)練結(jié)果進(jìn)行評(píng)估，然后使用SSGD、ASGD 和CSSGD 算法在MNIST 數(shù)據(jù)集上訓(xùn)練DNN、在CIFAR-10 數(shù)據(jù)集上訓(xùn)練CNN。在訓(xùn)練過程中，使用10 個(gè)訓(xùn)練節(jié)點(diǎn)（ASGD 算法額外使用一個(gè)參數(shù)服務(wù)器）并記錄測(cè)試精確度的變化情況。由于CSSGD 算法的目的是減少訓(xùn)練執(zhí)行時(shí)間，因此實(shí)驗(yàn)著重討論3 種算法到達(dá)相同測(cè)試精確度的時(shí)間。

3.2.1 訓(xùn)練性能分析

DNN 和CNN 的訓(xùn)練結(jié)果如圖4 和圖5 所示，可以看出CSSGD、SSGD 和ASGD 算法在充足的訓(xùn)練時(shí)間下，均可達(dá)到最終的測(cè)試精確度。

圖4 利用CSSGD、SSGD 和ASGD 算法訓(xùn)練DNN 的測(cè)試精確度比較Fig.4 Comparison of test accuracy of training DNN with CSSGD，SSGD and ASGD algorithms

圖5 利用CSSGD、SSGD 和ASGD 算法訓(xùn)練CNN 的測(cè)試精確度比較Fig.5 Comparison of test accuracy of training CNN with CSSGD，SSGD and ASGD algorithms

本節(jié)實(shí)驗(yàn)著重分析3 種算法訓(xùn)練所需的時(shí)間，在限定的測(cè)試精確度下比較算法執(zhí)行所需的時(shí)間以評(píng)估算法執(zhí)行效率。實(shí)驗(yàn)在CNN 和DNN 的原始訓(xùn)練結(jié)果中，在接近目標(biāo)精確度附近選取一個(gè)相對(duì)3 種算法差異最大的基準(zhǔn)測(cè)試精確度進(jìn)行后續(xù)實(shí)驗(yàn)。如圖6、圖7 所示，對(duì)于使用MNIST 數(shù)據(jù)集的DNN，其選取的基準(zhǔn)測(cè)試精確度為82%，對(duì)于使用CIFAR-10 數(shù)據(jù)集的CNN，其選取的基準(zhǔn)測(cè)試精確度為70%。下文將針對(duì)這組基準(zhǔn)測(cè)試精確度，比較3 種算法的執(zhí)行效率。

圖6 DNN 訓(xùn)練中的基準(zhǔn)測(cè)試精確度Fig.6 Benchmark test accuracy of DNN training

圖7 CNN 訓(xùn)練中的基準(zhǔn)測(cè)試精確度Fig.7 Benchmark test accuracy of CNN training

后續(xù)實(shí)驗(yàn)從3 個(gè)方面詳細(xì)分析了CSSGD 算法的執(zhí)行效率：1）由于ASGD 算法無(wú)獨(dú)占通信時(shí)間，因此在DNN 和CNN 訓(xùn)練過程中，對(duì)比使用CSSGD 與SSGD 算法在訓(xùn)練時(shí)間和通信總量上的差別；2）針對(duì)理論推導(dǎo)結(jié)果，通過實(shí)驗(yàn)驗(yàn)證不同冗余度設(shè)置下CSSGD 算法的每批次訓(xùn)練時(shí)間；3）使用相同的樣本數(shù)據(jù)集和神經(jīng)網(wǎng)絡(luò)在上述集群環(huán)境下，對(duì)比ASGD、SSGD 和CSSGD 算法訓(xùn)練至基準(zhǔn)測(cè)試精確度所需的訓(xùn)練時(shí)間。

3.2.2 DNN 實(shí)驗(yàn)結(jié)果分析

圖8 展示了DNN 訓(xùn)練中SSGD 和CSSGD 算法在MNIST 數(shù)據(jù)集上達(dá)到82%測(cè)試精確度所需的時(shí)間，其中，SSGD Multicast 和SSGD Unicast 分別表示基于多播技術(shù)的SSGD 算法和基于單播技術(shù)的SSGD 算法，CSSGDr=2 和CSSGDr=3 分別表示冗余度為2 的CSSGD 算法和冗余度為3 的CSSGD 算法，可以看出CSSGD 算法能夠有效降低SSGD 算法執(zhí)行所需時(shí)間。圖9 展示了DNN 訓(xùn)練中SSGD Multicast 和CSSGD 算法占用的網(wǎng)絡(luò)數(shù)據(jù)通信總量，可以看出CSSGD 算法占用的網(wǎng)絡(luò)數(shù)據(jù)通信總量相對(duì)SSGD 算法更少。

圖8 在DNN 訓(xùn)練中SSGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需時(shí)間Fig.8 The time required for SSGD and CSSGD algorithms to reach benchmark test accuracy in DNN training

圖9 在DNN 訓(xùn)練中SSGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需通信總量Fig.9 The total amount of communication required for SSGD and CSSGD algorithms to reach benchmark test accuracy in DNN training

3.2.3 CNN 實(shí)驗(yàn)結(jié)果分析

圖10 展示了CNN 訓(xùn)練中SSGD 與CSSGD 算法在CIFAR-10 數(shù)據(jù)集上達(dá)到70%測(cè)試精確度所需的時(shí)間。在DNN 訓(xùn)練過程中產(chǎn)生的權(quán)值矩陣相對(duì)CNN 更大，容易由于網(wǎng)絡(luò)速度限制造成計(jì)算瓶頸，如果對(duì)該類別網(wǎng)絡(luò)使用CSSGD 算法，則可以有效緩解通信瓶頸問題。在CNN 中執(zhí)行計(jì)算所需時(shí)間比DNN 更多，因此其對(duì)通信瓶頸的影響相對(duì)DNN 更小，在使用CSSGD 算法進(jìn)行編碼梯度下降時(shí)，其所能獲得的測(cè)試精確度相對(duì)DNN 更低。圖11 展示了CNN 訓(xùn)練中SSGD Multicast 和CSSGD 算法占用的網(wǎng)絡(luò)數(shù)據(jù)通信總量，可以看出CSSGD 算法在CNN和DNN 訓(xùn)練中都能夠有效降低中間結(jié)果的通信總量，但是CNN 計(jì)算中數(shù)據(jù)通信所占時(shí)間相較DNN更少，因此數(shù)據(jù)通信優(yōu)化對(duì)總體執(zhí)行性能的影響較小。

圖10 在CNN 訓(xùn)練中SSGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需時(shí)間Fig.10 The time required for SSGD and CSSGD algorithms to reach benchmark test accuracy in CNN training

圖11 在CNN 訓(xùn)練中SSGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需通信總量Fig.11 The total amount of communication required for SSGD and CSSGD algorithms to reach benchmark test accuracy in CNN training

3.2.4 冗余度分析

根據(jù)上文對(duì)編碼過程的理論推導(dǎo)可以得出，當(dāng)所需通信時(shí)間與數(shù)據(jù)通信總量呈線性相關(guān)時(shí)，CSSGD 算法單一批次訓(xùn)練所需時(shí)間TCSSGD可表示為每批次計(jì)算時(shí)間和每批次通信時(shí)間之和，假設(shè)SSGD 多播算法中一個(gè)批次計(jì)算所需時(shí)間為Tcalculate、中間結(jié)果傳輸所需時(shí)間為Tcommunicate，則TCSSGD可表示為TCSSGD=r·Tcalculate+1/r·Tcommunicate，可以看出，當(dāng)Tcalculate和Tcommunicate為定值時(shí)存在一個(gè)確定的冗余度使得TCSSGD最小。本文在8 個(gè)計(jì)算節(jié)點(diǎn)的情況下對(duì)不同冗余度的CSSGD 算法單一批次迭代所需時(shí)間進(jìn)行實(shí)驗(yàn)，結(jié)果如圖12、圖13 所示，可以看出在DNN 和CNN 訓(xùn)練中的最佳冗余度分別為3 和2。由實(shí)驗(yàn)結(jié)果可以得出和理論推導(dǎo)相同的結(jié)論，即在固定的計(jì)算時(shí)間和傳輸時(shí)間下，每個(gè)節(jié)點(diǎn)都存在確定的冗余度，當(dāng)冗余度為r時(shí)整個(gè)分布式集群?jiǎn)我慌蔚挠?xùn)練時(shí)間最短。

圖12 在DNN 訓(xùn)練中CSSGD 算法冗余度與單一批次訓(xùn)練時(shí)間的關(guān)系Fig.12 The relationship between the redundancy and the training time of single batch of CSSGD algorithm in DNN training

圖13 在CNN 訓(xùn)練中CSSGD 算法冗余度與單一批次訓(xùn)練時(shí)間的關(guān)系Fig.13 The relationship between the redundancy and the training time of single batch of CSSGD algorithm in CNN training

3.2.5 訓(xùn)練時(shí)間分析

本節(jié)對(duì)比ASGD、SSGD Multicast和最優(yōu)冗余度下的CSSGD（CSSGD Optimal）算法的實(shí)際訓(xùn)練時(shí)間，如圖14 和圖15 所示，由于ASGD 算法異步執(zhí)行過程導(dǎo)致其執(zhí)行狀態(tài)難以確定，最終收斂所需次數(shù)也存在一定的隨機(jī)性，因此對(duì)ASGD 算法進(jìn)行10 次實(shí)驗(yàn)取訓(xùn)練時(shí)間的平均值?？梢钥闯觯谕ㄐ牌款i問題較嚴(yán)重的DNN訓(xùn)練過程中，CSSGD 算法相對(duì)于SSGD 和ASGD 算法可取得明顯的效率提升，在DNN 的分布式訓(xùn)練中，相對(duì)SSGD 和ASGD 平均能減少53.97%和26.89%的訓(xùn)練時(shí)間。在CNN 訓(xùn)練過程中由于計(jì)算執(zhí)行過程占總執(zhí)行時(shí)間的比例較高，因此通過添加冗余編碼來降低通信負(fù)載的CSSGD 算法效率提升較少，但是ASGD 算法需要更多的計(jì)算開銷來消除梯度延遲問題帶來的干擾，因此CSSGD 算法相對(duì)SSGD 和ASGD 算法效率依然有一定的提升，在CNN 分布式訓(xùn)練中，相對(duì)SSGD 和ASGD 平均能減少39.11%和26.37%的訓(xùn)練時(shí)間。實(shí)驗(yàn)中給出10 個(gè)計(jì)算節(jié)點(diǎn)以內(nèi)的訓(xùn)練時(shí)間結(jié)果，可以看出，ASGD 和CSSGD 算法在分布式系統(tǒng)上的性能不能隨節(jié)點(diǎn)數(shù)目線性提升，隨著節(jié)點(diǎn)數(shù)目的增多，ASGD 算法的理論同步更新概率會(huì)越來越小，迭代所需時(shí)間會(huì)繼續(xù)增加，CSSGD 算法也會(huì)受到額外通信負(fù)載和多播帶寬擁塞的影響，但是其在更多節(jié)點(diǎn)加入后可更新其最優(yōu)冗余度參數(shù)配置，能夠達(dá)到更好的訓(xùn)練效果。

圖14 在DNN 訓(xùn)練中SSGD、ASGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需時(shí)間Fig.14 The time required for SSGD，ASGD and CSSGD algorithms to reach benchmark test accuracy in DNN training

圖15 在CNN 訓(xùn)練中SSGD、ASGD 和CSSGD 算法達(dá)到基準(zhǔn)測(cè)試精確度所需時(shí)間Fig.15 The time required for SSGD，ASGD and CSSGD algorithms to reach benchmark test accuracy in CNN training

4 結(jié)束語(yǔ)

本文針對(duì)異步隨機(jī)梯度下降算法的高通信負(fù)載問題，提出一種基于分布式編碼計(jì)算的同步梯度下降算法，通過冗余分發(fā)策略降低通信負(fù)載并消除通信瓶頸對(duì)分布式集群的影響。實(shí)驗(yàn)結(jié)果表明，當(dāng)配置合適的超參數(shù)時(shí)，與SSGD 和ASGD 算法相比，該算法在DNN分布式訓(xùn)練中能平均減少53.97%和26.89%的訓(xùn)練時(shí)間，在CNN 分布式訓(xùn)練中能平均減少39.11%和26.37%的訓(xùn)練時(shí)間，降低了分布式集群上的通信負(fù)載。下一步將研究并行梯度下降算法在分布式集群上的應(yīng)用，并分析數(shù)值量化誤差對(duì)最終損失函數(shù)收斂性能的影響。