基于深度強化學習改進的任務調度算法

葉芳澤，沈 煒

(浙江理工大學信息學院，浙江 杭州 310018)

0 引言

近年來，云計算和大數據中心迅猛發展，全球數據量正呈爆炸式增長，數據成為當今社會增長最快的資源之一[1]。面對增長迅速又十分復雜的數據資源，傳統單臺高性能服務器的處理能力已經不能滿足大部分網絡服務和數據密集型應用的需求，取而代之的是商業服務器集群[2]。

目前主流的分布式集群計算框架通常使用簡單通用的啟發式調度算法。但是這類算法通常忽略了系統中作業之間的負載特性，放棄了潛在的性能優化[3]。如果想在分布式集群上使用啟發式調度算法去實現高效地調度，通常需要針對特定的應用場景設計一個簡化的調度模型，并在實驗中精心調整并測試出較好的性能。一旦應用場景發生改變，算法就必須重新設計與測試。

近年來機器學習被成功應用于一些非常具有挑戰性的決策控制領域其中就包括調度算法[4]，而機器學習中的深度強化學習既能利用深度學習捕獲環境的特征，也能利用強化學習適應復制多變的調度場景[5]，越來越多的文獻和實驗也表明深度強化學習在調度領域有著巨大的潛力。

隨著系統調度任務不斷增多，調度過程也變得復雜，傳統強化學習算法中的狀態空間與動作空間呈指數式增長，在訓練過程中通常會出現訓練時間長，學習效率低，結果不易收斂等問題。針對上訴問題，本文提出一種基于動作分支架構[6]改進的深度強化學習調度算法：利用分支策略網絡分解動作空間，并用全局的評論家網絡評估聯合動作的優劣。實驗表明改進的算法在仿真的Spark 調度系統中，有著更好的調度性能。

1 深度強化學習

1.1 深度強化學習簡介

深度強化學習的基礎是強化學習，其本質是通過智能體與環境的不斷交互，并在觀察其行為的結果后根據環境的變化得到相應的獎勵，以此調整自身的動作策略[7]。利用這種方式，可以學習如何改變自己的行為，以得到更大的獎勵，其數學模型可由馬爾可夫決策過程進行表示，具體形式可以用五元組表示為。其中，S表示智能體的狀態空間；A表示智能體的可選動作空間；P(s＇|s,a)表示當前狀態st下執行動作at后，轉移到下一狀態st+1的狀態轉移概率密度函數；r(st,at,st+1)表示當前狀態st執行動作at后轉移到下一狀態st+1的瞬時獎賞；γ(0 ＜γ＜1)，表示未來獎賞折扣因子，決策過程如圖1 所示。而深度強化學習是在強化學習的基礎上引入了深度學習中的神經網絡，利用其強大的感知能力為復雜系統的決策問題提供強有力的技術支持。

圖1 強化學習示意圖

1.2 A3C算法

A3C 是一種基于策略的深度強化學習算法，結合了policy gradient 和動態規劃的優勢，當系統給定一個初始的環境狀態s1，算法根據策略θ 輸出動作a1的概率為pθ(a1|s1)，通過執行動作a1環境狀態變為s2，并得到獎勵r1，此時狀態轉移概率為p(s2|s1,a1)。重復上訴步驟直到任務結束，將一次調度過程記為τ=s1,a1,s2,a2,s3,a3…sT,aT。可以求出該調度過程發生的概率為：pθ(τ)=并得到累計獎勵：，將兩式相乘得到更新策略的目標公式：。最后根據策略梯度公式(1)最大化我們得到的獎勵：

在訓練過程中A3C 算法引入異步方法，利用CPU多線程機制同時執行多個智能體。在學習模型訓練的任意時刻，并行的智能體會根據不同的學習策略與環境狀態進行交互，有效去除了樣本間的關聯性。

2 基于動作分支架構改進的深度強化學習調度算法

2.1 基于Spark的集群任務調度模型

本文通過模擬ApacheSpark 的調度過程來驗證算法的有效性[8]。Spark 為每個輸入系統中的作業(job)構建了一個有向無環圖(DAG)，如圖2 所示。DAG 中的每個節點(node)代表該作業的一個執行階段(stage)，是一個或多個父節點的輸出，當所有的父節點完成時，該節點才會被激活，并參與下次的調度計劃；每個節點內有數個可并行計算的任務(task)，任務是Spark執行計算的最小單元，一個任務代表一個本地計算，不可拆分，且只能在一個執行器(executor)上執行計算過程，通常一個階段的任務比執行器多，因此任務分幾個批次運行；調度程序(Scheduler)負責維護任務隊列，每次執行器空閑時，它都會從中分配任務。執行器是由Spark 根據用戶請求指派的，默認情況下，他們會一直運行直到系統中沒有作業。

圖2 spark系統作業示意圖

Spark 任務調度模塊主要包含兩大部分：DAGScheduler 和TaskScheduler。其中DAGScheduler 主要負責分析用戶提交的應用，并根據計算任務的依賴關系建立DAG，然后將DAG 劃分為不同的stage，并以TaskSet 的形式把Stage 提交給TaskScheduler。TaskScheduler負責TaskSet中task的管理調度工作，這些task的執行邏輯完全相同，只是作用于不同的數據。調度過程如圖3所示。

圖3 調度示意圖[3]

2.2 算法設計

2.2.1 基于圖嵌入的狀態空間預處理

圖嵌入算法可以在保留DAG 節點信息的同時將圖的結構信息一并映射到低維稠密的特征向量中。首先提取DAG 中每個節點的特征信息并將其表示成節點特征矩陣X，然后與鄰接矩陣A作為圖神經網絡的輸入，模型架構如圖4所示。

圖4 多層GCN圖嵌入模型[9]

在嵌入算法中使用多層GCN 層間傳播[10]，傳播公式如下：

2.2.2 基于動作分支的深度強化學習調度算法

基于動作分支架構的思想，本文將傳統的單策略網絡分解為兩個動作分支網絡：①執行階段策略網絡，確定待調度的執行階段；②執行器策略網絡，確定上訴階段應該分配的執行器數量。最后使用一個共享的評論家網絡調整調度策略，整體架構如圖5所示。為了確保執行器動作網絡的輸出有效性，本文規定：執行器動作網絡最少輸出一個執行器，最多輸出空閑執行器的數量；當該執行階段內的剩余任務數量少于分配的執行器數量時，多余的執行器將繼續激活系統調度程序，直到系統中沒有可剩余可運行的任務。

圖5 基于動作分支架構的調度算法模型

當系統出現以下幾種情況：①一個階段用完任務(即不再需要更多的執行器)；②一個階段完成，解鎖它的一個或多個子階段的任務；③一個新的作業到達系統。系統便會激活調度程序開始新的調度過程，調度程序通過將上文計算得到的圖嵌入特征向量分別輸入執行階段策略網絡、執行器策略網絡和評論家網絡，并輸出待調度的節點、每個節點應該分配的執行器數量和期望獎勵值。每完成一次執行器分配，系統會根據任務的到達時間、完成時間等數據計算此次調度得到的獎勵。每當完成一輪完整的調度，系統根據公式⑵更新策略網絡。

損失函數選擇是非常關鍵的，它是深度強化學習的核心部分之一，網絡模型在訓練過程中使用TDerror 作為損失函數,可以有效地找到最佳調度策略,Critic損失函數如下：

Actor損失函數如公式⑹所示：

3 實驗分析

3.1 實驗環境

本次實驗采取ubuntu 下的TensorFlow 深度學習框架，使用Pycharm 軟件進行程序編寫，實驗平臺的配置如下：CPU 為Intel(R) Pentium(R) CPU G3260 @3.30 GHz，GPU為NVIDIA GTX 6G，1 TB硬盤。

3.2 訓練

為了評估算法的有效性，我們使用文獻[3]提供的TPC-H 查詢數據，從六個不同數據量(2,5,10,20,50,100SF)的全部22 個TPC-H 查詢中隨機抽樣，輸入Spark 調度系統。系統初始狀態為一個查詢作業，15個任務執行器。訓練開始時每間隔一段隨機時間從數據集中獲取20 個查詢作業組成一個批次輸入系統等待調度，共計100個批次，為了模擬系統在高負載下的調度性能，要求這100 個作業批次在規定時間內按泊松分布全部推送至系統，共計訓練5000輪。

3.3 評估方法

本文選取了以下四個經典的調度算法與第二章提出的算法（下文簡稱B-A3C）進行對比。

⑴FIFO：Spark 默認的調度算法，它以作業到達的先后順序進行分配執行器，并根據用戶請求為每個作業授予相同數量的執行器。

⑵SJF-CP：根據作業的總工作量，優先調度短作業，并在每個作業中優先選擇關鍵路徑上的節點。

⑶Tetris*：基于Teris 算法，平衡短期作業偏好和資源利用率得到一個綜合評分，以此分配執行器。

⑷A3C：僅使用一個策略網絡，在相同的訓練時間內比較算法的優劣。

3.4 結果與分析

表1 展示了在不同的執行器數量下，各個算法的平均作業完成時間。從表1 中的數據得知，隨著執行器數量的增加，平均作業完成時間逐漸減少。其中當執行器數量較少時，兩種深度強化學習算法的平均作業完成時間明顯低于其他算法。當執行器數量達到29 及以上時Tetris*算法的性能優于A3C 算法。由此可以推測在只訓練5000輪的情況下，A3C 算法不能合理分配空閑的執行器，而B-A3C算法得益于分支動作架構的存在，可以在較短的時間內習得更為高效的調度策略。

表1 平均任務完成時間(單位：秒)

4 結論

針對強化學習傳統的單策略網絡在復雜的調度系統中無法快速、高效地探索動作空間的問題，本文提出了一種基于動作分支架構的強化學習算法模型，通過將一個完整的調度動作分解為兩個分支動作，有效地減小了各個分支的動作空間，提高了探索效率。最后通過實驗證明在仿真的Spark 調度模型中，相較于傳統的調度算法、啟發式算法和單策略網絡的強化學習，該算法能有效的提升系統的調度性能。