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

周嘉 涂軍 任冬淋

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

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

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

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

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

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

1 相關技術介紹

1.1 Gossip協議

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

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

算法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 平均共識

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

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

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

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

1.3 系統設計

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

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

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

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

1.4 收斂性分析

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

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

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

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

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

即收斂性得到了證明。

2 實驗

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

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

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

3 結論及展望

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

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

[ 參 考 文 獻 ]

[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

[責任編校：張巖芳]