云環境下基于強化學習的任務調度問題研究

陳新鵬，汪瑩

（四川大學計算機學院，成都610065）

0 引言

云計算作為一種新型的計算模式，提供了方便的訪問方式以及靈活資源擴展服務，日益受到用戶的歡迎，在互聯網高速發展的今天，云計算已經成為一項基礎服務，國內外眾多企業均布局云計算業務。其中國外較為知名的有亞馬遜與谷歌。亞馬遜云服務平臺較早投入商業使用，提供了以EC2 計算平臺以及S3 存儲平臺在內的多種云服務；谷歌隨后也開發了基于網絡應用程序的開發與托管的GAE（Google Application Engine）平臺。云計算作為一項戰略性新興技術，國內互聯網企業同樣十分重視，百度、阿里、騰訊和華為等知名互聯網公司均有可處理上億用戶服務請求能力的云計算平臺，并為國內外諸多公司提供了數據存儲、網站搭建、計算力支持等相關服務，很大程度上推動了國內互聯網技術的發展。

云計算為用戶提供了方便快捷且可擴展的計算能力支持，而合理利用云計算提供的計算能力則需要優秀的任務調度算法來完成。作為計算任務與云端資源的映射處理算法，直接關系到了云服務質量的優劣，具有很大的經濟和社會效益，因此云環境下的任務調度算法受到了廣泛的關注，十余年來一直是云計算領域的熱點問題。云環境下的任務調度問題已被證明屬于NP-Hard 問題，無法在多項式時間內求得最優解。傳統的調度算法通常利用任務與云環境中的相關信息，如計算節點的CPU 頻率、RAM 容量，或是任務依賴關系等，提供可接受的近似最優解，例如HEFT、MIN-MIN等算法。這類算法的特點是求解速度快速，并且結果具有可解釋性，但劣勢是往往存在比較大的優化空間。使用啟發式算法是另一種解決任務調度問題的思路，其中典型的有模擬自然界優勝劣汰的遺傳算法，模擬螞蟻搜索食物的蟻群算法以及模擬群體協作的粒子群算法。進化算法將任務調度的可能方案編碼成染色體，設計對應的適應度函數，通過初始化種群，染色體雜交等操作，通過模擬自然環境下的生物進化，最終獲得具有最佳適應度的解。蟻群算法和粒子群則是通過仿照仿生學方式，模擬螞蟻和鳥群在自然環境中的覓食行為，在任務調度的可行解空間中搜索較優解。

近年來，隨著人工智能技術的發展，人們嘗試使用強化學習來解決任務調度問題。Alexandru 等人[1]利用Q-Learning 等算法研究了異構計算集群下的任務調度問題。Wu 等人[2]嘗試深度強化學習技術解決具有依賴關系的任務調度問題。然而這些算法多考慮的是資源相對簡單且靜態的集群環境，對于云計算中基于資源異構的虛擬環境下任務考慮不多，本文基于蒙特卡洛策略迭代的強化學習的方式對云環境下任務調度進行問題進行了研究，實驗結果表明，基于強化學習的任務調度算法較傳統算法有一定優勢。

1 模型介紹與問題定義

1.1 云計算任務模型

考慮到并行計算任務之間具有執行邏輯或是數據傳遞的依賴關系，通常使用有向無環圖DAG 來表示云計算任務以及任務依賴，如圖1 所示。

圖1 包含10個任務的DAG圖

DAG 任務圖G 由二元組G=＜T，E＞組成，其中T是圖節點的集合，由圖中t1, t2,…, tn組成。每個節點都代表一個由一組計算指令構成的任務，其下的數字代表此任務的計算成本，通常是以MIPS（百萬指令）為單位的任務指令長度。E 是圖中有向邊的集合，有向邊eij表示任務tj依賴任務ti，也即ti需要tj執行完畢后才可運行。有向邊上的權重cij代表任務ti與任務tj之間需要傳輸的數據量，通常以MB（百萬字節）為單位。當tj依賴任務ti時，我們稱tj是ti的前驅任務，反之稱ti是tj的后繼任務。一個任務可能存在多個前驅任務和后繼任務，我們使用集合Pred( ti)={tp|tp∈T,epi∈E}表示任務ti的前驅任務集合。同樣地，有集合Succ( ti)={tc|tc∈T, eic∈E} 表 示 任 務ti的 后 繼 任 務集合。

在本文中，DAG 圖入度為0 的節點表示整個計算任務的入口節點，用tEntry表示；對應地，DAG 中出度為0 的節點則表示計算任務的出口節點，用tExit表示。對于一些任務圖而言，可能存在多個入度為0 的或出度為0 的節點，為了方便描述與調度程序進行處理，我們通過為多個入度為0 的節點添加共同前驅任務、多個出度為0 的節點添加共同后繼任務的方式，將DAG 任務圖的前驅和后繼任務唯一化。添加的前驅或后繼任務，計算成本與傳輸數據均置零，因此不影響實際的調度結果。

1.2 云計算虛擬機模型

本文研究的問題中，云計算虛擬機是指在云數據中心上分配的一系列具有不同資源數量的虛擬機。云服務提供商通常根據不同的用戶需求，制定若干種具有不同資源的虛擬機，按照一定規則制定售價，擁有更高參數的虛擬機售價越高。考慮到本文中計算任務模型，我們主要關注每個虛擬機的三個參數：計算能力，帶寬和價格，分別用scpu，sbw，scost表示。集合S={，，，，，，…，}表示虛擬機資源的集合。虛擬機的資源設置參考亞馬遜云平臺在售虛擬機配置，如表1 所示。

表1 Amazon Cloud EC2 平臺虛擬機配置參數

1.3 問題定義

云環境中具有依賴關系的任務的調度問題可以描述為：存在n 個互相依賴的任務t1, t2,…, tn與m 臺虛擬機s1, s2,…, sm，每個任務ti均有計算成本與結果數據兩個參數，表示任務ti的計算指令數與計算結束后產生的結果文件大小，且任務之間存在依賴關系。每臺虛擬機si均有計算處理速度，網絡通信帶寬與單位時間花費三個參數，且存在以下約束關系：

（1）任務ti在虛擬機sk上的執行時間為：

（2）任務ti向其后繼任務Succ(ti)傳遞數據的時間花費為：

（3）任務ti必須等待所有前驅任務Pr ed(ti)數據均傳遞完成，才可運行。

定義任務ti在sk上的最早開始執行時間為：

任務最早完成時間為：

其中，dji是ti的前驅任務tj向ti傳輸數據所消耗的時間。

定義任務ti在sk上的實際開始執行時間為：

任務的實際完成時間為：

總的任務完成時間（makespan）為：

2 基本理論與算法

強化學習（Reinforcement Learning）是機器學習領域的一個分類，其顯著特點是，強化學習需要使用標注好的數據，而是通過智能體與環境交互，進行探索式的學習。強化學習以馬爾科夫決策過程為基礎，馬爾科夫決策過程的特點是，系統從當前狀態轉換到下一狀態的概率分布僅和當前狀態有關，而與歷史狀態無關。基于強化學習的馬爾科夫決策過程由一個四元組組成：

{S,A,P(st,at,st+1),r(st,at),st,st+1∈S,at∈A}

其中，S 為狀態空間，對應于任務調度中虛擬機與未調度任務的狀態集合，A 為動作空間，在任務調度中為將任意任務t 安排到任意虛擬機s 中的所有可能的集合。P(st,at,st+1)是指任務調度系統處在狀態st時，執行完調度動作at后，轉移到下一狀態st+1的狀態轉移概率。r(st,at)為調度系統處于狀態st時執行調度動作at獲得到的獎勵。

本文使用蒙特卡洛策略梯度的方式進行強化學習，狀態空間S 在時間步τ表示為：

Sτ=[n,EST(s1,ti),…, EST(sm,ti),wi,1,…,wi,m)]

動作空間在時間步τ表示為：

Aτ={si|s1,s2,…,sm}

實驗不設置單步獎勵，只在所有任務調度結束后為智能體提供獎勵，值為：

Rround= makespanHEFT-makespanRL

即使用HEFT 算法與智能體調度完成時間的差值。

3 實驗結果與分析

本文的目標是云環境下的任務調度算法研究，由于在實際的云環境中進行任務執行并評估調度較為昂貴，且此研究方向具有學術界較為認可的仿真實驗環境，因此本文利用仿真實驗進行算法性能驗證。云環境以及任務調度仿真使用澳大利亞墨爾本大學開源的CloudSim 仿真實驗平臺[3]，計算任務參數，如內存、執行任務長度，任務數據依賴等，則參考航空發動機燃燒數值仿真實驗平臺OpenFOAM 中的典型計算任務特征，并配合使用DAG 圖生成工具隨機生成。

圖2 基于HEFT CPOP RL 的調度時長對比

實驗結果表明，基于強化學習的任務調度策略能夠以更短的計算時間完成所有計算任務。通過分析實際調度動作，可以發現強化學習智能體更傾向于將關鍵路徑上的任務更多的安排到高性能虛擬機上，從而實現了比HEFT/CPOP 調度算法[4]更短的完成時間。

4 結語

本文介紹了云環境下任務調度問題中云計算數據中心計算節點以及任務模型，并對云環境下最小化任務完成時間的調度問題進行了定義。同時分析了使用深度強化學習進行任務調度分配的可行性，給出了基于深度強化學習的方法實現的云環境下任務調度算法，最后基于CloudSim 平臺編程實現了仿真條件下的算法測試。對比經典的HEFT 調度算法，基于深度強化學習的調度算法能夠在更短的任務時間進行云計算環境中的任務調度，具有一定的實際意義。