基于Gossip的異步分布式訓練算法

周嘉 涂軍 任冬淋

[摘 要]因此基于Gossip協(xié)議并結合SGD（Stochastic Gradient Descent）提出了一種用于深度學習的通信框架GR-SGD（Gossip Ring SGD），該通信框架是非中心化且異步的，解決了通信等待時間較長的問題。實驗使用ImageNet數(shù)據(jù)集，ResNet模型驗證了該算法的可行并與Ring AllReduce和D-PSGD（Decentralized parallel SGD）進行了比較，GR-SGD在更短的時間內完成了訓練。

[關鍵詞]非中心化分布式；Gossip；異步

[中圖分類號]TP399[文獻標識碼]A

近年以來，人工智能（AI）在各種科學和工程中得到了越來越多的應用。在使用機器學習（ML）和深度學習（DL）技術處理和訓練各行業(yè)巨大數(shù)據(jù)的時候，更大更深的模型有助于進一步提高效率以及準確性。因此，使用分布式模型來處理數(shù)據(jù)以及提供訓練必要的計算資源也變得越來越普遍^[1]。

已有的分布式深度學習算法分為中心化分布式算法和非中心化分布式算法。現(xiàn)常用的中心化分布式通信框架是參數(shù)服務器（Parameter Server，PS）^[2-4]。當今主流研究是在PS框架基礎上的改進，如：TensorFlow^[5]、CNTK^[6]、MXNet^[7]。PS框架最大的問題就是中心節(jié)點上的通信瓶頸以及安全問題。因此，非中心化算法成為了一種研究趨勢。比較典型的就是由百度硅谷人工智能實驗室（SVAIL）提出的Ring AllReduce算法，目前，Ring AllReduce算法被應用在Uber開發(fā)的Horovod^[8]中。雖然該算法解決了PS框架中心節(jié)點通信瓶頸的問題，且在大規(guī)模GPU集群中的性能高于PS框架^[9]。但由于Ring AllReduce是一個同步的算法，所以當集群中有某一個節(jié)點速度很慢，甚至宕機時，會導致集群內其它節(jié)點無法繼續(xù)工作。

對此，本文基于Gossip協(xié)議并結合SGD（Stochastic Gradient Descent）提出了一種用于深度學習的通信框架GR-SGD（Gossip Ring SGD）。并通過實驗與Ring AllReduce算法、D-PSGD（Decentralized parallel SGD）算法進行了比較。

1 相關技術介紹

1.1 Gossip協(xié)議

Gossip是目前非中心化深度學習模型訓練^[10-14]的主要算法之一。該算法最初是為分布式平均問題^[15-16]開發(fā)的，它迭代地計算對等網(wǎng)絡拓撲中所有的多個節(jié)點的平均向量。例如，典型的GoSGD算法^[12-13]的過程在一個訓練epoch中包含三個步驟。首先，對于每個參與者和每次迭代，算法使用參與者的本地輸入數(shù)據(jù)和模型計算梯度，并使用梯度更新參數(shù)。這一步通常采用mini-batch梯度下降法。其次，節(jié)點根據(jù)矩陣向其它參與者發(fā)送權重。最后，節(jié)點從其它參與者那里接收權重，并將它們與本地權重合并以更新模型。此外，Liu ^[17]還為D-PSGD^[18]算法提供了另一種復雜度范圍，它可以改善光譜間隙。

Gossip在DL中的工作流程如算法1的偽代碼所示。首先，每個節(jié)點初始化本地的模型；然后，模型參數(shù)的子集定期發(fā)送到網(wǎng)絡中的另一個節(jié)點。當每個節(jié)點接收到這樣的參數(shù)樣本時，它將其合并到自己的模型中，然后執(zhí)行一個本地更新步驟。盡管所有節(jié)點的周期Δ相同，但節(jié)點通信的輪次是不同步的。任何收到的消息都會立即處理。

算法1 Gossip 在深度學習中的工作流程

1：Initialize the local model （x）

2：loop

3：wait（Δ）

4：p ← Random selectPeer（）

5：send sample（x） to p

6：end loop

7：

8：procedure ONRECEIVEMODEL（r）

9：（x）←merge（（x），（r））

10： （x）←update（（x），D）

11：end procedure

1.2 平均共識

平均共識問題是使得網(wǎng)絡中所有節(jié)點達到初始狀態(tài)均值的一致狀態(tài)，它可以被廣泛的用于參數(shù)估計、定位、同步等方面。按照傳統(tǒng)的方法將網(wǎng)絡中的數(shù)據(jù)直接匯聚到某個節(jié)點中，將產(chǎn)生大量的通信開銷并造成通信瓶頸。而Gossip利用節(jié)點的本地信息處理能力，僅通過隨機喚醒網(wǎng)絡中的節(jié)點并與鄰居節(jié)點進行數(shù)據(jù)交換的方式使網(wǎng)絡達到平均共識狀態(tài)，從而避免了網(wǎng)絡中多余的通信開銷和瓶頸效應。簡單來說，Gossip算法在平均共識的問題上是線性收斂的。平均共識問題包括找到n個局部向量的平均向量，從形式上定義為下面公式：

對于具有壓縮通信的共識算法^[19]，被指出并不能收斂到正確的解^[20]，只能收斂到解的鄰域（其大小取決于壓縮精度）。自適應^[21]的方法都需要完全（非壓縮）通信才能達到較高的精度。而最近Anastasia^[22]等人基于Gossip協(xié)議提出了新的壓縮通信的方法，能夠實現(xiàn)線性的收斂。此外Ye^[23]等人還提出了多共識非中心化加速梯度下降的方法。

在Gossip協(xié)議中，針對平均共識問題通常有公式

其中γ是范圍（0，1]的步長參數(shù)，x_ij是[0，1]的平均權重值，Δ^（t）_ij∈ ?^d表示在迭代t的時候節(jié)點j發(fā)送到節(jié)點i的向量。其收斂速度取決于八卦矩陣（X）_ij=x_ij，其中矩陣X∈?^n×n。

1.3 系統(tǒng)設計

目的是設計一種異步的非中心化分布式通信框架并應用到深度學習訓練中。該框架使用Gossip通信協(xié)議而不是MPI。在框架中每個節(jié)點都能進行異步的通信，即使其中某一個或者某幾個節(jié)點出現(xiàn)宕機或者變慢時，整個系統(tǒng)無需等待阻塞節(jié)點。沒有中心節(jié)點意味著每個Worker都被期望收斂到相同的值，Worker之間達成嚴格的共識。中心節(jié)點的缺失可以通過通信矩陣的第一行和第一列為0表示出來，通信都以對等方式執(zhí)行^[15]。通信矩陣中，列是發(fā)送方，行是接收方。

通信框架中，使用Gossip協(xié)議，Worker不用等待其它Worker的消息也可進行計算的工作。非對稱的Gossip協(xié)議^[24]能轉化為通信矩陣X^（t）系數(shù)非零的約束，因此沒有Worker同時發(fā)送和接受消息。為了保證算法收斂到共識，權重w^（t）_m需要與每個變量x^（t）_m相關并由Workers使用相同的通信方式所共享。當Worker完成本地更新后，被喚醒時會向其它隨機Worker發(fā)送數(shù)據(jù)，依次循環(huán)。雖然在同一時間每個節(jié)點的數(shù)據(jù)不同或梯度不同，但最終所有節(jié)點都會趨于一致。

以4個節(jié)點為例，這里設定每個Worker在每次迭代中只發(fā)送和接收1條消息。如圖1所示，在整個系統(tǒng)中每個時間步長t內只有一個節(jié)點被喚醒。當節(jié)點0被喚醒時，它隨機向其它1個節(jié)點發(fā)送消息，接收到消息的節(jié)點會在本地更新數(shù)據(jù)，依次循環(huán)直至訓練完成。在一次迭代中，每個節(jié)點會發(fā)送1條消息，并接收1條消息，所以在這個網(wǎng)絡中通信負載是平衡的。為了保證每個節(jié)點在每次迭代中不重復發(fā)送和接收消息，本文引入了混合矩陣M^（t）。此混合矩陣是列隨機的 （列的和為1），每個節(jié)點i都可以選擇它的混合權重（矩陣M^（t）的第i列），因此獨立于網(wǎng)絡中的其它節(jié)點。在圖1網(wǎng)絡拓撲中，每個節(jié)點只隨機向其它一個節(jié)點發(fā)送消息，即得到下面矩陣

這里h_t表示在時間步長t內節(jié)點鄰居間的距離。

1.4 收斂性分析

GR-SGD的收斂性分析基于下面2個假設。

假設1 有界方差。存在2個常數(shù)C₁和C₂，使得

其中i∈[n]。其中C₁代表了每個節(jié)點上的隨機梯度方差，C₂代表不同節(jié)點上的數(shù)據(jù)分布。

假設2 f（x）是L-smooth，有

‖?F（x）- ?Fy‖≤L‖x-y‖其中L>0，F(xiàn)（x）是可微的。

即收斂性得到了證明。

2 實驗

實驗使用華中科技大學的高性能服務平臺，在實驗的集群中包含16張tesla V100s GPU，每個GPU作為一個節(jié)點。實驗使用ImageNet數(shù)據(jù)集以及ResNet50^[25]作為訓練模型。每個節(jié)點使用256的mini-batch大小。實驗將Ring AllReduce，D-PSGD和GR-SGD進行對比，在GR-SGD算法中，由混合矩陣控制每個節(jié)點在每次迭代中只發(fā)送并接收一條消息。對比實驗中，將主要體現(xiàn)GR-SGD異步通信算法的優(yōu)勢。

圖2給出了GR-SGD、 Ring AllReduce和D-PSGD在4、8、12和16個節(jié)點的時間方向的訓練收斂。在訓練的速度上GR-SGD是明顯優(yōu)于D-PSGD和Ring AllReduce的。可以看到，隨著節(jié)點數(shù)的增加GR-SGD比Ring AllReduce和D-PSGD在更短的時間內完成160個epoch。隨著節(jié)點數(shù)量的增加，GR-SGD和D-PSGD平均迭代時間幾乎保持不變，而Ring AllReduce的每次迭代時間明顯增加，導致整體訓練時間變慢。通過本文實驗結果可以推斷，當GPU數(shù)量不斷增大時，GR-SGD的優(yōu)勢會越來越明顯。

接下來，為了模擬集群不穩(wěn)定的情形，在實驗時讓每個Worker有1/16的概率變慢，這樣集群中會產(chǎn)生慢節(jié)點和快節(jié)點。如圖3所示，其中RA1和GR-SGD1代表有節(jié)點變慢，當有Worker變慢時，對Ring AllReduce會有比較明顯的影響，而對GR-SGD幾乎沒有影響。很顯然這證明了在集群中，使用異步的通信方法能有效增加系統(tǒng)的效率。

3 結論及展望

本文在非中心化分布式深度學習的基礎上，參考了現(xiàn)有的Ring AllReduce算法，通過使用Gossip協(xié)議以及引入混合矩陣，提出了GR-SGD算法。該算法通過混合矩陣控制節(jié)點的通信次數(shù)，能實現(xiàn)異步，解決了Ring AllReduce算法會因節(jié)點變慢而導致通信等待問題。通過實驗，驗證并推斷了在節(jié)點數(shù)量龐大的集群中，GR-SGD算法在速度上會優(yōu)于Ring AllReduce和D-PSGD。在下一步的工作中，將考慮通過混合矩陣增加通信的次數(shù)，來達到加快模型收斂，增加訓練精度，并為系統(tǒng)帶來容錯的目的。

致謝：本文的計算工作得到了華中科技大學網(wǎng)絡與計算中心提供的高性能計算公共服務平臺支持。

[ 參 考 文 獻 ]

[1] CHANDRASEKARAN V， RECHT B， PARRILO P A， et al. The convex geometry of linear inverse problem [J]. Foundations of Computational Mathematics 2012，12：805-849.

[2] LI M， ANDERSEN D G， PARK J W， et al. Scaling distributed machine learning with the parameter server[C].∥11th {USENIX} Symposium on Operating Systems Design and Implementation 2014，（{OSDI} 14）：583-598.

[3] LI M， ANDERSEN D G， SMOLA A J， et al. Communication efficient distributed machine learning with the parameter server[J]. Advances in Neural Information Processing Systems， 2014，27： 19-27.

[4] XING E P， HO Q， DAI W， et al. Petuum： A new platform for distributed machine learning on big data[J]. IEEE Transactions on Big Data， 2015，1（2）： 49-67.

[5] MARTN ABADI， PAUL BARHAM， JIANMIN CHEN，et al. Tensorflow： a system for large-scale machine learning[C]. In Proceedings of USENIX Symposium on Operating Systems Design and Implementation （OSDI），2016，265-283.

[6] Seide F， Agarwal A. CNTK： Microsoft's open-source deep-learning toolkit[C].∥Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2016： 2135-2135.

[7] TIANQI CHEN， MU LI， YUTIAN LI， et al. MXNet： A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems[C]. In Proceedings of NIPS Workshop on Machine Learning Systems， 2016.

[8] ALEXANDER SERGEEV， MIKE DEL BALSO. Horovod： fast and easy distributed deep learning in TensorFlow[EB/OL]. 2018， https：∥arxiv.org/abs/1802.05799v3.

[9] ZHANG Lizhi， RAN Zhejiang， LAI Zhi-quan， et al. Performance analysis of distributed deep learning communication architecture[C]. In Computer Engineer & Science，2020.

[10]Oguni H， Shudo K. Communication scheduling for gossip sgd in a wide area network[J]. IEEE Access， 2021.

[11]HAN R， LI S， WANG X， et al. Accelerating gossip-based deep learning in heterogeneous edge computing platforms[J]. IEEE Transactions on Parallel and Distributed Systems， 2020， 32（07）： 1591-1602.

[12]BLOT M， PICARD D， THOME N，et al. Cord， Distributed optimization for deep learning with gossip exchange[J]， Neurocomputing， 2019，330： 287-296.

[13]BLOT M， PICARD D， CORD M，et al. Thome， Gossip training for deep learning[EB/OL]. （2021-01-02）.[2016-11-29].https：∥arxiv.org/abs/1611.09726.

[14]LU Y ， SA C D . Optimal Complexity in Decentralized Training[C].∥ International Conference on Machine Learning. PMLR， 2021. [15]S. Boyd， A. Ghosh， B. Prabhakar， and D. Shah， Randomized gossip algorithms[J]， IEEE Trans. Inf. Theory， 2006， 2508–2530.

[16]I COLIN， A BELLET， J SALMON， et al. Gossip dual averaging for decentralized optimization of pairwise functions[C]. in Proc. 33rd Int. Conf. Int. Conf. Mach. Learn.， 2016，1388-1396.

[17] LIUIU JI， CE ZHANG HANGCE. Distributed learning systems with first-order methods[EB/OL]. （2021-01-02）.[2021-04-21]. https：//arxiv.org/abs/2104.05245.

[18]LIAN X， ZHANG C， ZHANG H， et al. Can decentralized algorithms outperform centralized algorithms？ a case study for decentralized parallel stochastic gradient descent[C]. In Advances in Neural Information Processing Systems， 2017，5330-5340.

[19]YUAN D， XU S， ZHAO H， et al. Distributed dual averaging method for multi-agent optimization with quantized communication[J]. Systems & Control Letters， 2012， 61（11）：1053-1061.

[20]XIAO L， BOYD S，LALLa S. A scheme for robust distributed sensor fusion based on average consensus[C]. In IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks， 2005， 63-70.

[21]THANOU D， KOKIOPOULOU E， PU Y， et al. Distributed average consensus with quantization refinement[J]. IEEE Transactions on Signal Processing， 2013，61（1）：194–205.

[22]KOLOSKOVA A， STICH S U， JAGGI M. Decentralized stochastic optimization and gossip algorithms with compressed communication：， 10.48550/arXiv.1902.00340[P]. 2019.

[23]HAISHAN Y E， LUO LUO， ZIANG ZHOU， AND TONG ZHANG. Multi-consensus decentralized accelerated gradient descent[EB/OL]. （2020）. https：∥arxiv.org/abs/2005.00797.

[24]KEMPE D， DOBRA A， GEHRKE J. Gossip-based computation of aggregate information[C].In： Proceedings of the Forty-Fourth Annual IEEE Symposium on Foundations of Computer Science，IEEE， 2003， 482-491.

[25]HE K， ZHANG X， REN S， et al. Deep residual learning for image recognition[C]. In Proceedings of the IEEE conference on computer vision and pattern recognition，2016， 770-778.

Asynchronous Distributed Training Algorithm based on Gossip

ZHOU Jia， TU Jun， REN Donglin

（School of Computer Science， Hubei Univ. of Tech.， Wuhan 430068， China）

Abstract：Ring AllReduce algorithm， one of the existing decentralized distributed clusters， can reduce the bottleneck of the central node communication. However， the communication algorithm is synchronous， which will lead to longer communication waiting time inter-node in the cluster. Combined the Gossip protocol with Stochastic Gradient Descent （SGD）， this paper proposes a communication framework Gossip Ring SGD （GR-SGD） for deep learning. GR-SGD is decentralized and asynchronous， and solves the problem of long communication waiting time. This paper uses the ImageNet data set and the ResNet model to verify the feasibility of GR-SGD and compares it with Ring AllReduce and D-PSGD， and it turns out that GR-SGD finishes the training in shorter time.

Keywords：distributed Decentralization; Gossip; asynchronous

[責任編校：張巖芳]