王立紅 張延華 孟德彬 李萌

(北京工業(yè)大學(xué)信息學(xué)部 北京 100124)

0 引言

云計(jì)算是近年來(lái)興起的一種新的商業(yè)模式,通過(guò)構(gòu)建具有強(qiáng)大計(jì)算能力的計(jì)算資源池,為企業(yè)、組織和個(gè)人提供按需、低成本的計(jì)算、帶寬等共享資源服務(wù)[1]。云計(jì)算技術(shù)的快速發(fā)展也使得數(shù)據(jù)中心在工業(yè)互聯(lián)網(wǎng)和物聯(lián)網(wǎng)技術(shù)中的核心地位越來(lái)越高[2]。隨著云數(shù)據(jù)中心數(shù)量和規(guī)模的增長(zhǎng),大量的電力消耗和能源消耗無(wú)疑成為各國(guó)面臨的嚴(yán)峻挑戰(zhàn)。根據(jù)自然資源保護(hù)委員會(huì)的報(bào)告,數(shù)據(jù)中心目前消耗了全球約7% 的電力,能耗預(yù)計(jì)每年將超過(guò)1400 億千瓦時(shí)。

云數(shù)據(jù)中心的能源消耗主要來(lái)自2 部分,即信息技術(shù)服務(wù)系統(tǒng)和基礎(chǔ)設(shè)施系統(tǒng)[3]。其中,物理服務(wù)器在數(shù)據(jù)中心的能耗中占比最大。值得注意的是,服務(wù)器的能源效率很大程度上取決于計(jì)算資源的使用情況,例如處理器的利用率[4]。另外,云環(huán)境中工作負(fù)載是隨機(jī)且高度動(dòng)態(tài)變化的,這些大批量的任務(wù)需要被分配給合適的節(jié)點(diǎn)處理。因此,進(jìn)行有效的任務(wù)調(diào)度是提高服務(wù)器資源利用率的一種較為合適的方法。它可以提高服務(wù)器的能效,減少服務(wù)器的空閑運(yùn)行,避免能源浪費(fèi),從而進(jìn)一步降低數(shù)據(jù)中心的最終能耗。

近來(lái)許多研究集中在云調(diào)度上。為了靈活管理大量的服務(wù)器資源和海量的任務(wù),數(shù)據(jù)中心采用虛擬化技術(shù),構(gòu)建多個(gè)虛擬機(jī)(virtual machine,VM)來(lái)執(zhí)行這些計(jì)算任務(wù)。云計(jì)算數(shù)據(jù)中心可以通過(guò)遷移和整合處理大量和短期工作的虛擬機(jī)來(lái)分配計(jì)算[5-6]。但是,這些方法不適合長(zhǎng)期和計(jì)算密集型任務(wù),因?yàn)檫w移會(huì)中斷任務(wù)執(zhí)行并導(dǎo)致移動(dòng)數(shù)據(jù)的開(kāi)銷。傳統(tǒng)上,各種元啟發(fā)式算法可以在一定條件下提供可行解。文獻(xiàn)[7]采用模擬退火方法實(shí)現(xiàn)云數(shù)據(jù)中心資源調(diào)度,以降低能耗。文獻(xiàn)[8]提出了一種改進(jìn)的粒子群優(yōu)化算法,該算法在平衡能源效率方面取得了良好的效果。為了考慮異構(gòu)資源,文獻(xiàn)[9]結(jié)合遺傳算法和粒子群算法的優(yōu)勢(shì)找到最優(yōu)資源調(diào)度方案,從而進(jìn)行能源優(yōu)化。然而,基于啟發(fā)式的方法只能處理相對(duì)穩(wěn)定的工作負(fù)載,且隨著工作負(fù)載的增加,該算法會(huì)導(dǎo)致高復(fù)雜度,從而增加了計(jì)算時(shí)間。

近年來(lái),深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning,DRL)作為傳統(tǒng)強(qiáng)化學(xué)習(xí)(reinforcement learning,RL)[10-12]方法的重要延伸,已廣泛應(yīng)用于解空間大的決策優(yōu)化和控制問(wèn)題,包括數(shù)據(jù)中心的能耗優(yōu)化問(wèn)題和資源調(diào)度問(wèn)題。在傳統(tǒng)的RL 系統(tǒng)中,代理通過(guò)迭代向環(huán)境發(fā)送動(dòng)作、監(jiān)控環(huán)境狀態(tài)以及評(píng)估標(biāo)量獎(jiǎng)勵(lì)以指導(dǎo)下一步動(dòng)作來(lái)與環(huán)境交互。代理的目標(biāo)是最大化累積獎(jiǎng)勵(lì)。在交互過(guò)程中,代理會(huì)構(gòu)建一個(gè)查找表,之后可以使用該查找表來(lái)根據(jù)環(huán)境狀態(tài)選擇一個(gè)動(dòng)作。但是,對(duì)于狀態(tài)空間和動(dòng)作空間大的優(yōu)化問(wèn)題,查找表的大小會(huì)非常大,不利于學(xué)習(xí)過(guò)程和模型性能。DRL 通過(guò)將表格替換為稱為深度Q 網(wǎng)絡(luò)(deep Q network,DQN) 的深度神經(jīng)網(wǎng)絡(luò)來(lái)解決此問(wèn)題。文獻(xiàn)[13]提出了一種深度強(qiáng)化學(xué)習(xí)方法實(shí)現(xiàn)了分布式數(shù)據(jù)中心的優(yōu)化選擇,有效降低了整體用戶成本。文獻(xiàn)[14]基于深度Q 學(xué)習(xí)的系統(tǒng),通過(guò)使用資源供應(yīng)和任務(wù)調(diào)度決策來(lái)最大限度地降低能源成本。文獻(xiàn)[15]提出DRL 模型來(lái)適應(yīng)服務(wù)級(jí)別協(xié)議目標(biāo),學(xué)習(xí)不同類型任務(wù)的固有特征,從而降低集群VM 的總使用成本和平均任務(wù)持續(xù)時(shí)間。這些方法都試圖利用DQN 卓越的在線和自主能力來(lái)解決云計(jì)算系統(tǒng)中的資源分配問(wèn)題,然而它們始終專注于提高DQN 的效率,而不是擴(kuò)展對(duì)不同工作負(fù)載變化的適應(yīng)性。當(dāng)這種變化持續(xù)發(fā)生時(shí),DQN 類型的方法是不夠的,這是因?yàn)樾枰獙?duì)所有可能的動(dòng)作生成Q 值。

為此,本文將在線任務(wù)調(diào)度表述為一個(gè)有約束的動(dòng)態(tài)優(yōu)化問(wèn)題,然后采用深度確定性策略梯度(deep deterministic policy gradient,DDPG)算法將連續(xù)的任務(wù)請(qǐng)求調(diào)度到合適的VM。具體來(lái)說(shuō),動(dòng)態(tài)變化的工作負(fù)載到達(dá)數(shù)據(jù)中心后,經(jīng)準(zhǔn)入控制策略進(jìn)入任務(wù)隊(duì)列;并在隊(duì)列中進(jìn)行優(yōu)先級(jí)排序之后,調(diào)度器采用DDPG 網(wǎng)絡(luò),將任務(wù)和VM 的信息作為代理的狀態(tài);將給任務(wù)分配的VM 作為動(dòng)作,任務(wù)的響應(yīng)時(shí)間和云數(shù)據(jù)中心能耗作為獎(jiǎng)勵(lì)函數(shù),自適應(yīng)地為實(shí)時(shí)任務(wù)分配VM。

本文的結(jié)構(gòu)安排如下。第1 節(jié)介紹本文的系統(tǒng)模型;第2 節(jié)詳細(xì)介紹本文所采用的在線任務(wù)調(diào)度策略;第3 節(jié)評(píng)估了所提出的算法并對(duì)仿真結(jié)果進(jìn)行討論和分析;第4 節(jié)對(duì)本文工作進(jìn)行了總結(jié)。

1 系統(tǒng)模型及問(wèn)題表述

如圖1 所示,本文研究的系統(tǒng)模型包含3 部分,分別為用戶工作負(fù)載模型、云環(huán)境模型和任務(wù)調(diào)度模型。根據(jù)系統(tǒng)模型,將在線任務(wù)調(diào)度問(wèn)題表述為一個(gè)有約束的多目標(biāo)優(yōu)化問(wèn)題。

圖1 系統(tǒng)模型

1.1 用戶工作負(fù)載模型

工作負(fù)載即用戶向數(shù)據(jù)中心提交包括中央處理器(central processing unit,CPU)、內(nèi)存、存儲(chǔ)、帶寬等資源需求。假設(shè)用戶提交的請(qǐng)求是相互獨(dú)立的,并且有以下特點(diǎn):(1)每個(gè)請(qǐng)求都被視為一個(gè)完整的任務(wù),不能進(jìn)一步拆分為更小的任務(wù);(2)每項(xiàng)任務(wù)僅可由一臺(tái)VM 完全完成;(3)在任何時(shí)候,每個(gè)VM 要么空閑,要么只執(zhí)行一項(xiàng)任務(wù);(4)任務(wù)間沒(méi)有通信或依賴關(guān)系。具體來(lái)說(shuō),用戶任務(wù)由其到達(dá)時(shí)間、計(jì)算能力和服務(wù)質(zhì)量(quality of service,QoS)(例如用戶請(qǐng)求截止時(shí)間)定義。通過(guò)這種方式,可以將任務(wù)形式化為六元組:

其中,Taskj指代到達(dá)的第j個(gè)任務(wù),是任務(wù)j到達(dá)時(shí)間,lenj是任務(wù)j的長(zhǎng)度,uj是處理任務(wù)j對(duì)CPU 的需求,mij是計(jì)算任務(wù)j需要的指令數(shù),dj是任務(wù)j硬截止時(shí)間,Ttypej是任務(wù)j類型(即I/O 或計(jì)算密集型)。

1.2 云環(huán)境模型

本文云環(huán)境模型簡(jiǎn)化為由VM 的建立、云能耗模型和VM 的釋放組成。構(gòu)建VM 模型,實(shí)現(xiàn)計(jì)算資源的提供;不同的VM,處理任務(wù)所需的能耗也不同,采用云能耗公式實(shí)現(xiàn)總能源成本的定量計(jì)算;最后,VM 空閑時(shí)及時(shí)釋放資源以達(dá)到節(jié)能的目的。

1.2.1 VM 模型

云數(shù)據(jù)中心的基礎(chǔ)設(shè)施依賴于資源虛擬化。映射虛擬化技術(shù)將許多物理服務(wù)器的計(jì)算資源劃分為獨(dú)立的隔離虛擬資源,從而實(shí)現(xiàn)資源池化。不同的VM 計(jì)算能力不同,功耗也不盡相同。因此,在本文的模型中,將每個(gè)VM 的屬性定義為一個(gè)四元組:

其中,VMi指代云數(shù)據(jù)中心的第i個(gè)VM,mipsi是VMi每秒執(zhí)行的指令數(shù),speedi是VMi接收用戶請(qǐng)求的速度,是VMi的靜態(tài)功耗,Vtypei是VMi的類型(即高I/O 或高計(jì)算型)。

1.2.2 云能耗公式

云計(jì)算環(huán)境中的VM 在任務(wù)到達(dá)之間存在一定的間隔,因此云環(huán)境的能量消耗會(huì)有一定的概率空閑。設(shè)是空閑概率,而1-則是VM 運(yùn)行的概率。因此,云環(huán)境的能量消耗是所有VM 的能耗之和,可以表示為

其中,Ui是VM 的CPU 利用率;ci是利用率的影響因素;bi是一個(gè)常數(shù),這意味著無(wú)論VM 有沒(méi)有任務(wù)運(yùn)行,都具有靜態(tài)功耗,取bi=,因?yàn)?當(dāng)Ui=0時(shí),

此外,式(3)還表明了能耗取決于任務(wù)在云環(huán)境中停留的時(shí)間,因此可以通過(guò)減少任務(wù)的響應(yīng)時(shí)間和提高CPU 的利用率來(lái)減少云數(shù)據(jù)中心的能源消耗。

1.2.3 VM 釋放

每個(gè)任務(wù)的運(yùn)行時(shí)間占用CPU 和內(nèi)存等資源的時(shí)間不是無(wú)限的,現(xiàn)實(shí)中會(huì)在進(jìn)程結(jié)束后自動(dòng)釋放。本文假設(shè)只有在任務(wù)完成后才能釋放VM。

1.3 任務(wù)調(diào)度模型

任務(wù)調(diào)度模塊由任務(wù)隊(duì)列(task queue,TQ)、狀態(tài)監(jiān)視器(status monitor,SM)和基于DDPG 的任務(wù)調(diào)度器構(gòu)成。

TQ 的功能主要是存儲(chǔ)用戶提交的請(qǐng)求并對(duì)其進(jìn)行優(yōu)先級(jí)排序。在每個(gè)時(shí)間窗口,用戶請(qǐng)求經(jīng)準(zhǔn)入控制策略被推送到隊(duì)列中,過(guò)度消耗資源或超過(guò)截止時(shí)間的任務(wù)會(huì)被拒絕。SM 分為任務(wù)監(jiān)視器和VM 監(jiān)視器,分別用來(lái)獲取任務(wù)和VM 的狀態(tài)信息,包括VM 的CPU 利用率、任務(wù)等待時(shí)間等。之后,這些狀態(tài)信息作為輸入發(fā)送到基于DRL 的任務(wù)調(diào)度器,輸出是任務(wù)-VM 分配方案。最后,任務(wù)調(diào)度器將TQ 中的任務(wù)推送到與該VM 關(guān)聯(lián)的緩沖隊(duì)列,將其分配給特定的VM 執(zhí)行。每輪分配后,TQ中的任務(wù)會(huì)被清空,為下一個(gè)時(shí)間窗口做準(zhǔn)備。

1.4 問(wèn)題表述

本文研究在保證服務(wù)質(zhì)量(QoS)的情況下減少云數(shù)據(jù)中心的能耗,為用戶提供服務(wù)。因此可將調(diào)度問(wèn)題表述為一個(gè)有約束的多目標(biāo)優(yōu)化問(wèn)題。

一旦任務(wù)開(kāi)始,任務(wù)的執(zhí)行就不能被中斷,即分配給忙碌VM 的任務(wù)將需要等待,直到所有先前分配的任務(wù)都已執(zhí)行。因此,任務(wù)j的響應(yīng)時(shí)間可以定義為

其中,Ttypej是任務(wù)j類型;Vtypei是VMi的類型;⊕是異或符號(hào),表示當(dāng)VM 類型和任務(wù)類型不同時(shí),CPU 處理速度會(huì)更低;mipsi是VMi每秒執(zhí)行的指令數(shù)。

由此,所有任務(wù)分配給VM 的平均響應(yīng)時(shí)間為

根據(jù)能耗模型可知,所有任務(wù)的能耗平均值為

基于上述公式,多目標(biāo)函數(shù)及其約束可以表述為

評(píng)估函數(shù)采用加權(quán)和的方法[16]來(lái)將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為具有權(quán)重的單個(gè)目標(biāo),該權(quán)重代表用戶在目標(biāo)之間的偏好。考慮到任務(wù)的響應(yīng)時(shí)間和VM 的能源消耗在數(shù)據(jù)規(guī)模上不統(tǒng)一,使用取對(duì)數(shù)的方法進(jìn)行標(biāo)準(zhǔn)化數(shù)據(jù)處理,最終定義任務(wù)調(diào)度評(píng)估函數(shù)為

其中,δ∈[0,1],為加權(quán)值系數(shù),表示用戶對(duì)響應(yīng)時(shí)間和能耗的關(guān)注度。

2 基于DDPG 的準(zhǔn)入動(dòng)態(tài)任務(wù)調(diào)度策略

針對(duì)云計(jì)算環(huán)境中工作負(fù)載的高度動(dòng)態(tài)性和多樣性的特點(diǎn),本文基于聯(lián)合優(yōu)化目標(biāo)函數(shù),提出DRL 方法對(duì)系統(tǒng)的任務(wù)調(diào)度進(jìn)行優(yōu)化,以獲取最小能源消耗。

2.1 準(zhǔn)入控制策略

基于準(zhǔn)入控制策略[17],調(diào)度器根據(jù)用戶的截止日期篩選任務(wù),只選擇可實(shí)現(xiàn)的任務(wù),而拒絕其他任務(wù)。具體來(lái)說(shuō),用戶提交任務(wù)之后,假設(shè)將其分配給云數(shù)據(jù)中心類型匹配的計(jì)算能力最強(qiáng)的VM 且無(wú)等待立即被執(zhí)行,若它仍不能在硬截止日期前完成,則請(qǐng)求應(yīng)被拒絕。根據(jù)服務(wù)級(jí)別協(xié)議,應(yīng)該滿足:

2.2 動(dòng)態(tài)任務(wù)優(yōu)先級(jí)

在大多數(shù)現(xiàn)有的基于DRL 的云任務(wù)調(diào)度策略中,用戶任務(wù)通常以先到先服務(wù)(first come first served,FCFS)的方式處理。但任務(wù)的順序不同,系統(tǒng)選擇的VM 就會(huì)不同,QoS 和能耗都會(huì)受到影響;另外,訓(xùn)練過(guò)程中探索階段對(duì)初始動(dòng)作的選擇會(huì)影響調(diào)度策略的收斂速度,為提高DRL 調(diào)度策略的運(yùn)行效率,可以在任務(wù)隊(duì)列對(duì)任務(wù)進(jìn)行動(dòng)態(tài)的優(yōu)先級(jí)排序。

僅僅依據(jù)某一方面的特征參數(shù)來(lái)排序是不夠的,本文綜合考慮了任務(wù)長(zhǎng)度和任務(wù)截止時(shí)間來(lái)設(shè)計(jì)優(yōu)先級(jí)。當(dāng)任務(wù)的長(zhǎng)度很短時(shí),優(yōu)先執(zhí)行可以盡快釋放VM 資源;離任務(wù)的截止時(shí)間很近時(shí),優(yōu)先執(zhí)行可以提高任務(wù)成功率。由此,任務(wù)的排序優(yōu)先級(jí)函數(shù)定義為

其中,lenj是任務(wù)的長(zhǎng)度;dj是任務(wù)j硬截止時(shí)間;ω∈[0,1],為加權(quán)值系數(shù),表示任務(wù)長(zhǎng)度和硬截止時(shí)間對(duì)優(yōu)先級(jí)的影響程度。當(dāng)ω取值很大且越接近于1 時(shí),任務(wù)長(zhǎng)度對(duì)優(yōu)先級(jí)的影響越大;ω越接近于0 時(shí),硬截止時(shí)間對(duì)優(yōu)先級(jí)影響越大,本文ω取值為0.5。

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

2.3.1 DRL 學(xué)習(xí)機(jī)制

RL 通常是基于馬爾可夫決策過(guò)程(Markov decision process,MDP)定義的,具有潛在的馬爾可夫性,即RL 決策僅依賴于直接從其經(jīng)驗(yàn)中學(xué)習(xí)而無(wú)需任何先驗(yàn)知識(shí)。然而,傳統(tǒng)的RL 算法無(wú)法處理高維的復(fù)雜狀態(tài)和動(dòng)作空間,因此作為深度學(xué)習(xí)(deep learning,DL)和RL 的結(jié)合,DRL 應(yīng)運(yùn)而生。DRL 的基本思想是在環(huán)境中設(shè)置一個(gè)代理,通過(guò)執(zhí)行動(dòng)作與環(huán)境進(jìn)行交互。代理將從環(huán)境中獲得獎(jiǎng)勵(lì),根據(jù)獎(jiǎng)勵(lì)改進(jìn)其行動(dòng)策略,并期望在下一步中獲得更多獎(jiǎng)勵(lì)[18]。代理的目標(biāo)是通過(guò)與環(huán)境交互來(lái)學(xué)習(xí)最優(yōu)策略π以最大化預(yù)期回報(bào)。

在時(shí)間t,代理觀察當(dāng)前系統(tǒng)的狀態(tài)st,采取行動(dòng)at,然后從環(huán)境反饋獲得即時(shí)獎(jiǎng)勵(lì)rt,之后系統(tǒng)進(jìn)入下一個(gè)狀態(tài)st+1。預(yù)期累計(jì)收益為

其中,γ∈[0,1]是折扣因子,表示對(duì)未來(lái)獲得獎(jiǎng)勵(lì)的重視程度,決定未來(lái)獎(jiǎng)勵(lì)如何轉(zhuǎn)換為當(dāng)前收益。

基于策略π,在狀態(tài)st的動(dòng)作at獲得的t時(shí)刻的最大期望獎(jiǎng)勵(lì)函數(shù)定義為動(dòng)作-價(jià)值函數(shù)Q,定義為

其中,Eπ[*] 表示數(shù)學(xué)期望,是針對(duì)環(huán)境中的所有隨機(jī)策略執(zhí)行的。

如果基于策略π的動(dòng)作-價(jià)值函數(shù)大于基于其他策略的Q 函數(shù),則策略π是最優(yōu)策略,對(duì)應(yīng)的Q函數(shù)是最優(yōu)動(dòng)作價(jià)值函數(shù)。

DRL 的最終目標(biāo)就是找到這個(gè)最優(yōu)策略:

據(jù)此,代理不斷通過(guò)下式迭代動(dòng)作-狀態(tài)值,表達(dá)式為

其中,α∈[0,1]為學(xué)習(xí)率,為下一狀態(tài)的最大動(dòng)作-狀態(tài)值。

在眾多DRL 算法中,應(yīng)用最廣泛的為DQN。盡管DQN 可以成功解決高維狀態(tài)空間中的問(wèn)題,但它只能處理離散和低維動(dòng)作空間。此外,DQN 還存在估計(jì)過(guò)高的缺陷,而Actor-Critic 方法存在收斂速度慢的問(wèn)題。為了解決上述問(wèn)題,本文提出了DDPG算法[19-20]。它的確定性策略可以提高效率,并且與DQN 的結(jié)合使訓(xùn)練過(guò)程易于收斂。因此,本文的在線任務(wù)調(diào)度算法是基于DDPG 的。

2.3.2 算法設(shè)計(jì)

基于DRL,分別設(shè)計(jì)和部署狀態(tài)空間、動(dòng)作空間、獎(jiǎng)勵(lì)設(shè)計(jì)、網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)訓(xùn)練。

(1)狀態(tài)空間

狀態(tài)空間是代理從當(dāng)前環(huán)境中觀測(cè)到的信息。在本文中,環(huán)境xt的狀態(tài)觀測(cè)由狀態(tài)監(jiān)視器提供,分為2 部分:對(duì)用戶任務(wù)的觀測(cè)和對(duì)VM 資源的觀測(cè)。假設(shè)環(huán)境是完全觀測(cè)的,則st=xt。此時(shí),任意時(shí)隙t的系統(tǒng)狀態(tài)定義為

(2)動(dòng)作空間

DRL 代理根據(jù)觀測(cè)的環(huán)境狀態(tài)信息以固定的間隔做出決策,從待處理的任務(wù)隊(duì)列中選擇合適的任務(wù)分配給某個(gè)VM。因此,動(dòng)作空間在時(shí)隙t處定義為

其中,ai,j(t)={0,1},如果ai,j(t)=1,則taskj分配給VMi。

(3)獎(jiǎng)勵(lì)設(shè)計(jì)

根據(jù)云系統(tǒng)模型和響應(yīng)時(shí)間與能耗最小化目標(biāo),并結(jié)合任務(wù)調(diào)度評(píng)估函數(shù),本文獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)為

其中,δ∈[0,1],和Ei,j(t) 分別是將taskj分配給VMi的任務(wù)響應(yīng)時(shí)間和在該VM 上的能量消耗。

(4)網(wǎng)絡(luò)結(jié)構(gòu)

在DDPG 中,因?yàn)椴捎肁ctor-Critic 架構(gòu),所以其由Actor 和Critic 2 個(gè)部分組成。此外,對(duì)于具有高維狀態(tài)和動(dòng)作空間的系統(tǒng),維護(hù)如此龐大的轉(zhuǎn)換表所消耗的計(jì)算量和存儲(chǔ)空間是無(wú)法接受的。因此,為從高維數(shù)據(jù)中獲取低維特征,DDPG 借鑒DQN的思想,采用深度神經(jīng)網(wǎng)絡(luò)(deep neural networks,DNN)通過(guò)調(diào)整網(wǎng)絡(luò)中的參數(shù)來(lái)逼近函數(shù)。Actor 網(wǎng)絡(luò)μ(s|θμ) ≈μ(s) 逼近策略函數(shù)μ,Critic 網(wǎng)絡(luò)Q(s,a|θQ) ≈Q(s,a) 逼近Q 函數(shù),其中,θ是神經(jīng)網(wǎng)絡(luò)的權(quán)重參數(shù)。最終DDPG 有Actor eval、Critic eval、Actor target 和Critic target 4 個(gè)神經(jīng)網(wǎng)絡(luò),網(wǎng)絡(luò)架構(gòu)如圖2,主要由評(píng)估網(wǎng)絡(luò)、目標(biāo)網(wǎng)絡(luò)和回放緩沖區(qū)3 個(gè)模塊組成。

圖2 DDPG 網(wǎng)絡(luò)架構(gòu)

代理從環(huán)境記憶庫(kù)中隨機(jī)抽取〈st,at,rt,st+1〉 存入回放緩沖區(qū)中,目的是打破訓(xùn)練時(shí)經(jīng)驗(yàn)學(xué)習(xí)的時(shí)間相關(guān)性。目標(biāo)網(wǎng)絡(luò)的輸出值分別為Q′ 和μ′,相應(yīng)函數(shù)的神經(jīng)網(wǎng)絡(luò)權(quán)重以如下方式緩慢更新。

其中,τ∈(0,1)是目標(biāo)網(wǎng)絡(luò)的學(xué)習(xí)率,通常τ ＜＜1。

本文的目標(biāo)是基于TD-error 最小化損失函數(shù),因此Critic eval 網(wǎng)絡(luò)的損失函數(shù)為

評(píng)估網(wǎng)絡(luò)中Actor 使用策略梯度函數(shù)進(jìn)行更新動(dòng)作:

(5)網(wǎng)絡(luò)訓(xùn)練

訓(xùn)練時(shí),為了增加探索的隨機(jī)性,增加策略函數(shù)的決策范圍,防止陷入局部最優(yōu),設(shè)置貪婪系數(shù)ε,根據(jù)概率ε隨機(jī)選擇動(dòng)作at。代理執(zhí)行動(dòng)作at并獲取即時(shí)獎(jiǎng)勵(lì)rt后,觀察下一狀態(tài)st+1,將經(jīng)驗(yàn)〈st,at,rt,st+1〉 存入環(huán)境記憶庫(kù)中,然后隨機(jī)抽取樣本容量B大小的經(jīng)驗(yàn)存放入回放緩沖區(qū),作為輸入傳進(jìn)行評(píng)估網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)計(jì)算Q 值,最后根據(jù)策略梯度函數(shù)和損失函數(shù)迭代更新,每隔一定訓(xùn)練步數(shù),降低貪婪系數(shù)ε,直至Q 值和損失函數(shù)曲線收斂,停止訓(xùn)練。在訓(xùn)練過(guò)程完全完成后,基于DRL 的調(diào)度方案在計(jì)算上將是輕量級(jí)的。

2.3.3 偽代碼

綜上,基于DDPG 的任務(wù)調(diào)度算法的偽代碼如算法1 所示。

算法中第(5)～(7)行為環(huán)境與代理的交互過(guò)程;第(8)～(9)行為利用經(jīng)驗(yàn)回放機(jī)制抽取樣本的訓(xùn)練過(guò)程;第(10)～(12)行為評(píng)估網(wǎng)絡(luò)的訓(xùn)練過(guò)程和目標(biāo)網(wǎng)絡(luò)參數(shù)的更新過(guò)程;第(5)行和第(13)行為利用貪婪系數(shù)ε經(jīng)固定訓(xùn)練步數(shù)平衡動(dòng)作偏好的選擇過(guò)程。

3 仿真實(shí)驗(yàn)及結(jié)果分析

本節(jié)首先介紹了仿真實(shí)驗(yàn)的環(huán)境和設(shè)置參數(shù),之后展示并比較分析了不同工作負(fù)載和不同調(diào)度策略下的仿真結(jié)果。

3.1 仿真環(huán)境與實(shí)驗(yàn)設(shè)置

本文仿真實(shí)驗(yàn)的硬件配置和軟件環(huán)境為@Intel Core i5 CPU 2.20 GHz,8 GB 內(nèi)存,Python3.8 和Py-Torch 1.0。

在云數(shù)據(jù)中心設(shè)置中,VM 數(shù)量設(shè)置為20,5 種類型,用于處理不同類型的任務(wù),包括計(jì)算密集型和I/O 密集型任務(wù)。任務(wù)數(shù)量設(shè)置為500 000,每個(gè)作業(yè)任務(wù)的長(zhǎng)度由正態(tài)分布控制。分布的均值和方差分別設(shè)置為150 和10。作業(yè)的到達(dá)時(shí)間由泊松分布控制,平均到達(dá)率λ選自{8,10,12,14,16}。在所提出DDPG 網(wǎng)絡(luò)中,2 個(gè)Actor 網(wǎng)絡(luò)的輸入層函數(shù)為tanh,輸出層利用ReLU 函數(shù)。Critic 網(wǎng)絡(luò)使用ReLU作為輸入激活函數(shù)并在輸出層采用線性激活函數(shù)。另外,在評(píng)估網(wǎng)絡(luò)中,使用自適應(yīng)矩估計(jì)(Adam)方法優(yōu)化網(wǎng)絡(luò)。Actor 和Critic 網(wǎng)絡(luò)的學(xué)習(xí)率分別設(shè)置為0.006 和0.008。在目標(biāo)網(wǎng)絡(luò)中,學(xué)習(xí)率τ設(shè)置為0.001。經(jīng)驗(yàn)回放緩沖區(qū)容量大小設(shè)置為1000。云環(huán)境中其他參數(shù)具體如表1 所示。

最后,通過(guò)大量實(shí)驗(yàn)來(lái)評(píng)估本文提出的任務(wù)調(diào)度策略。實(shí)驗(yàn)中選擇了5 種方法作為對(duì)比,包括隨機(jī)調(diào)度、輪循算法、貪婪算法、DQN 算法和DDPG 算法。并使用平均響應(yīng)時(shí)間、能耗和CPU 利用率標(biāo)準(zhǔn)差3 個(gè)指標(biāo)來(lái)評(píng)估調(diào)度策略的性能。

3.2 收斂性分析

為了驗(yàn)證DDPG 算法能夠更好更快地得到最優(yōu)解,本文通過(guò)觀察Actor 網(wǎng)絡(luò)的Q 值和Critic 網(wǎng)絡(luò)的Loss 值是否達(dá)到收斂來(lái)確定。

圖3 和圖4 分別展示了在不同到達(dá)率的條件下,訓(xùn)練期間評(píng)估網(wǎng)絡(luò)中Actor 網(wǎng)絡(luò)的Q 值和目標(biāo)網(wǎng)絡(luò)中Critic 網(wǎng)絡(luò)的Loss 值隨訓(xùn)練步數(shù)的變化曲線。對(duì)于Actor_Q_Value 來(lái)說(shuō),如果選擇的是一個(gè)正確的行為,則Q 值會(huì)不斷增加直至收斂不變。對(duì)于Critic_Q_loss 來(lái)說(shuō),損失代表了神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)空間。當(dāng)它變小時(shí),意味著神經(jīng)網(wǎng)絡(luò)在學(xué)習(xí),收斂代表學(xué)習(xí)完成。由圖3 和圖4 可看出,隨著迭代次數(shù)的增加,不同任務(wù)到達(dá)率的Q 值和Loss 值都在約5000 步的迭代次數(shù)時(shí)達(dá)到穩(wěn)定的收斂,表明訓(xùn)練結(jié)束且網(wǎng)絡(luò)輸出為最優(yōu)策略。

圖3 不同到達(dá)率下的Actor_Q_Value 值

圖4 不同到達(dá)率下的Critic_Q_Loss 值

圖5 展示了在相同到達(dá)率下DQN 算法和DDPG算法隨著訓(xùn)練步數(shù)的增加,其損失函數(shù)變化曲線對(duì)比圖。由圖5 可知,DDPG 算法比DQN 算法的Loss值更迅速地收斂。并且在這2 種算法都采用均方誤差計(jì)算損失函數(shù)的條件下,DDPG 算法的Loss 值更小,綜上說(shuō)明本文采用的DDPG 算法可以更快更準(zhǔn)確地找到最優(yōu)解。

圖5 DQN 和DDPG 算法的Q_Loss 值對(duì)比

3.3 結(jié)果對(duì)比分析

由于實(shí)驗(yàn)的隨機(jī)性,本文對(duì)不同到達(dá)率的每種算法進(jìn)行了10 次重復(fù)實(shí)驗(yàn),最后記錄了平均結(jié)果。

圖6 展示了用戶任務(wù)的到達(dá)率從8/s 增加到16/s 的5 種調(diào)度算法的平均響應(yīng)時(shí)間對(duì)比圖。由圖可知,各種算法的平均任務(wù)響應(yīng)時(shí)間隨到達(dá)率的增加都有不同程度的增加,這是因?yàn)楦叩牡竭_(dá)率意味著更多的用戶任務(wù)將在系統(tǒng)中排隊(duì)等待服務(wù)。

圖6 5 種調(diào)度算法的平均響應(yīng)時(shí)間對(duì)比

由圖6 的5 種算法的平均響應(yīng)時(shí)間對(duì)比可以看出,隨機(jī)任務(wù)算法產(chǎn)生的平均響應(yīng)時(shí)間最長(zhǎng)并且隨著到達(dá)率增加增長(zhǎng)得最快,原因是它將用戶提交的任務(wù)隨機(jī)分配給VM 而不考慮匹配性,可能會(huì)導(dǎo)致任務(wù)等待時(shí)間和處理時(shí)間都比較長(zhǎng)。同理,輪詢算法將任務(wù)依次分配給VM,響應(yīng)時(shí)間會(huì)因任務(wù)類型和VM 類型不匹配問(wèn)題而拉長(zhǎng)。貪婪算法的主要思想是根據(jù)任務(wù)的到達(dá)時(shí)間將任務(wù)分配給第一個(gè)空閑的VM,但過(guò)分強(qiáng)調(diào)每個(gè)單獨(dú)的任務(wù)可能不會(huì)導(dǎo)致所有任務(wù)的總體完成時(shí)間最短。相比之下,本文采用的DDPG 算法平均任務(wù)響應(yīng)時(shí)間最短。圖5 中,在到達(dá)率為16/s 時(shí),采用隨機(jī)算法的平均響應(yīng)時(shí)間為1.66 s,DQN 算法平均響應(yīng)時(shí)間為0.78 s,而DDPG 算法的平均響應(yīng)時(shí)間約為0.66 s,比隨機(jī)算法縮短了60%,比DQN 算法縮短了15%。這得益于將任務(wù)響應(yīng)時(shí)間作為獎(jiǎng)勵(lì)函數(shù)去訓(xùn)練和DDPG 算法處理高維度連續(xù)動(dòng)作空間問(wèn)題的優(yōu)越性。

圖7 展示了5 種調(diào)度算法在不同任務(wù)到達(dá)率下的系統(tǒng)總能耗對(duì)比圖。隨著到達(dá)率的增加,使用5種調(diào)度算法的系統(tǒng)總能耗都隨之增加。這是由于工作負(fù)載的增大,需要系統(tǒng)更多的資源和時(shí)間去處理任務(wù),根據(jù)能耗模型,系統(tǒng)能耗會(huì)隨之增加。觀察圖7可知,隨機(jī)調(diào)度算法和輪詢調(diào)度算法的總能耗最高且相差不大,這是由算法無(wú)需考慮任何因素快速將任務(wù)分配給VM 的特性決定的。顯然,基于DRL 調(diào)度的2 種算法總能耗最低。只有到達(dá)率為8/s 時(shí),DQN 的能耗低于DDPG 算法,之后的到達(dá)率,DDPG 能耗皆低于DQN,這表明DQN 更適合低負(fù)載的系統(tǒng)而DDPG 算法則更適合高負(fù)載的系統(tǒng),并且,工作負(fù)載越高,節(jié)能效果越顯著。

圖7 5 種調(diào)度算法的總能耗對(duì)比

圖8 展示了不同到達(dá)率、不同調(diào)度算法下系統(tǒng)VM 的CPU 利用率標(biāo)準(zhǔn)差。本文利用CPU 利用率的標(biāo)準(zhǔn)差來(lái)表征VM 之間的負(fù)載平衡。當(dāng)多個(gè)任務(wù)被頻繁地調(diào)度到同一VM 上,會(huì)導(dǎo)致其過(guò)度使用而其他VM 長(zhǎng)時(shí)間空閑,資源利用率低下。因此負(fù)載平衡也是評(píng)估調(diào)度策略好壞的一個(gè)重要指標(biāo)。由圖8可知,DDPG 算法的CPU 利用率標(biāo)準(zhǔn)差低于其他4 種算法,表明本文采用的DDPG 算法可以優(yōu)化系統(tǒng)的負(fù)載平衡。

圖8 5 種調(diào)度算法的CPU 利用率標(biāo)準(zhǔn)差對(duì)比

4 結(jié)論

本文研究了如何在滿足所有用戶的QoS 指標(biāo)下最大限度地減少云數(shù)據(jù)中心的能耗。為了解決這個(gè)問(wèn)題,提出了一種基于DDPG 的節(jié)能任務(wù)調(diào)度策略,所提出的策略分為3 個(gè)過(guò)程,即準(zhǔn)入控制、動(dòng)態(tài)優(yōu)先級(jí)排序和基于DDPG 網(wǎng)絡(luò)的任務(wù)調(diào)度。采用DDPG 網(wǎng)絡(luò)尋找最優(yōu)任務(wù)分配解決方案,將用戶提交的任務(wù)和VM 關(guān)鍵信息作為狀態(tài)輸入,聯(lián)合考慮任務(wù)的響應(yīng)時(shí)間和系統(tǒng)能耗2 大指標(biāo)作為獎(jiǎng)勵(lì)函數(shù)訓(xùn)練網(wǎng)絡(luò),動(dòng)態(tài)地適應(yīng)不確定性和高度波動(dòng)的工作負(fù)載。仿真結(jié)果證明,相比于現(xiàn)有調(diào)度方法,本文所提策略不僅具有更快更穩(wěn)定的收斂性,還能有效地減少平均任務(wù)響應(yīng)時(shí)間,節(jié)省系統(tǒng)整體能耗,并在保證系統(tǒng)負(fù)載均衡方面有很好的優(yōu)越性。