周嘉 涂軍 任冬淋

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

[關(guān)鍵詞]非中心化分布式；Gossip；異步

[中圖分類號]TP399[文獻(xiàn)標(biāo)識碼]A

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

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

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

1 相關(guān)技術(shù)介紹

1.1 Gossip協(xié)議

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

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

算法1 Gossip 在深度學(xué)習(xí)中的工作流程

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

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

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

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

1.3 系統(tǒng)設(shè)計(jì)

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

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

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

這里h_t表示在時(shí)間步長t內(nèi)節(jié)點(diǎn)鄰居間的距離。

1.4 收斂性分析

GR-SGD的收斂性分析基于下面2個(gè)假設(shè)。

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

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

假設(shè)2 f（x）是L-smooth，有

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

即收斂性得到了證明。

2 實(shí)驗(yàn)

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

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

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

3 結(jié)論及展望

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

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

[ 參 考 文 獻(xiàn) ]

[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

[責(zé)任編校：張巖芳]