JEDERL：一種異構(gòu)計算平臺任務(wù)調(diào)度優(yōu)化算法

呂文凱，楊鵬飛，丁韻青，張鶴于，鄭天洋

(西安電子科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

由圖形處理器(Graphics Prdessing Unit，GPU)、數(shù)字信號處理器(Digital Signal Processpr，DSP)、現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)等計算資源構(gòu)建的異構(gòu)計算平臺[1]，通過將不同屬性的計算任務(wù)調(diào)度到對應(yīng)的專用處理單元上來保證高性能計算需求[2-3]?；诋悩?gòu)計算平臺設(shè)計高效節(jié)能的任務(wù)資源管理調(diào)度方案，能夠最大限度地利用異構(gòu)計算資源，降低系統(tǒng)功耗，從而滿足不斷增長的計算需求[4-5]。

任務(wù)調(diào)度策略在資源利用上的微小優(yōu)化即可有效地減少任務(wù)執(zhí)行時間，大幅地降低服務(wù)成本[6]。因此，為了提高異構(gòu)計算平臺的任務(wù)調(diào)度效率并減少能耗，文獻[7]提出了基于蟻群算法的實時傳感器節(jié)點任務(wù)調(diào)度算法。文獻[8]提出了基于粒子群算法和遺傳算法的混合元啟發(fā)式算法，以最小化最大完工時間，提高資源利用率。異構(gòu)計算平臺的資源類型和組成結(jié)構(gòu)各異，導(dǎo)致基于啟發(fā)式思想的調(diào)度算法解集空間大、執(zhí)行時間長。強化學(xué)習(xí)[9]是當(dāng)下流行的機器學(xué)習(xí)方法，通過與環(huán)境不斷交互最大化累計獎勵，從而在解集空間中快速求解最優(yōu)策略[10]。目前已有許多利用強化學(xué)習(xí)算法思想來解決計算平臺上任務(wù)調(diào)度問題的實例。文獻[11]利用深度Q學(xué)習(xí)算法實現(xiàn)了單任務(wù)的在線調(diào)度。文獻[12]設(shè)計了一種基于強化學(xué)習(xí)和排隊理論的任務(wù)調(diào)度算法，通過對虛擬機狀態(tài)進行聚類減少狀態(tài)空間的維度。

上述的研究中，異構(gòu)計算平臺的調(diào)度策略大多依賴啟發(fā)式算法，而利用強化學(xué)習(xí)求解時，任務(wù)特征缺少多個任務(wù)的全局信息，導(dǎo)致模型訓(xùn)練不準(zhǔn)確。為此，筆者以最小化任務(wù)的平均完成時間為目標(biāo)設(shè)計了一種任務(wù)調(diào)度算法——JEDERL。JEDERL利用圖神經(jīng)網(wǎng)絡(luò)[13]對異構(gòu)計算資源和任務(wù)狀態(tài)信息進行編碼，提取資源特征及任務(wù)的局部和全局特征，并基于深度確定性策略梯度算法(Deep Deterministic Policy Gradient，DDPG)[14]進行算法的設(shè)計與求解。

1 問題建模

以任務(wù)的復(fù)雜性、計算資源的異構(gòu)性、系統(tǒng)中不同計算資源的網(wǎng)絡(luò)傳輸開銷等特性為基礎(chǔ)，以最小化任務(wù)平均完成時間為目標(biāo)設(shè)計優(yōu)化模型。具體如下。

1.1 系統(tǒng)模型

(1)

(2)

1.2 優(yōu)化目標(biāo)

(3)

(4)

對于單個任務(wù)Gv，其完成時間即為其子任務(wù)實際完成時間的最大值為

(5)

各個任務(wù)完成時間之和記為TSys：

(6)

以最小化任務(wù)的平均完成時間為目標(biāo)，優(yōu)化目標(biāo)模型如下所示：

(7)

式(7)所示的約束條件為，任意子任務(wù)實際開始時間大于其前繼子任務(wù)實際完成時間；任意子任務(wù)所用的計算資源不是同一個，即一個計算資源在某一時刻只能處理一個子任務(wù)。

2 面向異構(gòu)計算平臺的任務(wù)調(diào)度算法設(shè)計

2.1 任務(wù)調(diào)度框架設(shè)計

結(jié)合圖神經(jīng)網(wǎng)絡(luò)與DDPG設(shè)計的基于異構(gòu)計算資源的任務(wù)調(diào)度框架如圖1所示。任務(wù)編碼模塊的圖神經(jīng)網(wǎng)絡(luò)負(fù)責(zé)處理就緒子任務(wù)，聚合任務(wù)特征，經(jīng)過3個不同層次的嵌入編碼后，智能體根據(jù)任務(wù)的局部特征和全局特征計算當(dāng)前系統(tǒng)中所有就緒子任務(wù)的執(zhí)行優(yōu)先級，產(chǎn)生待調(diào)度子任務(wù)；設(shè)備編碼模塊的圖神經(jīng)網(wǎng)絡(luò)聚合異構(gòu)計算平臺上的異構(gòu)計算資源特征；調(diào)度決策模塊將任務(wù)特征與計算資源特征作為輸入，輸出任務(wù)調(diào)度動作作用于環(huán)境中，生成獎勵更新神經(jīng)網(wǎng)絡(luò)參數(shù)，更新異構(gòu)計算資源可用性狀態(tài)，不斷迭代，直至模型收斂。

圖1 基于異構(gòu)計算資源的任務(wù)調(diào)度框架

2.2 可伸縮的任務(wù)狀態(tài)信息編碼

神經(jīng)網(wǎng)絡(luò)通常需要固定大小的向量作為輸入[15]。因此，使用圖神經(jīng)網(wǎng)絡(luò)對任務(wù)狀態(tài)進行編碼[16]，將任務(wù)信息嵌入到一組向量中。具體的嵌入過程按層次執(zhí)行，如圖2所示。圖嵌入將任務(wù)的有向無環(huán)圖(Directed Acycic Graph，DAG)結(jié)構(gòu)(其節(jié)點帶有一組屬性)作為輸入，將3種不同類型且處于不同層次的嵌入作為輸出結(jié)果：

(1)子任務(wù)單元的嵌入收集當(dāng)前子任務(wù)節(jié)點及其祖先節(jié)點的信息，如圖2(a)所示；

(2)任務(wù)單元的嵌入聚合整個有向無環(huán)圖中所有子任務(wù)節(jié)點的信息，如圖2(b)所示；

(3)全局嵌入將所有任務(wù)的有向無環(huán)圖信息嵌入到一起，如圖2(b)所示。

(a)子任務(wù)單元嵌入編碼過程

(8)

2.3 基于DDPG的任務(wù)調(diào)度算法

基于異構(gòu)計算資源的任務(wù)調(diào)度框架如圖1所示，智能體接收到狀態(tài)信息的輸入，以獲得最大獎勵為目標(biāo)采取動作，與環(huán)境交互不斷更新狀態(tài)。具體的狀態(tài)、獎勵、動作定義如下。

獎勵(Reward)：基于DDPG算法單步更新的特點，獎勵函數(shù)為每一步更新提供一個即時的獎勵值。獎勵函數(shù)如式(9)所示，目標(biāo)是盡可能縮短任務(wù)平均完成時間：

(9)

動作(Action)：在關(guān)于就緒子任務(wù)選擇的動作探索中，假設(shè)在當(dāng)前時刻t，平臺系統(tǒng)中處于就緒狀態(tài)的子任務(wù)個數(shù)為nt，通過圖神經(jīng)網(wǎng)絡(luò)對每一個就緒子任務(wù)進行嵌入信息編碼后，就能得到關(guān)于這些就緒子任務(wù)的向量Vt，將就緒子任務(wù)的向量Vt轉(zhuǎn)換成可以表征選擇就緒子任務(wù)的概率向量Pt，之后智能體利用概率采樣的方式選擇每一步的動作，并通過環(huán)境給予的反饋來更新下次動作選擇的概率。

算法1基于DDPG的任務(wù)調(diào)度算法JEDERL。

輸入：待訓(xùn)練的策略網(wǎng)絡(luò)，訓(xùn)練任務(wù)信息，異構(gòu)計算平臺信息。

輸出：收斂的策略網(wǎng)絡(luò)。

① 隨機初始化在線critic網(wǎng)絡(luò)Q(s，a|θQ)和actor網(wǎng)絡(luò)μ(s，a|θμ)的參數(shù)θQ和θμ

② 初始化目標(biāo)網(wǎng)絡(luò)中的critic網(wǎng)絡(luò)Q′和actor網(wǎng)絡(luò)μ′：θQ′←θQ，θμ′←θμ

③ 初始化經(jīng)驗回放池M、隨機性噪聲pnoise等超參數(shù)

④ for episode=1，2，…，mdo

⑤s1=env.reset()

⑥ fort=1，2，…，tdo

3 實 驗

3.1 實驗環(huán)境及參數(shù)設(shè)置

使用5臺異構(gòu)服務(wù)器來構(gòu)建異構(gòu)計算平臺硬件環(huán)境，其中每種異構(gòu)計算資源包含多種計算類型，表示為DCPU={DCPU，1，DCPU，2，DCPU，3}，DGPU={DGPU，1，DGPU，2，DGPU，3}，DFPGA={DFPGA，1，DFPGA，2}，DDSP={DDSP，1，DDSP，2}，不同類型計算資源的計算能力存在差異。表1給出了每臺服務(wù)器上承載的異構(gòu)計算資源類型和數(shù)量。

表1 實驗使用的計算資源類型及數(shù)目

隨機生成25個不同拓?fù)浣Y(jié)構(gòu)的有向無環(huán)圖任務(wù)作為數(shù)據(jù)集，這些任務(wù)包含不同大小和計算類型的子任務(wù)個數(shù)共計501個。設(shè)置DDPG中actor網(wǎng)絡(luò)和critic網(wǎng)絡(luò)的學(xué)習(xí)率分別為0.001和0.005，目標(biāo)網(wǎng)絡(luò)的更新率β為0.01，訓(xùn)練的批數(shù)量大小為16；在計算critic網(wǎng)絡(luò)的未來獎勵時，設(shè)置折扣因子為0.9。

3.2 實驗結(jié)果與分析

將筆者提出的任務(wù)調(diào)度算法JEDERL與隨機調(diào)度、先進先出調(diào)度、輪盤法調(diào)度、短任務(wù)優(yōu)先調(diào)度以及基于設(shè)備嵌入的強化學(xué)習(xí)(Device Embedding Reinforcement Learning，DERL)算法進行對比。其中，隨機調(diào)度算法(Random)在每一時刻隨機選擇平臺上的某個就緒子任務(wù)進行調(diào)度；先進先出調(diào)度算法(FIFO)執(zhí)行先到達的子任務(wù)；輪盤法調(diào)度算法(Roulette)按機器使用順序為子任務(wù)分配執(zhí)行節(jié)點；短任務(wù)優(yōu)先調(diào)度算法(SJF)按任務(wù)大小排序，優(yōu)先調(diào)度小任務(wù)；DERL算法的實現(xiàn)參照文獻[17]，為未使用圖嵌入技術(shù)對就緒子任務(wù)進行編碼的基于DDPG的任務(wù)調(diào)度算法，將其與文中提出的算法進行對比，作為消融實驗[18]。

對使用不同算法時任務(wù)的平均完成時間和最大完成時間進行對比分析，實驗結(jié)果如圖3所示。其中，橫坐標(biāo)為任務(wù)的編號，縱坐標(biāo)為任務(wù)的完成時間，圖中虛線表示任務(wù)的平均完成時間，實線表示任務(wù)的最大完成時間。由圖3可以得到，JEDERL的任務(wù)平均完成時間相較于Random算法減少約27.8%，相較于先進先出調(diào)度算法減少約12.6%，相較于Roulette算法減少約28.6%，相較于短任務(wù)優(yōu)先調(diào)度算法減少約 21.9%，相較于DERL算法減少約 5.3%；JEDERL的任務(wù)最大完成時間相較于Random算法減少約 26.9%，相較于FIFO算法減少約35.8%，相較于Roulette算法減少約49.3%，相較于SJF算法減少約 15.9%，相較于DERL算法減少約30.2%。實驗結(jié)果表明，筆者提出的JEDERL算法通過對任務(wù)與計算資源的優(yōu)化表征，可伸縮狀態(tài)信息編碼有效地提取了任務(wù)與資源的全局信息，使得任務(wù)以更好的順序匹配到合適的計算資源，充分利用異構(gòu)計算資源算力，從而有效減少了任務(wù)的平均完成時間和最大完成時間。

(a)隨機調(diào)度

為了驗證JEDERL算法的穩(wěn)定性，進一步對比不同算法在任務(wù)數(shù)量、服務(wù)器數(shù)量變化時任務(wù)平均完成時間的大小。圖4中的實驗結(jié)果表明，當(dāng)服務(wù)器數(shù)量確定時，任務(wù)平均完成時間隨任務(wù)數(shù)量的增加而增加，這是由于有限的資源可以同時處理的任務(wù)量受限，造成任務(wù)堆積；在同一任務(wù)數(shù)量下，任務(wù)平均完成時間隨服務(wù)器數(shù)量的增加有所減少，原因在于服務(wù)器數(shù)量的增加使得同一時間有更多的資源被用于任務(wù)執(zhí)行，從而減少任務(wù)平均完成時間。將圖4中不同服務(wù)器個數(shù)下的任務(wù)平均完成時間做均值處理，JEDERL算法優(yōu)于Random算法約25.9%，優(yōu)于DERL算法約6.4%，即JEDERL算法能夠在變化的環(huán)境中保持其性能。

(a)平臺中服務(wù)器個數(shù)為5

4 結(jié)束語

根據(jù)異構(gòu)計算平臺的特性，以最小化任務(wù)平均完成時間為優(yōu)化目標(biāo)設(shè)計模型，筆者提出了一種基于深度確定性策略梯度算法的任務(wù)調(diào)度算法，并使用圖神經(jīng)網(wǎng)絡(luò)對有向無環(huán)圖任務(wù)和計算資源進行嵌入編碼，解決了異構(gòu)計算平臺上任務(wù)資源特征伸縮性差、缺少全局信息的問題。實驗結(jié)果表明，筆者提出的算法優(yōu)于隨機調(diào)度、先進先出調(diào)度、短任務(wù)優(yōu)先調(diào)度、輪盤法調(diào)度以及現(xiàn)有的強化學(xué)習(xí)調(diào)度算法。