楊堅(jiān)偉，孟 敏，黃家樂(lè)，武繼剛

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州510006)

1 引言

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

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

2 研究現(xiàn)狀

2.1 眾包感知模型與任務(wù)調(diào)度

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

然而現(xiàn)有的此類研究很少?gòu)囊活愄厥獾挠?jì)算任務(wù)——分布式訓(xùn)練任務(wù)的執(zhí)行效率角度研究相應(yīng)的眾包感知模型。在該模型中，眾包感知任務(wù)發(fā)布者在滿足資源約束的同時(shí)將任務(wù)分配給不同的ES。但是，與上述模型不同的是，ES集群也在執(zhí)行分布式訓(xùn)練任務(wù)。由于不確定異構(gòu)任務(wù)在其執(zhí)行時(shí)間內(nèi)的資源消耗，為盡可能滿足終端用戶的實(shí)時(shí)任務(wù)請(qǐng)求，PS在進(jìn)行全局模型的更新時(shí)，將會(huì)把執(zhí)行異構(gòu)任務(wù)的ES視為離群結(jié)點(diǎn)，不再使用其局部訓(xùn)練結(jié)果?；谶@一前提，在保證異構(gòu)任務(wù)執(zhí)行效率的條件下，還需實(shí)現(xiàn)該集群的分布式訓(xùn)練性能最大化。

2.2 分布式訓(xùn)練與任務(wù)調(diào)度

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

近年來(lái)也出現(xiàn)了不少針對(duì)訓(xùn)練性能這一指標(biāo)進(jìn)行量化所展開(kāi)的研究。Chen等[12]在保證分布式訓(xùn)練性能最優(yōu)的條件下，通過(guò)聯(lián)合優(yōu)化通信資源分配策略與工作結(jié)點(diǎn)選擇策略最小化訓(xùn)練時(shí)間，并進(jìn)一步引入人工神經(jīng)網(wǎng)絡(luò)估計(jì)模型參數(shù)，提高收斂速度；此外，Chen等[13]進(jìn)一步考慮數(shù)據(jù)包傳輸?shù)挠绊懀诼?lián)合優(yōu)化資源分配策略與工作結(jié)點(diǎn)選擇策略的同時(shí)，通過(guò)找到最優(yōu)通信功率建立訓(xùn)練性能與包錯(cuò)誤之間的關(guān)系，最大化訓(xùn)練性能。受文獻(xiàn)[12,13]對(duì)收斂性能分析方法的影響，本文建立了異構(gòu)任務(wù)調(diào)度與分布式訓(xùn)練性能之間的關(guān)系，將其創(chuàng)新性地轉(zhuǎn)化為多維多選擇背包問(wèn)題MMKP(Multidimensional Multiple-choice Knapsack Problem)進(jìn)行求解，在優(yōu)化異構(gòu)任務(wù)調(diào)度策略的同時(shí),最大化分布式訓(xùn)練的性能。

3 系統(tǒng)模型

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

Figure 1 System model圖1 系統(tǒng)模型

訓(xùn)練過(guò)程中，假設(shè)ES集群需要處理另一個(gè)到訪的異構(gòu)任務(wù)集合Q={Q1,…,Qj,…,Qq}，其中，q為任務(wù)數(shù)量且q

(1)

因此，本文關(guān)于異構(gòu)任務(wù)調(diào)度策略aj的分布式訓(xùn)練性能優(yōu)化目標(biāo)初步可以寫為：

(2)

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

(3)

3.1 通信模型

對(duì)于第i個(gè)ES節(jié)點(diǎn)Ni，其與PS之間的傳輸速率如式(4)所示：

(4)

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

(5)

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

(6)

其中，oi滿足與vi相關(guān)的指數(shù)分布，m為瀑布閾值[14]。

對(duì)于Qj，假設(shè)由Ni執(zhí)行，則其任務(wù)發(fā)布者與Ni之間的傳輸速率如式(7)所示：

(7)

(8)

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

(9)

在實(shí)際應(yīng)用中，分配給執(zhí)行異構(gòu)任務(wù)的ES的帶寬資源之和不能超過(guò)當(dāng)前可用的最大系統(tǒng)帶寬。假設(shè)當(dāng)前可用的最大系統(tǒng)帶寬為B，則有：

(10)

3.2 能耗模型

對(duì)于第j個(gè)異構(gòu)任務(wù)Qj，假設(shè)ES的有效電容系數(shù)為γ，CPU頻率為δ，η0為計(jì)算能耗懲罰因子，則Qj的計(jì)算能耗為：

(11)

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

(12)

在實(shí)際應(yīng)用中，執(zhí)行異構(gòu)任務(wù)的過(guò)程需滿足其產(chǎn)生的傳輸與計(jì)算能耗之和不超過(guò)ES集群所能承擔(dān)的最大能耗。假設(shè)系統(tǒng)可承擔(dān)的最大能耗開(kāi)銷為Emax，則有：

(13)

4 收斂分析

(14)

(15)

其中，

(16)

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

(17)

假設(shè)2F(W)滿足強(qiáng)凸性(μ為正常數(shù))，即：

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

(18)

假設(shè)3F(W)二次連續(xù)可微，基于上述假設(shè)則可推導(dǎo)出關(guān)于F(W)的二階偏導(dǎo)數(shù)被關(guān)于‖Wt+1-Wt‖的三次函數(shù)上下逼近：

(19)

以上假設(shè)均可被一般的機(jī)器學(xué)習(xí)損失函數(shù)所滿足。

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

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

(20)

其中，

(21)

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

(22)

給定學(xué)習(xí)率λ=1/L，則有：

(23)

結(jié)合式(16)推導(dǎo)其數(shù)學(xué)期望，則有：

(24)

(25)

因此：

(26)

由式(18)可以推導(dǎo)出：

(27)

(28)

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

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

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

(29)

證明完畢。

□

顯然，當(dāng)?！?時(shí)模型將無(wú)法收斂，因此本文只在Γ<1的情況下討論訓(xùn)練性能。而當(dāng)t足夠大時(shí)，有Γt=0。則不等式(29)右側(cè)的第1項(xiàng)可重寫為：

(30)

(31)

(32)

(33)

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

(34)

式(10)和式(13)

(35)

5 異構(gòu)任務(wù)調(diào)度算法

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

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

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

(36)

□

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

5.1 基于最大系統(tǒng)效用的貪心策略求初始解

步驟1計(jì)算異構(gòu)任務(wù)集合Q在邊緣服務(wù)器集合N上的預(yù)期效用值，得到預(yù)期效用矩陣。

步驟2置空異構(gòu)任務(wù)調(diào)度狀態(tài)轉(zhuǎn)移矩陣flag，令當(dāng)前背包容量為sum(k)=0，k=1,2。

步驟3從沒(méi)有分配到任何邊緣服務(wù)器的異構(gòu)任務(wù)中隨機(jī)選擇一個(gè)任務(wù)Qj，轉(zhuǎn)步驟4；若異構(gòu)任務(wù)全部分配完成，轉(zhuǎn)步驟7。

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

步驟5計(jì)算將Qj分配給Ni后所產(chǎn)生的k個(gè)背包權(quán)重并將其與對(duì)應(yīng)的當(dāng)前背包容量sum(k)相加，若sum(k)小于或等于其可容忍的最大容量，則flag(i,j)=flag(i,j)+1。

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

步驟7算法執(zhí)行完畢，得到異構(gòu)任務(wù)調(diào)度策略的初始解sol0。

5.2 禁忌搜索算法

在利用貪心策略求得異構(gòu)任務(wù)調(diào)度策略的初始解的基礎(chǔ)上，本文提出了基于禁忌搜索的異構(gòu)任務(wù)調(diào)度算法，其基本步驟(續(xù)5.1節(jié))如下所示：

步驟8給定禁忌搜索算法相關(guān)參數(shù)，置空邊緣服務(wù)器集合N所對(duì)應(yīng)的n×n禁忌矩陣tabu，即允許所有邊緣服務(wù)器被交換。

步驟9初始化時(shí)當(dāng)前最佳解為solbest=sol0，該解為n×q的任務(wù)調(diào)度矩陣，矩陣元素值為0或1。

步驟10令當(dāng)前最佳解所對(duì)應(yīng)的評(píng)價(jià)值BestL為solbest所對(duì)應(yīng)的系統(tǒng)效用值，并令當(dāng)前解solnow=solbest。

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

步驟12判斷第1個(gè)最佳候選解的系統(tǒng)效用值是否大于BestL，如果是，則更新solbest，同時(shí)更新BestL的值為該候選解的系統(tǒng)效用值，并將候選解所對(duì)應(yīng)的2個(gè)邊緣服務(wù)器置入禁忌表，轉(zhuǎn)向步驟13；否則，轉(zhuǎn)向步驟12。

步驟13判斷候選解集合中各對(duì)象的禁忌屬性，從中選擇不屬于禁忌表的最優(yōu)解更新當(dāng)前解solnow，然后將solnow所對(duì)應(yīng)的2個(gè)邊緣服務(wù)器置入禁忌表。

步驟14判斷算法是否達(dá)到最大迭代次數(shù)，若是，算法停止迭代并輸出最終結(jié)果；否則，轉(zhuǎn)步驟10。

5.3 時(shí)間復(fù)雜度分析

定理3基于禁忌搜索與貪心策略的異構(gòu)任務(wù)調(diào)度混合算法的總時(shí)間復(fù)雜度為O(n2)。

證明本文假設(shè)異構(gòu)任務(wù)數(shù)量為q，對(duì)應(yīng)可供分配的邊緣服務(wù)器數(shù)為n，且實(shí)際應(yīng)用中任務(wù)調(diào)度測(cè)試基準(zhǔn)滿足n>q，分析異構(gòu)任務(wù)調(diào)度算法的時(shí)間復(fù)雜度應(yīng)從以下兩部分進(jìn)行：

(1)初始解求解部分：步驟1，對(duì)q個(gè)異構(gòu)任務(wù)進(jìn)行遍歷，計(jì)算每個(gè)任務(wù)在n個(gè)邊緣服務(wù)器上的效用值，時(shí)間復(fù)雜度為O(nq)；初始化異構(gòu)任務(wù)調(diào)度狀態(tài)轉(zhuǎn)移矩陣flag，時(shí)間復(fù)雜度為O(nq)；步驟3，遍歷異構(gòu)任務(wù)集合，將任務(wù)分配給滿足資源約束的具有最大效用值的邊緣服務(wù)器，時(shí)間復(fù)雜度為O(nq)。因此，初始解求解部分的時(shí)間復(fù)雜度為O(nq)。

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

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

□

6 仿真對(duì)比實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文所提異構(gòu)任務(wù)調(diào)度算法對(duì)分布式訓(xùn)練性能的影響，采用Matlab平臺(tái)進(jìn)行仿真并分析所提算法的性能。本文算法的相關(guān)實(shí)驗(yàn)均在同一實(shí)驗(yàn)環(huán)境中進(jìn)行，其中：CPU主頻為2.80 GHz，內(nèi)存為8 GB，操作系統(tǒng)為64位Windows 10。本文假設(shè)邊緣服務(wù)器數(shù)量n=80，并采用3種基準(zhǔn)算法作為對(duì)比算法進(jìn)行對(duì)比分析，具體如下所示：

(1)模擬退火算法。通過(guò)模擬固體高溫退火過(guò)程，將溫度升高所對(duì)應(yīng)的物體內(nèi)能模擬為該算法中的目標(biāo)函數(shù)值，相應(yīng)溫度模擬為算法控制參數(shù)，得到隨機(jī)尋優(yōu)的模擬退火算法。模擬退火算法能夠有效避免陷入局部最優(yōu)的情況，且該算法執(zhí)行效率與初始解的好壞無(wú)關(guān)。

(2)貪心算法。即本文算法中求解異構(gòu)任務(wù)調(diào)度策略初始解時(shí)所用算法。相對(duì)于為求得最優(yōu)解所需要的大量窮舉操作，該算法更加簡(jiǎn)單高效。

(3)隨機(jī)調(diào)度算法。在滿足資源約束的前提下對(duì)異構(gòu)任務(wù)進(jìn)行隨機(jī)調(diào)度。該算法能夠顯著降低算法復(fù)雜度。

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

Figure 2 Relationship between total numbers of heterogeneous tasks and system utility under different bandwidths圖2 不同帶寬下異構(gòu)任務(wù)數(shù)量與系統(tǒng)效用之間的關(guān)系

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

Figure 3 Relationship between total numbers of heterogeneous tasks and system utility of different algorithms圖3 不同算法中異構(gòu)任務(wù)數(shù)量與系統(tǒng)效用之間的關(guān)系

7 結(jié)束語(yǔ)

本文對(duì)分布式訓(xùn)練中的異構(gòu)任務(wù)調(diào)度問(wèn)題進(jìn)行了研究，充分考慮了異構(gòu)任務(wù)調(diào)度策略與分布式訓(xùn)練性能之間的關(guān)系，在保證收斂的前提下對(duì)訓(xùn)練性能的影響因素進(jìn)行理論分析，從而建立了最大化分布式訓(xùn)練性能的優(yōu)化目標(biāo)；并將其轉(zhuǎn)化為多維多選擇背包問(wèn)題，在考慮系統(tǒng)帶寬與能耗開(kāi)銷的需求下，利用基于貪心策略的禁忌搜索算法為各個(gè)邊緣服務(wù)器進(jìn)行合理的異構(gòu)任務(wù)調(diào)度，最終得到了近似最優(yōu)的任務(wù)調(diào)度策略，有效地提升了分布式訓(xùn)練性能。