基于深度強化學(xué)習(xí)改進(jìn)的任務(wù)調(diào)度算法

葉芳澤，沈 煒

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

0 引言

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

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

近年來機器學(xué)習(xí)被成功應(yīng)用于一些非常具有挑戰(zhàn)性的決策控制領(lǐng)域其中就包括調(diào)度算法[4]，而機器學(xué)習(xí)中的深度強化學(xué)習(xí)既能利用深度學(xué)習(xí)捕獲環(huán)境的特征，也能利用強化學(xué)習(xí)適應(yīng)復(fù)制多變的調(diào)度場景[5]，越來越多的文獻(xiàn)和實驗也表明深度強化學(xué)習(xí)在調(diào)度領(lǐng)域有著巨大的潛力。

隨著系統(tǒng)調(diào)度任務(wù)不斷增多，調(diào)度過程也變得復(fù)雜，傳統(tǒng)強化學(xué)習(xí)算法中的狀態(tài)空間與動作空間呈指數(shù)式增長，在訓(xùn)練過程中通常會出現(xiàn)訓(xùn)練時間長，學(xué)習(xí)效率低，結(jié)果不易收斂等問題。針對上訴問題，本文提出一種基于動作分支架構(gòu)[6]改進(jìn)的深度強化學(xué)習(xí)調(diào)度算法：利用分支策略網(wǎng)絡(luò)分解動作空間，并用全局的評論家網(wǎng)絡(luò)評估聯(lián)合動作的優(yōu)劣。實驗表明改進(jìn)的算法在仿真的Spark 調(diào)度系統(tǒng)中，有著更好的調(diào)度性能。

1 深度強化學(xué)習(xí)

1.1 深度強化學(xué)習(xí)簡介

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

圖1 強化學(xué)習(xí)示意圖

1.2 A3C算法

A3C 是一種基于策略的深度強化學(xué)習(xí)算法，結(jié)合了policy gradient 和動態(tài)規(guī)劃的優(yōu)勢，當(dāng)系統(tǒng)給定一個初始的環(huán)境狀態(tài)s1，算法根據(jù)策略θ 輸出動作a1的概率為pθ(a1|s1)，通過執(zhí)行動作a1環(huán)境狀態(tài)變?yōu)閟2，并得到獎勵r1，此時狀態(tài)轉(zhuǎn)移概率為p(s2|s1,a1)。重復(fù)上訴步驟直到任務(wù)結(jié)束，將一次調(diào)度過程記為τ=s1,a1,s2,a2,s3,a3…sT,aT。可以求出該調(diào)度過程發(fā)生的概率為：pθ(τ)=并得到累計獎勵：，將兩式相乘得到更新策略的目標(biāo)公式：。最后根據(jù)策略梯度公式(1)最大化我們得到的獎勵：

在訓(xùn)練過程中A3C 算法引入異步方法，利用CPU多線程機制同時執(zhí)行多個智能體。在學(xué)習(xí)模型訓(xùn)練的任意時刻，并行的智能體會根據(jù)不同的學(xué)習(xí)策略與環(huán)境狀態(tài)進(jìn)行交互，有效去除了樣本間的關(guān)聯(lián)性。

2 基于動作分支架構(gòu)改進(jìn)的深度強化學(xué)習(xí)調(diào)度算法

2.1 基于Spark的集群任務(wù)調(diào)度模型

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

圖2 spark系統(tǒng)作業(yè)示意圖

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

圖3 調(diào)度示意圖[3]

2.2 算法設(shè)計

2.2.1 基于圖嵌入的狀態(tài)空間預(yù)處理

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

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

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

2.2.2 基于動作分支的深度強化學(xué)習(xí)調(diào)度算法

基于動作分支架構(gòu)的思想，本文將傳統(tǒng)的單策略網(wǎng)絡(luò)分解為兩個動作分支網(wǎng)絡(luò)：①執(zhí)行階段策略網(wǎng)絡(luò)，確定待調(diào)度的執(zhí)行階段；②執(zhí)行器策略網(wǎng)絡(luò)，確定上訴階段應(yīng)該分配的執(zhí)行器數(shù)量。最后使用一個共享的評論家網(wǎng)絡(luò)調(diào)整調(diào)度策略，整體架構(gòu)如圖5所示。為了確保執(zhí)行器動作網(wǎng)絡(luò)的輸出有效性，本文規(guī)定：執(zhí)行器動作網(wǎng)絡(luò)最少輸出一個執(zhí)行器，最多輸出空閑執(zhí)行器的數(shù)量；當(dāng)該執(zhí)行階段內(nèi)的剩余任務(wù)數(shù)量少于分配的執(zhí)行器數(shù)量時，多余的執(zhí)行器將繼續(xù)激活系統(tǒng)調(diào)度程序，直到系統(tǒng)中沒有可剩余可運行的任務(wù)。

圖5 基于動作分支架構(gòu)的調(diào)度算法模型

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

損失函數(shù)選擇是非常關(guān)鍵的，它是深度強化學(xué)習(xí)的核心部分之一，網(wǎng)絡(luò)模型在訓(xùn)練過程中使用TDerror 作為損失函數(shù),可以有效地找到最佳調(diào)度策略,Critic損失函數(shù)如下：

Actor損失函數(shù)如公式⑹所示：

3 實驗分析

3.1 實驗環(huán)境

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

3.2 訓(xùn)練

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

3.3 評估方法

本文選取了以下四個經(jīng)典的調(diào)度算法與第二章提出的算法（下文簡稱B-A3C）進(jìn)行對比。

⑴FIFO：Spark 默認(rèn)的調(diào)度算法，它以作業(yè)到達(dá)的先后順序進(jìn)行分配執(zhí)行器，并根據(jù)用戶請求為每個作業(yè)授予相同數(shù)量的執(zhí)行器。

⑵SJF-CP：根據(jù)作業(yè)的總工作量，優(yōu)先調(diào)度短作業(yè)，并在每個作業(yè)中優(yōu)先選擇關(guān)鍵路徑上的節(jié)點。

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

⑷A3C：僅使用一個策略網(wǎng)絡(luò)，在相同的訓(xùn)練時間內(nèi)比較算法的優(yōu)劣。

3.4 結(jié)果與分析

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

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

4 結(jié)論

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