異構(gòu)計算系統(tǒng)中能量感知利潤最大化在線算法

張慶輝, 李偉東, 張學(xué)杰

(1.云南大學(xué) 信息學(xué)院 云南 昆明 650500;2.云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院 云南 昆明 650500)

0 引言

隨著數(shù)據(jù)中心能耗的快速增長,異構(gòu)計算系統(tǒng)中關(guān)注于能效的任務(wù)調(diào)度越來越重要。最近學(xué)界提出了一種名為任務(wù)包(bag-of-tasks)的靜態(tài)調(diào)度模型[1]。與以往的經(jīng)典調(diào)度模型相比,某臺機器上的固定執(zhí)行時間(estimated time to compute,ETC)取決于任務(wù)類型與機器類型。通過這一概念,能把異構(gòu)計算系統(tǒng)中心成千上萬的任務(wù)進(jìn)行分類,而分類后的類型數(shù)量相對較少。如果單獨地為每一個任務(wù)進(jìn)行決策,那將要耗費難以接受的時間。而任務(wù)包的調(diào)度模型很好地限制了問題規(guī)模,這也使得為該問題設(shè)計一種能得到擬最優(yōu)調(diào)度的高效算法成為可能[2-3]。

經(jīng)典的能量感知調(diào)度模型旨在最小化任務(wù)包所消耗的能量或最大完工時間。然而,對于異構(gòu)計算系統(tǒng)中心運營商而言,將每個單位時間的運行利潤最大化會帶來更多的經(jīng)濟收益,其中利潤等于用戶為一個任務(wù)包支付的費用減去執(zhí)行該任務(wù)包消耗的電力成本。通過綜合考慮能源成本和最大完工時間,實現(xiàn)單位時間利潤最大化的目標(biāo),即考慮任務(wù)包的能量感知利潤最大化(energy-aware profit maximizing, EAPM)問題。Tarplee等以此為目標(biāo)提出了一種新的異構(gòu)計算系統(tǒng)調(diào)度模型,該模型具有機器類型數(shù)與任務(wù)數(shù)都十分有限的特征[3]。通過使用一種新穎的基于線性規(guī)劃(linear programming, LP)的舍入算法,設(shè)計了一個能夠得到接近最優(yōu)調(diào)度的高效算法。

Tarplee等用一個最大完工時間下界代替了原本的最大完工時間[3]。最大完工時間下界是將任務(wù)平均分配給所有機器時的完工時間。這個下界與真實的最大完工時間是有一定差距的。因此,該數(shù)學(xué)模型是不準(zhǔn)確的,而且在基于LP的舍入步驟過程中,能耗成本可能會增加。這導(dǎo)致即便可以通過使用基于匹配的舍入技術(shù)來改善,但執(zhí)行時間會隨著問題規(guī)模的擴大而急劇上升,使該算法在大型數(shù)據(jù)中心無法有很好的表現(xiàn)。

本文的主要貢獻(xiàn)如下:1) 為EAPM問題建立了一個準(zhǔn)確的數(shù)學(xué)模型,該模型能精確計算每到達(dá)一個用戶并分配其任務(wù)包后系統(tǒng)的最大完工時間;2) 提出了一個時間復(fù)雜度為O(nm4)的在線算法,該算法在每個用戶到達(dá)時構(gòu)造多個線性方程組,這些線性方程組中最好的結(jié)果,便是當(dāng)前針對該用戶任務(wù)包的調(diào)度結(jié)果;3) 通過對比實驗,說明了本文提出算法的優(yōu)越性。

1 相關(guān)工作

最近幾十年有大量關(guān)于異構(gòu)計算系統(tǒng)中任務(wù)調(diào)度模型的研究。Braun等比較了11種靜態(tài)啟發(fā)式算法,他們將一類互相獨立的任務(wù)映射到異構(gòu)分布式計算系統(tǒng),來最小化最大完工時間[4]。Dai等在包含兩臺平行機的系統(tǒng)中,設(shè)計了一種半在線算法,能很好地限制機器的最大完工時間[5]。針對考慮任務(wù)包的調(diào)度模型,Tarplee 等提出了一種基于線性規(guī)劃的資源分配算法,能高效地給出最小化最大完工時間的調(diào)度方案[2]。胡逸騉針對面向異構(gòu)計算集群的任務(wù)調(diào)度和能量消耗問題,提出一種面向異構(gòu)計算系統(tǒng)的能量感知任務(wù)調(diào)度算法[6]。

Friese 等針對任務(wù)包這種情形提出了一種改進(jìn)的多目標(biāo)遺傳算法來生成多個不同的調(diào)度方案,能很好地平衡能源消耗和最大完工時間之間的得失[1,7]。他們還創(chuàng)建了一個工具,該工具能幫助系統(tǒng)管理員對系統(tǒng)性能和系統(tǒng)能量分配進(jìn)行權(quán)衡[8]。Zhang等設(shè)計了一個整數(shù)線性雙目標(biāo)優(yōu)化模型,并提出了兩階段的啟發(fā)式分配算法以找到高質(zhì)量的可行解決方案[9]。除此之外,追求能量感知利潤最大化的目標(biāo)也能很好地平衡最大完工時間和能耗。Li等針對考慮任務(wù)包的能量感知利潤最大化問題,設(shè)計了一個最壞情況即近似比接近2的近似算法[10]。隨后又提出了一個針對該問題的多項式時間近似算法,該算法同樣能在某些情況下有接近2的近似比效果[11]。

在云計算環(huán)境中,云資源管理同樣是云供應(yīng)商的一個重要內(nèi)容。Khemka 等為能源受限的環(huán)境設(shè)計了四種能量感知的資源分配啟發(fā)式方法,目的是使系統(tǒng)獲得的總效用最大化[12]。姜春茂等提出面向?qū)崟r云任務(wù)的細(xì)粒度任務(wù)合并調(diào)度算法,在滿足用戶SLA的前提下,能夠有效降低云能耗[13]。Zhang等通過拍賣機制對云計算虛擬資源進(jìn)行分配和定價,以提升資源提供商的社會福利[14]。

2 在線調(diào)度模型

在一個異構(gòu)計算機系統(tǒng)中包含了m種不同的機器類型和n種不同類型的用戶。用戶i提交的任務(wù)包中的任務(wù)相互獨立,數(shù)量為ai[4],執(zhí)行這類任務(wù)能產(chǎn)生的收益為pi。ETC=(ETCij)是一個n×m維矩陣,ETCij是用戶i的任務(wù)在機器j上執(zhí)行所需的固定執(zhí)行時間;APC=(APCij)同樣是一個n×m維矩陣,其中APCij是用戶i的任務(wù)在機器j上執(zhí)行所需要的平均功率消耗(average power consumption,APC)[3]。xij表示用戶i的任務(wù)分配給機器j執(zhí)行的任務(wù)數(shù)。對于一個可行解x=(xij),機器j的負(fù)載可以定義為

(1)

所有機器的最大完工時間MS(x)為

(2)

相應(yīng)的,n個用戶的能量消耗為

(3)

用c表示每個單位能耗的成本,EAPM問題可以用非線性整數(shù)規(guī)劃表示:

(4)

(5)

(6)

xij∈N,?i,j。

(7)

目標(biāo)函數(shù)(4)要最大化單位時間的收益,x是決策向量。約束(5)確保了每一個用戶的每一個任務(wù)都被分配給某個機器。由于最大化單位時間收益的目標(biāo)等價于最小化最大完工時間,約束(6)確保了MS(x)是所有機器的最大完工時間。

然而在實際場景中,當(dāng)某個用戶到達(dá)時就需要在機器不知道未到達(dá)用戶的信息的情況下分配該用戶的所有任務(wù)。因此,研究考慮任務(wù)包的EAPM問題的在線算法是很有必要的。該在線算法考慮用戶i的任務(wù)會在用戶i+1到達(dá)之前就被分配,i=1,2,…,n-1。但是,當(dāng)用戶i提交的任務(wù)數(shù)非常大時,不能逐個分配這些任務(wù)。因此,為考慮任務(wù)包的EAPM問題設(shè)計一個高效的在線算法是很有必要的。

3 在線算法

(8)

(9)

(10)

其中:

(11)

(12)

(13)

為了便于操作,將服務(wù)于用戶i的任務(wù)的機器按照APCijETCij降序排序。不失一般性,假設(shè)

APCi1ETCi1≥APCi2ETCi2≥…≥APCimETCim,

(14)

我們的算法是基于引理1實現(xiàn)的。

引理1存在一個最優(yōu)解,該最優(yōu)解符合

其中:τ∈{1,2,…,m}。

(15)

因此,該引理成立。

對于每個τ=1,2,…,m,只需要考慮部分的決策變量xij(j=τ,…,m)。此時想要得到用戶i到達(dá)時的所有xij值以及MSi的值,通過計算可得預(yù)期結(jié)果:

(16)

式(16)共有m-τ+2個等式和m-τ+2個未知數(shù),未知數(shù)為MSi和xij(j=τ,…,m)。因此,在多項式時間內(nèi)對式(16)進(jìn)行求解。對于每一個τ=1,2,…,m,得到一組xij的值。比較這m組可行解的目標(biāo)值,便能得到當(dāng)前的最優(yōu)調(diào)度。將「xij?個用戶i的任務(wù)分配給機器j,直到所有任務(wù)都被分配。

算法1在線算法

輸入:m,n,ETC,APC以及用戶到達(dá)序列。

輸出:x。

1) fori=1,2,…,n

2) 重索引下標(biāo)使得APCi1ETCi1≥…≥APCimETCim

3) forτ=1,2,…,m

5) 比較這m個解,找到使得公式(11)的值最大的xij

6) forj=1,2,…,m

7) 將「xij?個用戶i的任務(wù)分配給機器j,直到所有任務(wù)都被分配

8) 更新機器j對應(yīng)的Lj

接下來計算在線算法的時間復(fù)雜度。該算法中最主要耗費時間的是步驟4)中的解線性方程組。通過矩陣運算來對該方程組進(jìn)行求解,花費的時間為(m-τ+2)3。對于每個到達(dá)用戶,需要求解m個線性方程組,共有n個用戶到達(dá)。因此,此算法的時間復(fù)雜度為O(nm4)。

4 實驗評估

4.1 實驗環(huán)境

為了進(jìn)行對比,除了本文提出的在線方法(Online),我們還使用了貪心算法(Greedy)和平均分配算法(Average)來解決EAPM問題。Greedy算法將會在一個用戶到達(dá)時,將該用戶的整個任務(wù)包分配給能使ETC·APC值最小的那臺機器,而Average將會把該用戶的整包任務(wù)平均分配給每臺機器。使用C++編程語言實現(xiàn)上述算法,并在以下硬件配置環(huán)境中進(jìn)行了實驗:CPU為Intel i7-10700,8核16線程2.9 GHz,16 GB內(nèi)存及1 TB硬盤。實驗的部分?jǐn)?shù)據(jù)源于Tarplee在OpenBenchmark基礎(chǔ)上進(jìn)行了擴充的數(shù)據(jù)集,共有包含9種機器類型與30種任務(wù)類型[15]。

4.2 不同γ值對系統(tǒng)的影響

本實驗是在上述9種機器類型和30種任務(wù)類型的基準(zhǔn)上進(jìn)行的?？紤]30個用戶按任意順序提交類型各不相同的任務(wù)包,用戶i的任務(wù)包中的任務(wù)數(shù)ai∈[200,1 000]。隨著γ的變化,三種方法得到的目標(biāo)值(式(4))變化如表1所示。為了減小隨機性帶來的影響,每次γ取值后重復(fù)100次實驗并將結(jié)果取平均值,結(jié)果見表1。從表1可以看到本文提出的Online方法在所有情況下都優(yōu)于另外兩種方法。當(dāng)γ較小時,Online方法與Greedy方法得到的目標(biāo)值差距并不大,但當(dāng)γ逐漸增大后Online方法便體現(xiàn)了其優(yōu)越性。Average方法與另外兩種方法得到的目標(biāo)值有著較大差距。它雖然能使得系統(tǒng)的最大完工時間最小,但是由于并未考慮成本的原因,會使得最終的目標(biāo)值變得很差。

4.3 不同用戶數(shù)對系統(tǒng)的影響

本實驗研究了用戶數(shù)(n)從30逐漸增長到2 000時對系統(tǒng)最終目標(biāo)值的影響。為了更全面地評估n的增長帶來的影響,取γ=1.2、1.3和1.5進(jìn)行對比。用戶i提交的任務(wù)包中的任務(wù)數(shù)ai∈[200,1 000]。

從圖1中可以看到當(dāng)用戶數(shù)較小時,Online方法得到的目標(biāo)值更大,當(dāng)用戶數(shù)不斷增加,Online方法與Greedy方法得到的目標(biāo)值幾乎變得相等。這是由于當(dāng)n變得足夠大時,總的任務(wù)數(shù)也會增加,這會使得兩種方法給出的調(diào)度方案產(chǎn)生的最大完工時間逐漸靠近最優(yōu)調(diào)度所產(chǎn)生的最大完工時間。

表1 不同γ值對目標(biāo)值的影響Table 1 The object value was effected by different γ values

從圖2可以看出三種方法的執(zhí)行時間都在隨著用戶數(shù)的增加而增加。雖然Online方法的執(zhí)行時間最長,但它得到的目標(biāo)值也是最大的,即使在n=2 000時其執(zhí)行時間也是ms級的。

4.4 用戶到達(dá)順序?qū)ο到y(tǒng)的影響

在實際場景中,用戶到達(dá)后所提交的任務(wù)數(shù)是無法預(yù)知的。為了評估用戶到達(dá)順序?qū)ο到y(tǒng)的影響,令用戶數(shù)n=30,類型為隨機。如果用戶i提交的任務(wù)包中的任務(wù)數(shù)ai>500,則為大任務(wù)包;若用戶i提交的任務(wù)包中的任務(wù)數(shù)ai<200,則為小任務(wù)包。對比四種到達(dá)順序?qū)?yīng)的目標(biāo)值,“BaS”為前一半的用戶提交大任務(wù)包,后一半用戶提交小任務(wù)包;“SaB”為前一半的用戶提交小任務(wù)包,后一半用戶提交大任務(wù)包;“Rand”為提交大任務(wù)包與小任務(wù)包的用戶隨機到達(dá);“Equal”為所有用戶提交的任務(wù)包任務(wù)數(shù)相同,為400。

從圖3可以看到,在所有情況下Online方法都能得到最好的目標(biāo)值結(jié)果。此外,用戶到達(dá)的順序并未對目標(biāo)值造成明顯的影響,只有當(dāng)SaB情形時Online方法與Greedy得到的目標(biāo)值會稍微降低。這是由于先將小任務(wù)包分配之后,為了不引起最大完工時間的快速增長,大包任務(wù)到達(dá)時有較小可能被分配給成本更大的機器進(jìn)行執(zhí)行。

5 總結(jié)

我們提出的Online的方法,通過新穎的方法構(gòu)造線性方程組得到最終的分配結(jié)果,其執(zhí)行時間依賴用戶數(shù)以及機器種類數(shù),并通過實驗證明此方法能得到令人滿意的結(jié)果。

圖1 三種方法的目標(biāo)值隨著n增長的變化Figure 1 Objective values of three methods with varying n

圖2 三種方法的執(zhí)行時間隨著n增長的變化Figure 2 Execution time of three methods with varying n

圖3 不同用戶到達(dá)順序?qū)δ繕?biāo)值的影響Figure 3 The impact of different user arrival sequences on the objective value