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

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

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

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

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

1 問題建模

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

1.1 系統(tǒng)模型

(1)

(2)

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

(3)

(4)

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

(5)

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

(6)

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

(7)

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

(9)

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

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

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

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

① 隨機(jī)初始化在線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)驗(yàn)回放池M、隨機(jī)性噪聲pnoise等超參數(shù)

④ for episode=1，2，…，mdo

⑤s1=env.reset()

⑥ fort=1，2，…，tdo

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

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

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

表1 實(shí)驗(yàn)使用的計(jì)算資源類型及數(shù)目

隨機(jī)生成25個(gè)不同拓?fù)浣Y(jié)構(gòu)的有向無環(huán)圖任務(wù)作為數(shù)據(jù)集，這些任務(wù)包含不同大小和計(jì)算類型的子任務(wù)個(gè)數(shù)共計(jì)501個(gè)。設(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；在計(jì)算critic網(wǎng)絡(luò)的未來獎(jiǎng)勵(lì)時(shí)，設(shè)置折扣因子為0.9。

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

(a)平臺(tái)中服務(wù)器個(gè)數(shù)為5

4 結(jié)束語

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