面向異構分布式機器學習的動態自適應并行加速方法

馬翔，申國偉，郭春，崔允賀，陳意

（貴州大學 計算機科學與技術學院, 貴州 貴陽 550025）

近年來機器學習(machine learning, ML)廣泛應用到了各種領域，在圖像分類[1]、目標檢測[2-3]、語義分析[4]等領域取得了顯著的效果。然而，隨著訓練數據量的增加和模型復雜度的提升，在單臺機器上訓練ML 模型變得非常困難。因此，為了提高訓練速度，將訓練任務部署在多個計算節點進行并行處理是常用的技術手段[5]。學術界和工業界對許多分布式ML 系統進行了深入研究，例如 PyTorch[6]、TensorFlow[7]。大多數現有系統利用數據并行模式將分布式機器學習任務部署在由高性能計算節點組建的集群之上，比如公共云環境。然而，隨著硬件架構的迭代升級與云技術的高速發展，在實際應用場景中，分布式機器學習集群普遍存在異構性[8]。其異構性主要包括以下方面：1)由于集群中計算節點配備的計算設備(GPU)類型不同，導致節點間的計算性能不一致(即硬件異構性)；2)集群中各計算節點與服務器相連的網絡帶寬與拓撲結構存在差異，導致服務器與各節點之間的通信時間不一致(即網絡異構性)[9]；3)集群資源往往由多個用戶所共享，用戶之間向集群所提交的計算任務對資源的爭用造成同一物理節點在連續迭代訓練中計算速度動態變化(即動態異構性)[10]。

為保證分布式訓練實現與順序訓練相同的收斂性，集群中的節點需要應用相應參數并行方法同步各自的進度。當前主流并行方法有基于同步思想的批量同步并行方法(bulk synchronous parallel,BSP)與基于異步思想的異步并行方法(asynchronous parallel, ASP)。然而，由于集群異構的特點，主流并行方法并不能表現出良好的迭代質量與收斂效率。其中，BSP 每次迭代同步所有節點的模型參數以保證迭代質量,但是快速節點等待慢速節點(stragglers) 同步所消耗的時間受集群環境影響大，并且延遲快速節點開始新一輪的迭代降低了計算資源的利用率和收斂效率[11-12]。ASP 各節點獨立迭代以最大化迭代速度，但是節點參數的不及時同步造成節點間參數新舊各異，舊參數所產生的陳舊梯度增加了訓練的不穩定性與全局模型收斂的不確定性[13-14]。

因此，在異構集群環境中部署分布式學習任務時，如何能充分利用計算資源來加快迭代速度又能降低陳舊梯度的產生成為一個關鍵性問題。針對此問題，本文提出了基于節點狀態的動態自適應同步并行方法(dynamic adaptive synchronous parallel, DASP)，通過對節點訓練狀態的管理和節點并行狀態的動態調整提高迭代速度與收斂效率。

1 相關工作

異構環境下的分布式計算一直是分布式計算社區感興趣的話題[15]。針對異構集群下，主流分布式訓練并行方法帶來的同步等待與陳舊值問題。研究人員主要從減少同步頻率、降低同步代價與消除stragglers 等方面提出了多種解決方案。

在減少同步頻率方面，Ho 等[16]提出了延遲同步并行方法(stale synchronous parallel, SSP)，該方法在訓練開始之前設置延遲同步閾值，當節點之間的迭代次數不超過閾值時，計算節點使用ASP 進行訓練，否則快速節點等待stragglers 進行同步以消除滯后參數。Li 等[17]也引入了有界延遲，不同的是它考慮了所有工作節點的迭代，而不是讓每個節點計算自己的迭代。由于節點訓練狀態的變化，固定的有界閾值可能并不適合整個訓練過程，因此Zhao 等[18]提出了動態延遲同步并行(dynamic stale synchronous parallel, DSSP)來解決靜態有界延遲問題。它設定延遲閾值上下限，允許節點延遲在訓練過程中在該范圍內動態變化。上述方法都有一定局限性，并且在異構集群中，以節點迭代次數作為參考指標可能會退化為BSP[19-20]。

在降低同步代價方面，Chen 等[21]嘗試通過添加備份節點來優化BSP。即在BSP 中有N個節點，然后添加m個備份節點，因此在訓練期間有N+m個節點。在每次迭代完成時，參數服務器只接收前N個節點的梯度，并刪除m個慢速節點的梯度，以減少同步等待時間。但是每次迭代都會隨機浪費m個節點的計算數據。根據此思想，Teng 等[22]提出了貝葉斯分布式隨機梯度下降(Bayesian distributed stochastic gradient descent,BDSGD)，該算法通過選擇一個截止值來減輕同步代價，而超出該截止值所提交的梯度消息會被忽略。Sun 等[23]從節點靜態性能出發提出分組延遲同步并行(grouping stale synchronous parallel,GSSP)方法，該方法將性能相近的工作節點分為同一組，組內采用ASP，組間采用SSP。該方法限制了stragglers 的影響范圍，但是需要在訓練前確定集群中各節點性能，并且沒有關注訓練過程中集群資源共享導致節點性能動態變化的問題。

從消除stragglers 角度出發，Harlap 等[24]提出了FlexRR 靈活并行方案，該方案在計算節點之間動態點對點工作重新分配，將stragglers 的訓練任務按比例卸載到快速節點中。FlexRR 在訓練過程中能根據節點迭代狀態實現最優工作分配，但是在進行任務動態分配時需要花費更長的網絡傳輸時間。Xu 等[25]提出了動態批處理大小機制，該機制通過增大stragglers 的Batch size 來加快其處理速度，但是在異構特點突出的集群中，調整Batch size 帶來速度提升不足以消除stragglers 的影響，并且可能出現Batch size 過大的風險。

上述工作雖然在一定程度上緩解了異構集群下stragglers 與陳舊梯度對模型收斂效率的影響，但是依然存在不足，以節點迭代次數表示陳舊參數不夠精準和靈活，未有效地利用節點訓練時的狀態信息，因此難以適應資源共享情況下節點迭代速度的動態變化。

2 動態自適應同步并行方法

針對當前并行方法的不足與缺點，本文提出DASP 并行方法，框架如圖1 所示。該方法通過參數服務器管理所有工作節點的狀態信息，從中快速識別stragglers 與參數滯后節點。其次，參數服務器利用狀態閾值對并行狀態進行合理劃分，并且根據工作節點運行時狀態信息判斷所處狀態，有效地控制同步等待時間與滯后參數的影響。最后，參數服務器根據節點的并行狀態，對各節點采用合適的參數更新機制。下面將分別討論DASP 方法的節點狀態管理、并行狀態管理以及參數更新管理。

圖1 DASP 框架Fig.1 DASP Framework

2.1 節點狀態管理

為了準確實時地標識使用陳舊參數的節點，參數服務器管理所有節點運行時的狀態信息，其主要是工作節點當前使用的參數版本v與工作節點最近一輪迭代完成時間f。假設t時刻工作節點參數版本v=＜vt1,vt2,···,vtn＞與最近一輪迭代完成時間f=＜f1t,f2t,···,fnt＞ ，其中vt1表示1 號工作節 點在t時刻使用的參數版本，f1t表示1 號工作節點t時刻最近迭代完成時間，并且利用表示t時刻最新的參數版本。假設在t+1時刻收到1 號工作節點梯度，參數服務器對全局模型權重更新之后進一步更新1 號工作節點的參數版本=+1和最近迭代完成時間f1t=f1t+1。通過管理節點運行時狀態信息，參數服務器能夠及時準確地判斷哪些工作節點使用了陳舊模型參數，且對于一個需要進行同步操作的工作節點，根據運行時從每個工作節點收集的最近迭代完成時間，動態生成該工作節點與其他工作節點的最小等待時間。

在DASP 中，針對stragglers 的處理采用了參數版本標識的方法，以代替傳統以迭代次數標識stragglers。因為一些迭代次數較少的計算節點在完成局部梯度傳輸并更新全局模型參數后，它們所使用的模型參數也是新于其他計算節點。

DASP 通過對節點狀態信息的管理，參數服務器利用工作節點參數版本能準確反映節點陳舊參數的使用程度，同時，結合參數版本信息與工作節點最近迭代完成時間確定工作節點的同步點并動態設定最小等待時間以減少同步頻率與同步代價。

2.2 并行狀態管理

在DASP 中，為了更好平衡同步等待與陳舊梯度對全局模型收斂效率的影響，如圖2 所示，并行狀態管理利用狀態閾值Smin與Smax將工作節點的同步狀態合理劃分為3 個狀態，即快速迭代狀態(quick iteration state, QIS) 、弱同步狀態(weak synchronization state, WSS)與強同步狀態(force synchronization state, FSS)。當參數服務器收到工作節點的局部梯度值時，并行狀態管理模塊根據節點狀態管理中的工作節點參數版本信息與狀態閾值決定節點所處的并行狀態Pstate，后續參數更新管理根據節點所處的并行狀態設定對全局模型參數的更新機制。

圖2 DASP 并行狀態管理Fig.2 DASP parallel state management

1) 快速迭代。

從減少同步頻率角度出發，DASP 引入快速迭代狀態。所有工作節點開始迭代訓練時，節點狀態管理中的參數版本信息都為0。此時不存在陳舊參數，并行狀態管理將所有工作節點初始并行狀態設置為QIS。QIS 不對工作節點設立同步屏障，工作節點能完全異步地對參數服務器中全局模型進行更新，使節點可以快速開始新一輪的迭代，同時為了避免節點之間參數差距過大而造成收斂方向偏差，DASP 設立狀態閾值下限Smin，保證QIS 下的工作節點之間參數版本之差不超過Smin。因此，在DASP 方法下允許工作節點進行異步迭代提高資源利用率，同時控制節點之間的參數陳舊程度在一定范圍之內。

2) 弱同步。

當集群中某幾個工作節點版本差距超過Smin時，DASP 并不會立即強制所有節點進行同步操作，因為此時只有少數節點參數版本具有較大差距，所以只需嘗試控制版本相差較大節點，從而限制同步操作影響的范圍。因此，DASP 在并行狀態管理中引入弱同步狀態。在工作節點之間的參數版本超過Smin而 不大于Smax時，并行狀態管理會根據節點狀態所維護的節點最近迭代完成時間設置合理延遲時間：

式中：表示最新參數版本的節點i在開始新一輪迭代之前延遲等待時間， α為權重值，fi為節點i的最近迭代完成時間，fj為 參數版本最小vmin節點的最近迭代完成時間。如圖2 中，在動態延遲等待時間內，最新參數版本的節點有可能與最舊參數版本節點進行同步。因此，DASP 方法可以在弱同步階段利用很小的同步代價消除陳舊參數的影響，并且使節點狀態并行狀態再次轉換為QIS。

3) 強同步。

WSS 在一定程度上緩解了工作節點同步等待問題與陳舊參數的影響，不過在工作節點之間具有突出異構性時，節點并不能在動態延遲時間Twait內成功完成同步。因此為了使DASP 適應各種集群環境并且保證在節點之間參數版本太大時能及時進行參數同步消除陳舊參數，DASP 在并行狀態管理引入了強同步狀態，一旦工作節點之間參數版本差值超過Smax，那么節點就處于強同步狀態。此時DASP 會設立顯式同步柵欄，保證最新參數版本節點與最舊參數版本的節點在同步約束下消除陳舊參數，以防止過度滯后的梯度增加訓練的不穩定性。所以DASP 最后通過FSS 同步約束下保證集群所有節點參數陳舊程度在Smax范圍內，進而防止陳舊參數影響的擴大。

并行狀態管理具體算法如算法1 所示。

算法1PS 并行狀態管理算法

輸入節點參數版本v,節點最近迭代完成時間f

輸出節點Pstate

1)whilereceive local gradientfrom nodendo

3)vn←IdToV(v,n);

4)vmin←min(v); /*獲取當前最舊參數版本*/

5) ifvn-vmin≤Sminthen

6)Pnstate←QIS; /*節點并行狀態為QIS*/

7) else ifSmin＜vn-vmin≤Smaxthen

8)←WSS;

9) i dmin←VTOId(vmin); /*獲取最舊參數版本的節點id*/

11)=/*設置動態延遲時間*/

12) Wait time

13) else

14)←FSS;

15) Wait for the iteration of the oldest parameter version node idminto complete

16) end if

17) end while

2.3 參數更新管理

參數更新管理模塊基于分布式小批量SGD算法并根據并行狀態管理模塊所確定的節點并行狀態對全局模型參數進行更新。在參數更新管理中，并行狀態與參數更新規則為

式中：N是工作節點個數，B表示批大小，為第j批訓練樣本的損失值，K表示節點在節點延遲時間內參數服務器所接收到局部梯度節點的數量。處于QIS 下節點的對服務器全局參數更新規則，處于WSS 與FSS 節點的服務器全局參數更新更新規則。

參數更新具體如算法2 所示。

算法2參數更新算法

輸入節點個數N，學習率γ

輸出最新參數版本參數wnew

1) Receive local gradientginfrom noden

2) Paralle state management sets the parallel state of noden

3) if== QIS then

5) else

6)Δwi←

7)wi+1←wi-γΔwi;

8) Send(wi+1,n); /*將新版本參數發送給節點n*/

9) Atomic operation updating nodenparameter version

3 實驗評估

3.1 實驗設置

為了驗證DASP 策略的有效性，本文針對同構與異構兩種集群環境進行了實驗。該集群中擁有6 個計算節點與一個參數服務器節點。參數服務器節點的硬件信息與軟件信息如表1 所示，工作節點硬件信息與軟件信息如表1、2 所示。

表1 同構環境下工作節點信息Table 1 Information on the work nodes in the homogeneous environment

表2 異構環境下異構工作節點信息Table 2 Information on heterogeneous work nodes in a heterogeneous environment

本實驗采用了MNIST、CIFAR-10 兩種常用的圖像識別數據集來進行分布式訓練。在實驗過程中，本文采用LeNet-5、ResNet-18[26]和VGG-19[27]常用的深度學習模型進行訓練，并應用BSP、ASP、SSP、DSSP 與DASP 進行對比分析。

為了量化不同并行策略的性能，使用了多個常用的評估標準，包括平均迭代時間(average iteration time)、收斂時間(convergence time)，并且利用模型在測試集上準確率的波動程度表示陳舊梯度對收斂方向的影響。其中訓練具體參數如表3 所示。

表3 具體訓練參數Table 3 Specific training parameters

3.2 實驗結果分析

為了量化陳舊梯度對收斂趨勢的影響程度，首先測試了在BSP、ASP、SSP、DSSP 與DASP 并行方法下模型在測試集上準確率變化情況。如圖3 與圖4 所示，對于復雜度較低的LeNet-5，在兩種集群下不同并行方法都能快速穩定地達到收斂。對于ResNet-18 與VGG19_bn，BSP 在同構與異構環境下都能穩定達到收斂，這是因為其同步特性，所以節點之間每次迭代都使用相同的全局模型，不存在參數偏差的影響。而ASP出現了明顯的波動，這是由于ASP 異步特性無法及時解決節點所使用的陳舊參數而最終影響整體模型。相較于ASP，SSP、DSSP 與DASP 在準確率上的表現比較穩定，并且隨著集群異構性越明顯，DASP 的表現要比SSP 和DSSP 越好。因為在DASP 下處于弱同步狀態下的高參數版本節點可以通過動態延遲等待一定時間，在這段時間內低參數版本可能與高參數版本節點進行同步從而減少陳舊參數的產生，而當節點間參數版本相差較大時，在強同步狀態的控制下高參數版本節點會強制與低參數版本節點進行同步，從而限制陳舊參數影響的擴散。DASP通過這兩種狀態降低了節點陳舊參數對全局模型的影響。

圖3 同構集群下不同并行方法 LeNet-5、ResNet-18、VGG19_bn 測試集準確率Fig.3 Accuracy of test sets of LeNet-5, ResNet-18, VGG19_bn with different parallel methods under homogeneous clusters

圖4 異構集群下不同并行方法 LeNet-5、ResNet-18、VGG19_bn 測試集準確率Fig.4 Accuracy of test sets of LeNet-5, ResNet-18, VGG19_bn with different parallel methods under heterogeneous clusters

為了反映在DASP 下stragglers 對快速節點影響情況，統計了不同集群中模型平均迭代時間。平均迭代時間越低表示在參數服務器進行參數聚合時，集群中stragglers 對快速節點的影響更小。如表4 與表5 所示，BSP 每次迭代都需要進行節點之間參數同步，所以平均迭代時間在兩種集群下都遠高于其他并行方法，而ASP 由于節點之間異步迭代訓練，所以平均迭代時間最低。總體來看，對于LeNet-5、ResNet-18 與VGG 19_BN 3 種模型，在同構環境下，DASP 對比BSP 分別減少了16.9%、69.2% 與39.5% 的迭代時間，對比SSP 分別減少了1.5%、32.1%與7.9%的迭代時間，對比DSSP 分別減少了4.7%、7.0%與7.6%的迭代時間。在異構集群下，DASP 對比BSP 分別減少了19.3%、82.1%與66.5%的迭代時間，對比SSP 分別減少了5.3%、41.4%與7.2%的迭代時間，對比DSSP 分別減少3.2%、1.5%與3.2%的迭代時間。同時，DASP 受集群中節點性能差異的影響最小。這是因為DASP 是基于節點參數版本來管理節點的同步狀態，所以在模型訓練過程中減少快速節點不必要的等待，從而減少了迭代時間，進而提高集群資源的利用率。

表4 同構集群下不同并行方法平均迭代完成時間Table 4 Average iteration completion time for different parallel methods under homogeneous clusters

表5 異構集群下不同并行方法平均迭代完成時間Table 5 Average iteration completion time of different parallel methods under heterogeneous clusters

最后統計了在BSP、ASP、SSP、DSSP 與DASP并行方法下模型到達相同準確率所需時間，該時間為迭代平均完成時間與迭代次數的乘積。ASP雖然平均迭代時間短，但是由于陳舊參數的影響而導致收斂需要更多輪次。如表6 與表7 所示，DASP 在同構與異構集群下都具有良好的收斂時間。總體來看，對于LeNet-5 模型，DASP 與其他并行方法都能快速收斂，但在同構集群下，DASP并沒有表現出良好的收斂效果，其主要原因是該模型迭代時間非常低以至于節點之間的等待時間不足以覆蓋狀態調整時所需的額外開銷。對于ResNet-18 與VGG19_BN 復雜度較高的模型，在同構集群下，DASP 對比BSP 收斂時間減少了10%、24.4%，對比ASP 減少了23.5%、10%，相比SSP 減少了5.9%、1.8%,相比DSSP 減少了3.5%、4.9%。在異構集群下，DASP 對比BSP 收斂時間減少了61.2%、22.3%，對比ASP 減少了42.7%、29.8%，相比SSP 減少了16.3%、16.9%，相比DSSP 減少了14.8%、10.1%。

表6 同構集群下不同并行方法收斂時間Table 6 Convergence time of different parallel strategies under homogeneous clusters

表7 異構集群下不同并行方法收斂時間Table 7 Convergence time of different parallel strategies under heterogeneous clusters

從實驗結果得出，DASP 相比主流并行方法更有效地緩解stragglers 與陳舊梯度問題。最終，提高了資源利用率并降低了收斂時間。

4 結束語

針對異構集群下分布式機器學習參數同步并行策略的問題，提出了一種基于節點狀態的動態自適應同步并行方法DASP。DASP 并行方法通過工作節點訓練狀態信息管理使參數服務器可以更精準標識stragglers 與產生陳舊梯度的節點，解決了異步并行方法的問題。針對同步等待問題，通過在運行時分析工作節點的狀態信息為每個節點實現不同的并行范例，提高stragglers 的更新效率并消除舊參數來避免陳舊梯度的產生，以此來緩解它們的影響。最后，通過使用典型的深度學習模型和數據集分別在同構集群與異構集群下開展了實驗。實驗表明，在將模型收斂到相同測試準確率的情況下，DASP 相比與基準方法收斂時間減少了16.9%～82.1%。

后續工作將繼續探索如何更有效地利用節點狀態信息對并行狀態閾值進行動態設定，從而進一步降低同步代價。