分布式訓練異構任務調度算法研究

楊堅偉，孟 敏，黃家樂，武繼剛

(廣東工業大學計算機學院，廣東 廣州510006)

1 引言

近年來，隨著深度學習領域研究的快速發展以及移動終端的大規模普及，資源與計算密集型的深度學習應用越來越多地被部署在移動終端設備上，如車聯網中的道路識別應用和遠程醫療應用等。然而，由于深度學習網絡結構日趨復雜且產生了大型數據集，終端設備往往難以承擔深度學習應用所需的巨大訓練成本。通過將訓練任務分配給多個邊緣服務器ES(Edge Server)進行協同訓練，分布式訓練與邊緣計算的結合使得這一問題的解決成為可能。目前一般采用參數服務器PS(Parameter Server)架構執行分布式訓練過程，由多個邊緣服務器作為工作結點(Worker)計算本地數據的梯度，并與PS(在本文中指云服務器)之間進行參數共享，實現對模型損失函數的優化。

然而，作為分布式訓練中的工作結點，ES在訓練過程中經常需要同時處理大量異構任務。以車聯網中道路識別的分布式訓練任務為例，車載輔助駕駛設備可能需要ES(如路旁基站等)在執行訓練任務的同時提供實時的多媒體語音、視頻等服務。在實際應用中，異構任務發布者可能預購了與訓練結果相關的服務，同時異構任務在不同的ES上執行所需的工作能耗、通信要求不同。因此，研究如何合理調度異構任務，從而能夠在保障異構任務服務質量的同時，盡可能最大化ES集群的分布式訓練性能，具有十分重要的現實意義。

2 研究現狀

2.1 眾包感知模型與任務調度

隨著無線傳感器的廣泛使用，由傳感器節點承擔大型感知項目的部分子任務成為可能，因此人們提出了眾包感知模型這一概念，即具有傳感器的計算結點可以向眾包任務發布者上傳其感知并處理的數據，常見于人群計數、目標檢測等相關任務中[1]。在眾包感知模型中，如何基于有限的價格預算、算力和設備能耗等資源約束，實現高效的任務分配，一直以來都是人們研究的重點。Zhang等[2]提出了一種新的參與者選擇框架，能夠在基于節能原則的眾包感知模型上選擇合適的參與者，實現激勵報酬最小化；文獻[3,4]通過在線問卷或來自社交網絡的真實數據了解用戶偏好，推斷決策過程，并提出一種用戶貢獻依賴于其所得到的激勵大小的概率模型，在有限的任務預算下將其應用于用戶選擇過程，實現用戶總貢獻的期望最大化。

然而現有的此類研究很少從一類特殊的計算任務——分布式訓練任務的執行效率角度研究相應的眾包感知模型。在該模型中，眾包感知任務發布者在滿足資源約束的同時將任務分配給不同的ES。但是，與上述模型不同的是，ES集群也在執行分布式訓練任務。由于不確定異構任務在其執行時間內的資源消耗，為盡可能滿足終端用戶的實時任務請求，PS在進行全局模型的更新時，將會把執行異構任務的ES視為離群結點，不再使用其局部訓練結果。基于這一前提，在保證異構任務執行效率的條件下，還需實現該集群的分布式訓練性能最大化。

2.2 分布式訓練與任務調度

由于分布式訓練的興起，將任務調度與分布式訓練相結合也成為近年來的研究熱點之一。文獻[5]研究了分布式訓練中任務卸載與資源分配協同優化策略，在滿足服務質量的前提下將其形式化定義為混合非線性整型優化問題，最大化系統吞吐量；文獻[6]研究了分布式訓練中計算任務的分配問題，提出了2種最小化任務完成時間的調度方案；Bao等[7]基于強化學習策略，以最小化同位干擾與最大化訓練性能為目標，設計能夠高效放置訓練任務的機器學習集群調度器。此外，國內學者也從不同角度針對分布式訓練中的資源調度過程進行過大量研究[8 - 11]。上述研究對象大都是單一任務類型，但在實際訓練過程中，Worker集群可能需要以犧牲訓練任務執行效率為代價處理實時的異構任務請求，而上述研究大都沒有考慮異構任務調度策略對訓練性能的影響。

近年來也出現了不少針對訓練性能這一指標進行量化所展開的研究。Chen等[12]在保證分布式訓練性能最優的條件下，通過聯合優化通信資源分配策略與工作結點選擇策略最小化訓練時間，并進一步引入人工神經網絡估計模型參數，提高收斂速度；此外，Chen等[13]進一步考慮數據包傳輸的影響，在聯合優化資源分配策略與工作結點選擇策略的同時，通過找到最優通信功率建立訓練性能與包錯誤之間的關系，最大化訓練性能。受文獻[12,13]對收斂性能分析方法的影響，本文建立了異構任務調度與分布式訓練性能之間的關系，將其創新性地轉化為多維多選擇背包問題MMKP(Multidimensional Multiple-choice Knapsack Problem)進行求解，在優化異構任務調度策略的同時,最大化分布式訓練的性能。

3 系統模型

本文在無線環境下采用文獻[12]所使用的分布式訓練框架，結點傳輸時采用的協議是正交頻分復用OFDMA(Orthogonal Frequency Division Multiple Access)。圖1搭建了一個由ES集群與異構任務發布者所組成的任務調度系統。本文假設云服務器為分布式訓練任務中的PS，ES集群為N={1,2,…,n}，并將第i(i∈N)個ES結點表示為Ni。PS在ES集群N中分發訓練任務。由于訓練任務具有一定時延要求，本文以二值變量ci表示最終分發結果，其中，ci=1表示Ni在延遲約束條件下成功接收到訓練任務，反之ci=0。對于Ni，將其本地訓練樣本數量表示為si，則其訓練所得到的權重向量可表示為wi=[wi,1,…,wi,zi,…,wi,si]。

Figure 1 System model圖1 系統模型

訓練過程中，假設ES集群需要處理另一個到訪的異構任務集合Q={Q1,…,Qj,…,Qq}，其中，q為任務數量且q

(1)

因此，本文關于異構任務調度策略aj的分布式訓練性能優化目標初步可以寫為：

(2)

wi,1=…=wi,zi=…=wi,si,?i∈N

(3)

3.1 通信模型

對于第i個ES節點Ni，其與PS之間的傳輸速率如式(4)所示：

(4)

其中，Bi是Ni與PS之間的通信帶寬，ω是背景噪聲，αi與pi分別為Ni與PS之間的信道增益與通信功率。由于各ES從PS下載的訓練模型大小相同，因此通信速率將成為ES能否在一定時間內成功下載模型的主要瓶頸。考慮用oi表示Ni成功接收訓練任務的概率，則有：

(5)

oi(vi)=1-exp[-m(vi+ω)]

(6)

其中，oi滿足與vi相關的指數分布，m為瀑布閾值[14]。

對于Qj，假設由Ni執行，則其任務發布者與Ni之間的傳輸速率如式(7)所示：

(7)

(8)

因此，在上述前提下，分配給Ni的最小帶寬資源為：

(9)

在實際應用中，分配給執行異構任務的ES的帶寬資源之和不能超過當前可用的最大系統帶寬。假設當前可用的最大系統帶寬為B，則有：

(10)

3.2 能耗模型

對于第j個異構任務Qj，假設ES的有效電容系數為γ，CPU頻率為δ，η0為計算能耗懲罰因子，則Qj的計算能耗為：

(11)

假設Qj由Ni執行，ηi為Qj與Ni之間的傳輸能耗懲罰因子，則最大傳輸能耗為：

(12)

在實際應用中，執行異構任務的過程需滿足其產生的傳輸與計算能耗之和不超過ES集群所能承擔的最大能耗。假設系統可承擔的最大能耗開銷為Emax，則有：

(13)

4 收斂分析

(14)

(15)

其中，

(16)

設全局模型收斂后的權重為W*，本文使用下列收斂分析中常用的定義與假設[15 - 18]：

(17)

假設2F(W)滿足強凸性(μ為正常數)，即：

F(Wt+1)≥F(Wt)+

(18)

假設3F(W)二次連續可微，基于上述假設則可推導出關于F(W)的二階偏導數被關于‖Wt+1-Wt‖的三次函數上下逼近：

(19)

以上假設均可被一般的機器學習損失函數所滿足。

定理1在上述已知條件與假設成立的情況下，有：

ΓtE(F(W0)-F(W*))

(20)

其中，

(21)

證明由式(17)可求得F(Wt+1)的二階泰勒展開式：

(22)

給定學習率λ=1/L，則有：

(23)

結合式(16)推導其數學期望，則有：

(24)

(25)

因此：

(26)

由式(18)可以推導出：

(27)

(28)

將式(26)代入式(24)，兩邊同減去F(W*)，遞歸調用后，則有：

E(F(Wt+1)-F(W*))≤

Γt(F(W0)-F(W*))

(29)

證明完畢。

□

顯然，當Γ≥1時模型將無法收斂，因此本文只在Γ<1的情況下討論訓練性能。而當t足夠大時，有Γt=0。則不等式(29)右側的第1項可重寫為：

(30)

(31)

(32)

(33)

aj,i∈{0,1},?i∈N,?j∈Q

(34)

式(10)和式(13)

(35)

5 異構任務調度算法

定理2式(31)可轉化為多維多選擇背包問題。

證明多維多選擇背包問題MMKP可用式(36)描述：

xi,j∈{0,1},i=1,2,…,K;j=1,2,…,M

(36)

□

由于MMKP問題為非確定性多項式難題，不難得知式(31)也屬于非確定性多項式難題。作為一種可以快速求得此類問題次優解的解法，啟發式解法通常從較優的初始可行解出發，經過多次迭代調整后得到更優的可行解。為在保證服務質量的同時滿足分布式訓練性能最大化，本文采用基于貪心策略的禁忌搜索算法對式(31)進行求解。本文所使用的禁忌搜索算法是一種改進的局部鄰域搜索算法(又稱爬山啟發式算法)。在本文中，該算法通過引入一個高效靈活的存儲結構——禁忌表，以及設計相應的禁忌準則與藐視準則，能夠保證對不同搜索路徑的有效探索；此外，貪心策略能夠基于最大系統效用值實現對異構任務調度策略初始解的優化[19]。禁忌搜索算法已經成功地應用到許多優化問題，如旅行推銷員問題、生產調度問題等。

5.1 基于最大系統效用的貪心策略求初始解

步驟1計算異構任務集合Q在邊緣服務器集合N上的預期效用值，得到預期效用矩陣。

步驟2置空異構任務調度狀態轉移矩陣flag，令當前背包容量為sum(k)=0，k=1,2。

步驟3從沒有分配到任何邊緣服務器的異構任務中隨機選擇一個任務Qj，轉步驟4；若異構任務全部分配完成，轉步驟7。

步驟4在預期效用矩陣中找到其效用值最高且未被分配的邊緣服務器Ni。

步驟5計算將Qj分配給Ni后所產生的k個背包權重并將其與對應的當前背包容量sum(k)相加，若sum(k)小于或等于其可容忍的最大容量，則flag(i,j)=flag(i,j)+1。

步驟6若flag(i,j)=2，則更新sum(k)，將Qj分配給Ni，轉步驟3；否則，轉步驟4。

步驟7算法執行完畢，得到異構任務調度策略的初始解sol0。

5.2 禁忌搜索算法

在利用貪心策略求得異構任務調度策略的初始解的基礎上，本文提出了基于禁忌搜索的異構任務調度算法，其基本步驟(續5.1節)如下所示：

步驟8給定禁忌搜索算法相關參數，置空邊緣服務器集合N所對應的n×n禁忌矩陣tabu，即允許所有邊緣服務器被交換。

步驟9初始化時當前最佳解為solbest=sol0，該解為n×q的任務調度矩陣，矩陣元素值為0或1。

步驟10令當前最佳解所對應的評價值BestL為solbest所對應的系統效用值，并令當前解solnow=solbest。

步驟11在當前解的鄰域內使用交換操作產生r個候選解(本文取r=50)，即交換當前解中任意2行作為當前解的一個鄰域候選解，計算候選解的系統效用值，并選擇前25個滿足條件的最佳候選解，按照系統效用值從大到小進行排序。

步驟12判斷第1個最佳候選解的系統效用值是否大于BestL，如果是，則更新solbest，同時更新BestL的值為該候選解的系統效用值，并將候選解所對應的2個邊緣服務器置入禁忌表，轉向步驟13；否則，轉向步驟12。

步驟13判斷候選解集合中各對象的禁忌屬性，從中選擇不屬于禁忌表的最優解更新當前解solnow，然后將solnow所對應的2個邊緣服務器置入禁忌表。

步驟14判斷算法是否達到最大迭代次數，若是，算法停止迭代并輸出最終結果；否則，轉步驟10。

5.3 時間復雜度分析

定理3基于禁忌搜索與貪心策略的異構任務調度混合算法的總時間復雜度為O(n2)。

證明本文假設異構任務數量為q，對應可供分配的邊緣服務器數為n，且實際應用中任務調度測試基準滿足n>q，分析異構任務調度算法的時間復雜度應從以下兩部分進行：

(1)初始解求解部分：步驟1，對q個異構任務進行遍歷，計算每個任務在n個邊緣服務器上的效用值，時間復雜度為O(nq)；初始化異構任務調度狀態轉移矩陣flag，時間復雜度為O(nq)；步驟3，遍歷異構任務集合，將任務分配給滿足資源約束的具有最大效用值的邊緣服務器，時間復雜度為O(nq)。因此，初始解求解部分的時間復雜度為O(nq)。

(2)初始解優化部分：步驟8，初始化大小為n×n的禁忌矩陣，時間復雜度為O(n2)；步驟11，基于禁忌搜索算法選擇效用值大的邊緣服務器對進行交換，其交換次數不大于n2，時間復雜度為O(n2)。因此，初始解優化部分的時間復雜度為O(n2)。

由于實際情況下一般n>q，因此，基于禁忌搜索與貪心策略的異構任務調度混合算法的總時間復雜度為O(n2)。定理3得證。

□

6 仿真對比實驗與結果分析

為了驗證本文所提異構任務調度算法對分布式訓練性能的影響，采用Matlab平臺進行仿真并分析所提算法的性能。本文算法的相關實驗均在同一實驗環境中進行，其中：CPU主頻為2.80 GHz，內存為8 GB，操作系統為64位Windows 10。本文假設邊緣服務器數量n=80，并采用3種基準算法作為對比算法進行對比分析，具體如下所示：

(1)模擬退火算法。通過模擬固體高溫退火過程，將溫度升高所對應的物體內能模擬為該算法中的目標函數值，相應溫度模擬為算法控制參數，得到隨機尋優的模擬退火算法。模擬退火算法能夠有效避免陷入局部最優的情況，且該算法執行效率與初始解的好壞無關。

(2)貪心算法。即本文算法中求解異構任務調度策略初始解時所用算法。相對于為求得最優解所需要的大量窮舉操作，該算法更加簡單高效。

(3)隨機調度算法。在滿足資源約束的前提下對異構任務進行隨機調度。該算法能夠顯著降低算法復雜度。

圖2為系統最大帶寬B為10 MHz，30 MHz，50 MHz,80 MHz時，本文算法中異構任務數量與系統效用值(即分布式訓練性能)之間的關系。由于異構任務所需消耗的計算資源是固定的，因此系統總能耗開銷主要依賴于通信能耗開銷。隨著可用系統帶寬的增大，各邊緣服務器所能支配的帶寬資源與所能容忍的通信能耗開銷也隨之增大，因此能夠在滿足約束條件的前提下求得系統效用值更大的近似最優解。而在系統帶寬B為10 MHz時，邊緣服務器數量超過某一閾值后，系統效用值變化較小，其原因在于大部分邊緣服務器無法滿足與異構任務調度策略相關的帶寬與能耗約束，系統效用值基本趨于平穩。

Figure 2 Relationship between total numbers of heterogeneous tasks and system utility under different bandwidths圖2 不同帶寬下異構任務數量與系統效用之間的關系

圖3描繪了4種不同算法中系統效用值隨異構任務數量的變化曲線。與圖2的仿真分析結果相似，固定其他參數不變的情況下，同一種算法中系統效用值均隨異構任務數量的增大而減少，但能夠直觀看出的是，由于本文所提算法基于貪心策略得到了一個較優的初始解，能夠靈活跳出局部最優的陷阱，因此性能明顯優于其他3種基準算法。從圖3中可以看出，隨機調度算法作為一種概率算法，其求解得到的系統效用值具有較高的不穩定性；貪心算法雖然能夠快速地求得局部最優解，但難以保證全局最優；而模擬退火算法與禁忌搜索算法的區別之一是，模擬退火算法主要基于隨機尋優策略尋找鄰域解，因此較容易錯過更優的解。當異構任務數量較少時，4種算法所對應的系統效用值基本一致；而當異構任務數量增多時，本文所提算法明顯優于其他算法。

Figure 3 Relationship between total numbers of heterogeneous tasks and system utility of different algorithms圖3 不同算法中異構任務數量與系統效用之間的關系

7 結束語

本文對分布式訓練中的異構任務調度問題進行了研究，充分考慮了異構任務調度策略與分布式訓練性能之間的關系，在保證收斂的前提下對訓練性能的影響因素進行理論分析，從而建立了最大化分布式訓練性能的優化目標；并將其轉化為多維多選擇背包問題，在考慮系統帶寬與能耗開銷的需求下，利用基于貪心策略的禁忌搜索算法為各個邊緣服務器進行合理的異構任務調度，最終得到了近似最優的任務調度策略，有效地提升了分布式訓練性能。