池來新 謝 寧 張學(xué)杰 張?bào)K先

(云南大學(xué)信息學(xué)院 云南 昆明 650500)

0 引 言

分布式計(jì)算系統(tǒng)的資源分配問題一直是許多研究的焦點(diǎn)，其目標(biāo)是減少處理任務(wù)所需的時間，提升處理效率，并盡可能減少處理這些任務(wù)所需的功耗，以降低處理成本。一般來說，當(dāng)高性能計(jì)算系統(tǒng)的處理器性能提高時，其功耗也會增加，運(yùn)營的電力成本也會隨之增加。對于大型分布式計(jì)算系統(tǒng)來說，機(jī)器運(yùn)營的電力成本顯得尤為重要[1]，如何對資源進(jìn)行分配以調(diào)和任務(wù)處理時間和處理功耗以達(dá)到利潤的最大化則成為了關(guān)鍵。

分布式計(jì)算系統(tǒng)往往包含多種類型的機(jī)器，其處理速度各不相同，而用戶有大量的待處理任務(wù)，同時這些任務(wù)可分為不同類型，不同類型的任務(wù)在不同的機(jī)器上進(jìn)行處理所需時間和功耗可能都不相同，以上情形都造成了問題的復(fù)雜性。一般來說，對此建立的模型都是非線性的，而且存在諸多復(fù)雜的約束條件，無法在多項(xiàng)式的時間內(nèi)進(jìn)行求解。

這種將所有任務(wù)分配給在分布式計(jì)算系統(tǒng)中所有機(jī)器的調(diào)度模型已經(jīng)在多篇文獻(xiàn)中提出，起初更多的研究主要針對完工時間或是系統(tǒng)性能進(jìn)行優(yōu)化。Braun等[2]比較了11種靜態(tài)啟發(fā)式算法，用于將一類獨(dú)立的任務(wù)分配到一個分布式計(jì)算系統(tǒng)，目標(biāo)是最小化完工時間。Diaz等[3]評估了3種用于高度異構(gòu)計(jì)算系統(tǒng)的啟發(fā)式算法，其目標(biāo)是最小化完工時間和流動時間。雖然上述研究中的算法能優(yōu)化完工時間，但未考慮功耗情況，因而在綜合考慮完工時間和能量消耗的能效優(yōu)化問題上難以發(fā)揮作用。

隨著分布式計(jì)算系統(tǒng)不斷發(fā)展，集群規(guī)模不斷增大，電力成本不斷提高，能耗問題已是資源分配所要考慮的重要因素，因此如何平衡計(jì)算效率和能量消耗達(dá)到能效的最優(yōu)化成為研究的熱點(diǎn)。Friese等[4]創(chuàng)建了一個工具，允許系統(tǒng)管理員研究權(quán)衡系統(tǒng)的性能和系統(tǒng)能量消耗。Oxley等[5]開發(fā)并分析了能量感知資源分配的幾種啟發(fā)式算法，用于能量約束和期限約束問題，同時確定每種類型的任務(wù)數(shù)量并將任務(wù)分配給每種類型的機(jī)器的調(diào)度模型。這些研究在優(yōu)化系統(tǒng)性能的同時也考慮了功耗，以便權(quán)衡完工時間和任務(wù)處理成本。

文獻(xiàn)[6]提出了一種基于線性規(guī)劃的資源分配算法，有效計(jì)算出最小化完工時間的高質(zhì)量解決方案。文獻(xiàn)[7]設(shè)計(jì)了一種基于線性規(guī)劃的舍入方法，以生成一組高質(zhì)量的解決方案，可以對完工時間和能量消耗之間進(jìn)行權(quán)衡以使目標(biāo)值最大化。文獻(xiàn)[8]提出了一種新的調(diào)度模型，最大化每單位時間的利潤，并且將任務(wù)調(diào)度的過程分為兩個階段：先通過求取線性規(guī)劃模型并對分?jǐn)?shù)解進(jìn)行舍入以獲得整數(shù)解；再使用LPT算法將任務(wù)分配到具體機(jī)器上。Li等[9]優(yōu)化了上述研究中的線性規(guī)劃模型，可以得出質(zhì)量更高的近似解。這類研究中均使用線性規(guī)劃的方法來綜合考慮完工時間和能量消耗，通過優(yōu)化得出近似易于求解的線性整數(shù)規(guī)劃模型進(jìn)行求解，但由于對模型進(jìn)行近似而產(chǎn)生誤差，因此對算法結(jié)果的質(zhì)量無法給予保障。

同時，對于資源分配問題，文獻(xiàn)[10-12]使用拍賣的思想來解決，但拍賣思想一般用于解決多個用戶的資源需求，類似背包問題，并不適用針對單一用戶而必須滿足所有資源需求的能效優(yōu)化問題。

可見，對于分布式計(jì)算系統(tǒng)中能效問題的研究已較為深入，但限于問題模型過于復(fù)雜難解，其主流思想是對原本復(fù)雜的問題模型進(jìn)行優(yōu)化以得出相對易于求解的近似模型，因此設(shè)計(jì)出一種能直接求解該問題的非線性整數(shù)規(guī)劃的算法才能從根本上解決問題并獲取或趨近最優(yōu)解。粒子群算法(PSO)在復(fù)雜問題模型的求解方面可以發(fā)揮較大作用，其思想簡單、計(jì)算效果好，且相比其他啟發(fā)式算法收斂速度快，比較適用于此類問題的求解。

PSO是一種現(xiàn)在流行的群優(yōu)化算法，因其所要調(diào)整的參數(shù)很少，相比其他啟發(fā)式算法的收斂速度更快，能在更短時間內(nèi)取得比較滿意的結(jié)果。PSO是用于優(yōu)化連續(xù)非線性函數(shù)的最新進(jìn)化優(yōu)化技術(shù)之一，其源于對鳥群和魚群的捕食行為的研究，群體之間共享最優(yōu)信息，通過協(xié)作使群體達(dá)到最優(yōu)的目的，群體中的各成員追隨著當(dāng)前搜索到的最優(yōu)值的方向進(jìn)行尋優(yōu)。PSO還可以同其他啟發(fā)式算法結(jié)合以解決不同特性的問題[13]，同時可以改善收斂性。因此，使用PSO有助于解決上述最優(yōu)化問題。本文使用PSO在文獻(xiàn)[8]基礎(chǔ)上對原有非線性規(guī)劃上進(jìn)行全局搜索，求解真實(shí)目標(biāo)值而非近似目標(biāo)值作為適應(yīng)度，以獲取問題更準(zhǔn)確的可行解，并迭代計(jì)算使其趨向于最優(yōu)解。

1 問題描述

對于分布式計(jì)算系統(tǒng)的資源分配問題，服務(wù)提供商需要合理地將客戶提交的任務(wù)集合分配到分布式計(jì)算系統(tǒng)的服務(wù)器上。任務(wù)包括不同種類型，每個任務(wù)都只能在一臺機(jī)器上進(jìn)行處理，且不可分割，并獨(dú)立于其他任務(wù)，不存在執(zhí)行優(yōu)先級關(guān)系?？蛻魹樘幚砣蝿?wù)集合而支付的價格為p。分布式計(jì)算系統(tǒng)的服務(wù)提供商為客戶處理任務(wù)的成本是電費(fèi)，假設(shè)單位電能成本是c，為便于討論，本文忽略其他成本。組織方的利潤則是用戶支付的價格減去服務(wù)方的電能成本。容易得出，當(dāng)試圖使用功耗較低的機(jī)器去降低電力成本提高利潤時，而由于功耗較低的機(jī)器性能不夠高，因此可能會增加任務(wù)集合的處理時間，故而解決問題的目標(biāo)應(yīng)該是最大化單位時間的利潤。單位時間利潤可表示如下：

(1)

式中：E(x)表示處理任務(wù)集合的總功耗；MS(x)為完工時間，兩者都與資源分配的決策x相關(guān)。同文獻(xiàn)[1]一樣，將完工時間定義為所有機(jī)器的最大處理完任務(wù)的時間。

對上述設(shè)定進(jìn)行舉例說明：

t=2T1={1,2,…,n1}T2={1,2,…,n2}

m=2M1={1,2,…,k1}M2={1,2,…,k2}

對于一臺特定的機(jī)器jk，處理完分配到該機(jī)器上的任務(wù)的時間為Fjk，顯然有式(2)成立，即特定一臺機(jī)器處理任務(wù)的總時間為分配到該機(jī)器上的所有任務(wù)執(zhí)時間的總和。

(2)

不同的決策變量xijk有著不同的完工時間，根據(jù)完工時間的定義，可以得到完工時間的計(jì)算公式如式(3)所示，即完工時間等于在處理該任務(wù)集合中所耗時最長的機(jī)器的處理時間。

MS(x)=maxjmaxk:jk∈MjFjk

(3)

對于集合消耗的總能量E(x)，為了便于討論，本文忽略機(jī)器的空閑功耗，即機(jī)器沒有任務(wù)執(zhí)行時不會產(chǎn)生功耗，在有任務(wù)執(zhí)行時機(jī)器不會產(chǎn)生額外功耗，所以總能量E(x)計(jì)算如下：

(4)

因此，分布式計(jì)算系統(tǒng)的單位利潤最大化問題可以表示為以下非線性整數(shù)規(guī)劃問題：

(5)

該非線性整數(shù)規(guī)劃問題的目標(biāo)是最大化單位時間的利潤Obj。第一個約束確保第i類型的任務(wù)全部分配完；第二個約束確保所有機(jī)器處理任務(wù)的時間小于或等于完工時間MS(x)；第三個約束確保決策變量的值為0及其以上的整數(shù)，因?yàn)槿蝿?wù)不可分，所以要保證xijk為整數(shù)。

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

本文稱文獻(xiàn)[8]中的算法為EAPM算法(Energy-Aware Profit Maximizing Scheduling Algorithm)，該算法所代表的近似線性規(guī)劃算法為目前在分布式能效優(yōu)化中的主流算法。式(5)中目標(biāo)函數(shù)分子和分母的取值都與決策變量x相關(guān)，目標(biāo)函數(shù)是一個非線性函數(shù)，無法在多項(xiàng)式的時間內(nèi)求得最優(yōu)解。一般的解決辦法是將非線性問題轉(zhuǎn)化為等效的線性問題，再將求得的最優(yōu)解轉(zhuǎn)換為原非線性問題的可行解。EAPM算法用完工時間的下界MS，LB來近似代替完工時間MS(x)，MS，LB被定義為不考慮功耗情況而在所有機(jī)器分配任務(wù)而獲得的完工時間，計(jì)算方式如式(6)所示，然后用式(7)和式(8)做變量替換得到一個近似的線性目標(biāo)函數(shù)。

(6)

(7)

(8)

近似之后的線性整數(shù)規(guī)劃決策變量變?yōu)榱藃和z，目標(biāo)函數(shù)可寫為如下形式：

Obj=p·r-c·E(z)

(9)

式(9)為線性函數(shù)，可以使用傳統(tǒng)的線性規(guī)劃求解方法(如單純形法)進(jìn)行求解，再通過式(7)和式(8)將r和z轉(zhuǎn)換為原問題可行解。該方法由于采用近似模型，因此存在一定誤差，即在該模型下求得的最優(yōu)解并非是原模型下的最優(yōu)解。不過在機(jī)器類型為1的特殊情況下實(shí)際上兩者的最優(yōu)解一致，因?yàn)樵谥挥幸环N機(jī)器類型的情況下最優(yōu)的分配方案即在該類型所有機(jī)器上平分任務(wù)數(shù)。由式(6)知MS，LB基于各類型機(jī)器的平均完成時間進(jìn)行計(jì)算，所以此時有MS(x)=MS，LB，則兩者結(jié)果必然一致，但在更一般的情況(機(jī)器類型數(shù)大于1)下，兩者存在誤差，且當(dāng)任務(wù)數(shù)量較小時MS，LB和最優(yōu)解的完工時間MS(x)相對偏差會比較大，導(dǎo)致求出的解與原非線性問題的最優(yōu)解仍有較大差距。

使用PSO可以克服上述問題，因?yàn)镻SO可以直接對非線性問題進(jìn)行全局搜索，無須事先將其轉(zhuǎn)換為線性問題，可以直接通過MS(x)來計(jì)算當(dāng)前調(diào)度策略的真正單位時間利潤，從而能夠以較準(zhǔn)確的方向逼近最優(yōu)解，該方法已廣泛應(yīng)用于各個領(lǐng)域中[14-15]，尤其在資源分配與任務(wù)調(diào)度問題上最為適用[16]。

粒子群優(yōu)化算法如圖1所示。PSO使用粒子作為在目標(biāo)函數(shù)自變量取值空間的搜索個體，粒子的位置取值即為該粒子所對應(yīng)的一個解，所有粒子都在一個D維空間(即自變量為D維向量)中進(jìn)行搜索，且可以通過一個適應(yīng)度函數(shù)來判斷當(dāng)前位置的好壞，適應(yīng)度函數(shù)一般直接使用數(shù)學(xué)規(guī)劃的目標(biāo)函數(shù)。粒子被賦予記憶，能記住當(dāng)前所搜尋到的最佳位置，每個粒子都有一個速度來決定該粒子的移動速度和方向，這個速度可以由粒子本身的歷史經(jīng)驗(yàn)(歷史最佳位置)和其他粒子的歷史經(jīng)驗(yàn)(全局最佳位置)進(jìn)行動態(tài)調(diào)整。

圖1 粒子群優(yōu)化算法簡單示意圖

假設(shè)在D維空間中，有n個粒子，粒子k的位置向量Xk=[Xk1,Xk2,…,XkD],1≤k≤n，粒子k的速度向量Vk=[Vk1,Vk2,…,VkD],1≤k≤n，粒子k經(jīng)歷過的歷史最好位置Pk=[Pk1,Pk2,…,PkD],1≤k≤n，群體內(nèi)(或領(lǐng)域內(nèi))所有粒子所經(jīng)歷過的最好位置Pk=[Pg1,Pg2,…,PgD]。通過若干次迭代動態(tài)調(diào)整上述變量，依次迭代即依次搜索的過程，每次迭代過程中粒子k的第d維速度更新公式如下：

(10)

式中：第一部分表示粒子的運(yùn)動慣性，w被稱為慣性權(quán)重，表示粒子先前速度對當(dāng)前速度的影響，用于調(diào)節(jié)空間中粒子的搜索范圍；第二部分表示粒子的自我認(rèn)知，c1為學(xué)習(xí)因子，表示粒子最佳位置和當(dāng)前位置的差對粒子速度的影響程度；第三部分代表粒子間的信息共享，c2作為學(xué)習(xí)因子，表示群體最佳位置和粒子當(dāng)前位置的差對速度的影響程度[17]；r1和r2是兩個隨機(jī)數(shù)，用于增加搜索的隨機(jī)性。為了提升粒子群算法的收斂性能，避免陷入局部最優(yōu)，可以對上述參數(shù)進(jìn)行動態(tài)調(diào)整[18]。每次迭代過程中粒子k的第d維位置更新公式如下：

(11)

本文算法總體流程如圖2所示。

圖2 算法總體流程

算法每進(jìn)行一次迭代，都要計(jì)算各粒子新位置的適應(yīng)度值，更新各粒子的最佳位置和群體的最佳位置，通過迭代，各粒子都將趨近于全局的最優(yōu)位置。一般來說，粒子的位置和速度的取值范圍是連續(xù)的實(shí)數(shù)空間，但本文問題同文獻(xiàn)[19]和文獻(xiàn)[20]一樣，解都具有離散性。由于任務(wù)不可分，故而應(yīng)將粒子的位置和速度限制為0以上的整數(shù)，對其進(jìn)行離散化。

根據(jù)式(1)的目標(biāo)函數(shù)，目標(biāo)函數(shù)的取值代表著決策x的好壞，而x是一個二維矩陣，表示i類型任務(wù)分配到j(luò)類型機(jī)器的任務(wù)數(shù)目，為了使用粒子群優(yōu)化算法，需要將決策變量x轉(zhuǎn)換為一個D=t×m維的向量X，它代表了一個粒子的位置，而在計(jì)算粒子在某位置適應(yīng)度時又需將向量X轉(zhuǎn)換回二維矩陣的形式才能求出真實(shí)的MS(x)值。本文使用算法1和算法2實(shí)現(xiàn)上述兩種情形的轉(zhuǎn)換。

算法1將二維決策變量x轉(zhuǎn)換為粒子位置向量P

輸入：二維決策變量x。

輸出：粒子位置向量P。

1.ProceduretransferToP(x)

2.fori=1:tdo

3.forj=1:mdo

4.Pd←xij

5.d←d+1

6.endfor

7.endfor

8.returnP

算法2將粒子位置向量P轉(zhuǎn)換為二維決策變量x

輸入：粒子位置向量P。

輸出：二維決策變量x。

1.ProceduretransferToX(P)

3.i←(d-1)/m

4.j←(d-1)%m

5.xij←Pd

6.endfor

7.returnx

算法1通過第2行至第7行的兩層for循環(huán)對二維矩陣x進(jìn)行遍歷，將值依次存入一維向量X中,便可生成二維決策變量對應(yīng)的粒子向量。算法2通過依次遍歷粒子位置向量，通過算法第3行和第4行獲取對應(yīng)的決策變量的下標(biāo)(即任務(wù)類型和機(jī)器類型)，從而實(shí)現(xiàn)粒子向量到二維決策變量的轉(zhuǎn)換。

PSO首先要對所有粒子進(jìn)行隨機(jī)的初始化，根據(jù)式(5)中的規(guī)劃問題，必須考慮約束問題，為了在能夠保持約束的情形下可以隨機(jī)生成粒子位置P數(shù)據(jù)，最后的數(shù)據(jù)只能根據(jù)約束條件計(jì)算得出。生成粒子位置P數(shù)據(jù)的同時，要對所有粒子的最優(yōu)位置Pk(k=1,2,…,D)和群體最優(yōu)位置Xk進(jìn)行初始化。在每一輪迭代中，通過公式計(jì)算每個粒子的新速度和新位置，速度和位置都是D維向量。之后可以根據(jù)粒子的個體適應(yīng)度更新粒子個體的最佳位置和粒子群體的最佳位置。迭代完成后得到的是一個D維的粒子位置向量，必須轉(zhuǎn)換為目標(biāo)的t×m的決策矩陣x，才能再根據(jù)x對任務(wù)進(jìn)行最終的分配。上述過程可以由算法3來實(shí)現(xiàn)。

算法3粒子群算法的初始化和最優(yōu)化搜索

1.ProcedurePSO()

2.fork=1:Psizedo

7.endif

8.endfor

9.fort=1:step

10.fork=1:Psizedo

11.ford=1:t×mdo

13.endfor

17.endif

20.endif

21.endfor

22.endfor

24.assignMachines(x)

算法3中Psize為粒子數(shù)目，step為算法的迭代次數(shù)，t用來來指示當(dāng)前的迭代次數(shù)?；镜牧Ｗ尤核惴ㄊ窃谶B續(xù)空間中進(jìn)行搜索，而本文的目標(biāo)值都是離散值，所以計(jì)算出新的位置之后要進(jìn)行離散化，一般可以直接取近似值，同時還要保證每種類型任務(wù)數(shù)目守恒的約束，以上可以通過算法4中的getBoundP()函數(shù)實(shí)現(xiàn)。算法中對粒子位置適應(yīng)度的計(jì)算通過算法5中的getFitness()函數(shù)來完成。迭代完成后調(diào)用算法2中的transferToX()函數(shù)將粒子群體最佳位置向量轉(zhuǎn)換為決策矩陣x，然后調(diào)用算法6中的assignMachines()函數(shù)對任務(wù)進(jìn)行最終的分配。

算法4離散化位置向量并且在保持約束的前提下求解新一輪迭代的粒子位置

輸入：粒子速度V和粒子位置X。

輸出：粒子新的位置X。

1.ProceduregetBoundP(V,X)

2.ford=1:t×mdo

3. temp←Xd+Vd

4.i←(d-1)/m+1

5.i←(d-1)%m+1

9.else

10.Xd←temp

11.endif

13.endfor

14.returnX

算法5計(jì)算粒子位置的適應(yīng)度

輸入：粒子位置向量P。

輸出：單位利潤Obj。

1.ProceduregetFitness(P)

2.x=chanceferToX(P)

3.forj=1:mdo

4.fori=1:tdo

5.E←E+xijAPCijETCij

6.endfor

7.endfor

8.MS←assignMachines(x)

9.returnp/MS-cE/MS

算法6對各類型機(jī)器進(jìn)行任務(wù)分配

輸入：二維決策變量x。

輸出：完工時間MS。

1.ProcedureassignMachines(x)

2.forj=1:mdo

3. z←φ

4.fori=1:tdo

5.z←z∪{分配在j類型機(jī)器的xij個i類型任務(wù)}

6.endfor

7.y←{對z中的任務(wù)按ETC降序排列}

9.r←arcminMachineTimej

10.分配y中第k個任務(wù)到j(luò)類型的第r臺機(jī)器

11.Timejr←Timejr+ETCij

12.ifTimejr>Timestart+MSthen

13.MS←Timejr=Timestart

14.endif

15.endfor

16.endfor

17.returnMS

算法4中傳入的是粒子速度和粒子上一次迭代的位置，算法第3行保證粒子位置均為整數(shù)。為了保持式(5)的約束，不能直接使用式(11)來計(jì)算粒子在新一輪迭代的位置的第d維數(shù)值，需要先用一個臨時變量temp保存計(jì)算的值。第4行和第5行可以得出粒子位置向量的第d維所對應(yīng)的決策矩陣x的行號和列號，xij代表第i類型任務(wù)分配在j類型機(jī)器的任務(wù)數(shù)，通過計(jì)算該類型任務(wù)分配在前面j-1個類型機(jī)器的任務(wù)數(shù)目之和s，根據(jù)式(5)中的第一個約束條件可知該類型任務(wù)在j類型機(jī)器上還能分配多少，進(jìn)而可以分辨通過式(11)計(jì)算的數(shù)值能否滿足約束條件。注意在j=t×m時，不能再使用式(11)，而須通過任務(wù)數(shù)目減去前面j-1個機(jī)器類型分配的任務(wù)數(shù)目的和，以使其滿足約束條件，該方法同樣適用于算法3中的第3行。

算法5中的粒子適應(yīng)度實(shí)際上就是式(5)中的目標(biāo)函數(shù)，即單位利潤的取值，其中P為傳入的粒子位置向量，需要通過算法2中的chanceferToX()函數(shù)轉(zhuǎn)換為決策矩陣x，然后通過遍歷矩陣x計(jì)算出此決策下需要消耗的功耗總和E，第8行調(diào)用算法5中的assignMachines()函數(shù)，注意這只是對此決策進(jìn)行模擬的任務(wù)分配，用來計(jì)算出此決策的真正的完工時間MS，因此算法5可以計(jì)算出準(zhǔn)確的單位利潤。

算法6基于傳統(tǒng)的LPT多處理器調(diào)度算法，獨(dú)立處理各類型機(jī)器的任務(wù)分配，z用來存儲分配在j類型機(jī)器上的所有任務(wù)，并且以貪婪策略將ETC更大的任務(wù)分配給有最早就緒時間的機(jī)器，此機(jī)器可以通過算法第9行獲得，算法中Timejr表示第j類型機(jī)器的第r臺機(jī)器的就緒時間。為了在計(jì)算粒子位置適應(yīng)度的時候得出完工時間，我們用Timestart存儲任務(wù)集合的開始時間，分配任務(wù)的同時要據(jù)此更新完工時間。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

進(jìn)行模擬實(shí)驗(yàn)比較粒子群算法和EAPM算法的性能，主要根據(jù)用兩種方法所獲取的單位利潤和處理完用戶所有任務(wù)的完工時間及總的能量消耗來評估。不失一般性，假設(shè)所有實(shí)驗(yàn)中的單位電能成本c=1，客戶支付價格為：

p=γEmin

(12)

式中:Emin是忽略完工時間時消耗的能量的下限。

(13)

γ=p/Emin是一個無量綱參數(shù)，用來影響價格，根據(jù)式(1)，為了盈利(即使目標(biāo)值大于0)，需保證分子大于0，則需保證γEmin-cE(x)>0，根據(jù)Emin的定義必有γEmin≤E(x)，因此一般要設(shè)定γ>1，同時要考慮市場因素，不能過高。本實(shí)驗(yàn)分別針對γ=1.2、γ=1.3和γ=1.5進(jìn)行測試。

本文模擬實(shí)驗(yàn)共設(shè)有5種機(jī)器類型，即m=5，每種類型機(jī)器各20臺，共計(jì)100臺機(jī)器，任務(wù)類型共有5種，即t=5。測試的主要變量是客戶的任務(wù)數(shù)目，EAPM算法中的線性規(guī)劃可以使用文獻(xiàn)[22]中的單純形法進(jìn)行求解，測試共分為四組，前兩組分別針對較小任務(wù)數(shù)量和較大任務(wù)數(shù)量時的單位利潤進(jìn)行測試和對比，后兩組分別對完工時間和總的能量消耗進(jìn)行測試和對比。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

由前面的論述可知實(shí)驗(yàn)的測試數(shù)據(jù)是矩陣ETC和矩陣APC的具體數(shù)值，本次實(shí)驗(yàn)的數(shù)據(jù)集來源于實(shí)際的處理器基準(zhǔn)測試[23]，該基準(zhǔn)測試主要對不同處理器執(zhí)行若干項(xiàng)任務(wù)，得出相對應(yīng)的任務(wù)執(zhí)行時間和所需能耗，從中可以整理出矩陣ETC和矩陣APC的相應(yīng)數(shù)值，以便在本文實(shí)驗(yàn)中進(jìn)行測試。

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

圖3和圖4分別顯示了對較小數(shù)量任務(wù)(200～1 000個任務(wù))和較大數(shù)量任務(wù)(2 000～10 000個任務(wù))進(jìn)行測試得出的兩種算法單位利潤對比結(jié)果。由圖3和圖4均可以看出，γ取值越高，單位利潤也越高，因?yàn)閮r格變高了。無論任務(wù)數(shù)量取多大，PSO求解結(jié)果的單位利潤都要高于EAPM算法。同時，對比圖3和圖4兩種情況可以發(fā)現(xiàn)在任務(wù)數(shù)量較大的時候PSO的結(jié)果雖優(yōu)于EAPM算法，但產(chǎn)生的差距并不是特別大，而在任務(wù)數(shù)量較小的時候，EAPM算法對于PSO結(jié)果差距明顯。換言之，EAPM算法在任務(wù)量較少的情況下離最優(yōu)解存在較大誤差，這同2.1節(jié)中對EAPM算法的分析一致。

(a) γ=1.2

(b) γ=1.3 (c) γ=1.5圖3 較小任務(wù)數(shù)量時單位利潤對比

(a) γ=1.2

(b) γ=1.3 (c) γ=1.5圖4 較大任務(wù)數(shù)量時單位利潤對比

表1和表2分別顯示了在不同任務(wù)數(shù)量(2 000～6 000個任務(wù))下兩種算法處理任務(wù)的能量消耗和完工時間對比結(jié)果?？梢钥闯觯谌蝿?wù)數(shù)量相對較小的情況下，PSO的完工時間要短于EAPM算法，雖然個別情形完工時間長于EAPM算法，比如在γ=1.2、任務(wù)數(shù)量為4 000的情況，但從該情況所對應(yīng)的能量消耗情況來看，PSO的結(jié)果明顯優(yōu)于EAPM算法的結(jié)果，表明PSO在提升單位利潤的同時，也在大多數(shù)情況下減少了用戶的等待時間，并降低了分布式服務(wù)提供商的能量消耗，這些均對于現(xiàn)實(shí)情況有較大意義。從表1中同時還可以發(fā)現(xiàn)在任務(wù)數(shù)量相對較大的情況下，兩種算法的結(jié)果一致，表明EAPM算法的誤差的影響在任務(wù)數(shù)量較大的情況下被削弱，這與圖3和圖4所表現(xiàn)出來的特點(diǎn)一致。所以PSO在任務(wù)數(shù)量相對較小的情況下具有明顯優(yōu)勢。

表1 較大任務(wù)數(shù)量時能量消耗對比

表2 較大任務(wù)數(shù)量時完工時間對比

產(chǎn)生上述差距的原因在于EAPM在建立模型的時候?qū)θ缡?1)所示的目標(biāo)函數(shù)進(jìn)行了近似，用完工時間的下界MS，LB代替真正的完工時間MS，以便于后面進(jìn)行變量替換使原非線性整數(shù)規(guī)劃轉(zhuǎn)換為等效的線性整數(shù)規(guī)劃。但這造成了模型的不準(zhǔn)確，而且造成的誤差會在任務(wù)數(shù)目過少的時候顯得特別突出，使得線性整數(shù)規(guī)劃的最優(yōu)解并不是原問題的最優(yōu)解。而本文算法通過模擬任務(wù)分配計(jì)算出真實(shí)MS，使算法可以直接基于式(5)中準(zhǔn)確的非線性整數(shù)規(guī)劃模型進(jìn)行啟發(fā)式搜索，從而能夠找到更優(yōu)的解。

3.4 任務(wù)類型數(shù)目和機(jī)器類型數(shù)目對實(shí)驗(yàn)結(jié)果的影響

上述實(shí)驗(yàn)中任務(wù)類型數(shù)目和機(jī)器類型數(shù)目被恒定設(shè)置為5，事實(shí)上機(jī)器類型數(shù)目和任務(wù)類型數(shù)目的不同對實(shí)驗(yàn)結(jié)果均會產(chǎn)生影響。本次實(shí)驗(yàn)固定任務(wù)數(shù)目為1 000，γ設(shè)置為1.2，對任務(wù)類型數(shù)目和機(jī)器類型數(shù)目分別進(jìn)行調(diào)試以對兩種算法的單位利潤、能量消耗、完工時間進(jìn)行測試，結(jié)果如圖5、圖6所示。

(a) 單位利潤對比 (b) 完工時間對比圖5 任務(wù)類型數(shù)目不同時單位利潤和能量消耗情況的對比結(jié)果

(a) 單位利潤對比 (b) 完工時間對比圖6 機(jī)器類型數(shù)目不同時單位利潤和能量消耗的對比結(jié)果

圖5和表3顯示了在機(jī)器類型數(shù)目設(shè)置為5，任務(wù)數(shù)目設(shè)置為1 000、γ設(shè)置為1.2時兩種算法在不同任務(wù)數(shù)目下的單位利潤、能量消耗和完工時間況的對比結(jié)果?？梢钥闯鲈诓煌蝿?wù)數(shù)目的情況下，PSO在單位利潤方面均優(yōu)于EAPM算法，雖然在部分情況下PSO比EAPM算法消耗了更多能量，但通過表2可以看出，在這些情況下PSO處理任務(wù)的完工時間明顯小于EAPM算法的結(jié)果，由于PSO以單位利潤作為目標(biāo)進(jìn)行優(yōu)化，故而這些情況會正常存在。

表3 任務(wù)類型數(shù)目不同時能量消耗的對比結(jié)果

圖6和表4顯示了在任務(wù)類型數(shù)目設(shè)置為5，任務(wù)數(shù)目設(shè)置為1 000、γ設(shè)置為1.2時兩種算法在不同機(jī)器數(shù)目下的單位利潤、能量消耗和完工時間情況的對比結(jié)果?？梢园l(fā)現(xiàn)PSO得出的單位利潤要優(yōu)于EAPM算法的結(jié)果，但由于PSO是基于單位利潤進(jìn)行優(yōu)化的原因，存在一些能量消耗或完工時間情況下PSO不如EAPM算法的結(jié)果。同時可以發(fā)現(xiàn)在機(jī)器數(shù)目為1的情況下PSO和EAPM算法的單位利潤、能量消耗和完工時間均取得一致的結(jié)果，這同本文的分析一致。

表4 機(jī)器類型數(shù)目不同時完工時間的對比結(jié)果

PSO在任務(wù)類型和機(jī)器類型不同的情況下均能取得不錯的結(jié)果，且在大多數(shù)時候均優(yōu)于EAPM算法。其原因仍在于EAPM算法使用了近似的線性模型進(jìn)行求解造成和結(jié)果的不精確，即線性模型的最優(yōu)解實(shí)際上離原始模型的最優(yōu)解存在差距，而PSO由于直接基于原始的模型進(jìn)行求解，故而具備更高的求解精度。

對于機(jī)器類型數(shù)目為1的特殊情況，可以發(fā)現(xiàn)兩種算法的完工時間相同，這與本文的分析一致，由于EAPM算法使用各類型機(jī)器處理任務(wù)時間平均值的最大值作為完工時間的一個近似，當(dāng)機(jī)器類型數(shù)目為1時，最優(yōu)的結(jié)果是將所有任務(wù)分?jǐn)傊了袡C(jī)器，在能完全平分的情況下該近似值等于式(3)計(jì)算出來的完工時間。故而EAPM算法在任務(wù)類型數(shù)目為1的情況下能得到最優(yōu)結(jié)果，同時也反映了本文算法也具備搜索到最優(yōu)解的能力，而且在更為普遍的情況下可以相比傳統(tǒng)基于線性規(guī)劃的算法得出更優(yōu)的結(jié)果，這對于現(xiàn)實(shí)中分布式計(jì)算系統(tǒng)的能效優(yōu)化具有較大意義。

4 結(jié) 語

在分布式計(jì)算系統(tǒng)中，為了平衡客戶的任務(wù)處理效率和功耗，進(jìn)行資源調(diào)度決策以達(dá)到單位利潤的最大化。本文對問題建立了準(zhǔn)確的數(shù)學(xué)模型，指出了EAPM算法不能取得最優(yōu)解的原因，詳細(xì)闡述了本文所用的粒子群算法，并用該算法在保持約束的情形下離散化變量進(jìn)行啟發(fā)式搜索取得了比EAPM算法更優(yōu)的實(shí)驗(yàn)結(jié)果，表明了該算法可以在分布式計(jì)算系統(tǒng)中得到應(yīng)用。

為了討論方便，本文對問題做了一定簡化，忽略了機(jī)器待機(jī)(無任務(wù)運(yùn)行)時的功耗及其他成本，且未考慮機(jī)器的功耗上限，未來可以在更復(fù)雜的情形下建立準(zhǔn)確模型，適當(dāng)調(diào)整算法使其更具可用性。