異構計算系統中能量感知利潤最大化在線算法

張慶輝, 李偉東, 張學杰

(1.云南大學 信息學院 云南 昆明 650500;2.云南大學 數學與統計學院 云南 昆明 650500)

0 引言

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

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

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

本文的主要貢獻如下:1) 為EAPM問題建立了一個準確的數學模型,該模型能精確計算每到達一個用戶并分配其任務包后系統的最大完工時間;2) 提出了一個時間復雜度為O(nm4)的在線算法,該算法在每個用戶到達時構造多個線性方程組,這些線性方程組中最好的結果,便是當前針對該用戶任務包的調度結果;3) 通過對比實驗,說明了本文提出算法的優越性。

1 相關工作

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

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

在云計算環境中,云資源管理同樣是云供應商的一個重要內容。Khemka 等為能源受限的環境設計了四種能量感知的資源分配啟發式方法,目的是使系統獲得的總效用最大化[12]。姜春茂等提出面向實時云任務的細粒度任務合并調度算法,在滿足用戶SLA的前提下,能夠有效降低云能耗[13]。Zhang等通過拍賣機制對云計算虛擬資源進行分配和定價,以提升資源提供商的社會福利[14]。

2 在線調度模型

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

(1)

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

(2)

相應的,n個用戶的能量消耗為

(3)

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

(4)

(5)

(6)

xij∈N,?i,j。

(7)

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

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

3 在線算法

(8)

(9)

(10)

其中:

(11)

(12)

(13)

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

APCi1ETCi1≥APCi2ETCi2≥…≥APCimETCim,

(14)

我們的算法是基于引理1實現的。

引理1存在一個最優解,該最優解符合

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

(15)

因此,該引理成立。

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

(16)

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

算法1在線算法

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

輸出:x。

1) fori=1,2,…,n

2) 重索引下標使得APCi1ETCi1≥…≥APCimETCim

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

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

6) forj=1,2,…,m

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

8) 更新機器j對應的Lj

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

4 實驗評估

4.1 實驗環境

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

4.2 不同γ值對系統的影響

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

4.3 不同用戶數對系統的影響

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

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

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

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

4.4 用戶到達順序對系統的影響

在實際場景中,用戶到達后所提交的任務數是無法預知的。為了評估用戶到達順序對系統的影響,令用戶數n=30,類型為隨機。如果用戶i提交的任務包中的任務數ai>500,則為大任務包;若用戶i提交的任務包中的任務數ai<200,則為小任務包。對比四種到達順序對應的目標值,“BaS”為前一半的用戶提交大任務包,后一半用戶提交小任務包;“SaB”為前一半的用戶提交小任務包,后一半用戶提交大任務包;“Rand”為提交大任務包與小任務包的用戶隨機到達;“Equal”為所有用戶提交的任務包任務數相同,為400。

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

5 總結

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

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

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

圖3 不同用戶到達順序對目標值的影響Figure 3 The impact of different user arrival sequences on the objective value