JEDERL：一種異構計算平臺任務調度優化算法

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

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

由圖形處理器(Graphics Prdessing Unit，GPU)、數字信號處理器(Digital Signal Processpr，DSP)、現場可編程門陣列(Field Programmable Gate Array，FPGA)等計算資源構建的異構計算平臺[1]，通過將不同屬性的計算任務調度到對應的專用處理單元上來保證高性能計算需求[2-3]。基于異構計算平臺設計高效節能的任務資源管理調度方案，能夠最大限度地利用異構計算資源，降低系統功耗，從而滿足不斷增長的計算需求[4-5]。

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

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

1 問題建模

以任務的復雜性、計算資源的異構性、系統中不同計算資源的網絡傳輸開銷等特性為基礎，以最小化任務平均完成時間為目標設計優化模型。具體如下。

1.1 系統模型

(1)

(2)

1.2 優化目標

(3)

(4)

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

(5)

各個任務完成時間之和記為TSys：

(6)

以最小化任務的平均完成時間為目標，優化目標模型如下所示：

(7)

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

2 面向異構計算平臺的任務調度算法設計

2.1 任務調度框架設計

結合圖神經網絡與DDPG設計的基于異構計算資源的任務調度框架如圖1所示。任務編碼模塊的圖神經網絡負責處理就緒子任務，聚合任務特征，經過3個不同層次的嵌入編碼后，智能體根據任務的局部特征和全局特征計算當前系統中所有就緒子任務的執行優先級，產生待調度子任務；設備編碼模塊的圖神經網絡聚合異構計算平臺上的異構計算資源特征；調度決策模塊將任務特征與計算資源特征作為輸入，輸出任務調度動作作用于環境中，生成獎勵更新神經網絡參數，更新異構計算資源可用性狀態，不斷迭代，直至模型收斂。

圖1 基于異構計算資源的任務調度框架

2.2 可伸縮的任務狀態信息編碼

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

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

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

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

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

(8)

2.3 基于DDPG的任務調度算法

基于異構計算資源的任務調度框架如圖1所示，智能體接收到狀態信息的輸入，以獲得最大獎勵為目標采取動作，與環境交互不斷更新狀態。具體的狀態、獎勵、動作定義如下。

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

(9)

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

算法1基于DDPG的任務調度算法JEDERL。

輸入：待訓練的策略網絡，訓練任務信息，異構計算平臺信息。

輸出：收斂的策略網絡。

① 隨機初始化在線critic網絡Q(s，a|θQ)和actor網絡μ(s，a|θμ)的參數θQ和θμ

② 初始化目標網絡中的critic網絡Q′和actor網絡μ′：θQ′←θQ，θμ′←θμ

③ 初始化經驗回放池M、隨機性噪聲pnoise等超參數

④ for episode=1，2，…，mdo

⑤s1=env.reset()

⑥ fort=1，2，…，tdo

3 實 驗

3.1 實驗環境及參數設置

使用5臺異構服務器來構建異構計算平臺硬件環境，其中每種異構計算資源包含多種計算類型，表示為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給出了每臺服務器上承載的異構計算資源類型和數量。

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

隨機生成25個不同拓撲結構的有向無環圖任務作為數據集，這些任務包含不同大小和計算類型的子任務個數共計501個。設置DDPG中actor網絡和critic網絡的學習率分別為0.001和0.005，目標網絡的更新率β為0.01，訓練的批數量大小為16；在計算critic網絡的未來獎勵時，設置折扣因子為0.9。

3.2 實驗結果與分析

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

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

(a)隨機調度

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

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

4 結束語

根據異構計算平臺的特性，以最小化任務平均完成時間為優化目標設計模型，筆者提出了一種基于深度確定性策略梯度算法的任務調度算法，并使用圖神經網絡對有向無環圖任務和計算資源進行嵌入編碼，解決了異構計算平臺上任務資源特征伸縮性差、缺少全局信息的問題。實驗結果表明，筆者提出的算法優于隨機調度、先進先出調度、短任務優先調度、輪盤法調度以及現有的強化學習調度算法。