基于粒子群算法的分布式計算系統(tǒng)能效優(yōu)化方法

池來新 謝 寧 張學杰 張驥先

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

0 引 言

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

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

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

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

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

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

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

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

1 問題描述

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

(1)

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

對上述設定進行舉例說明：

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

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

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

(2)

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

MS(x)=maxjmaxk:jk∈MjFjk

(3)

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

(4)

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

(5)

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

2 算法設計

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

(6)

(7)

(8)

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

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

(9)

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

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

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

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

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

(10)

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

(11)

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

圖2 算法總體流程

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

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

算法1將二維決策變量x轉換為粒子位置向量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轉換為二維決策變量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進行遍歷，將值依次存入一維向量X中,便可生成二維決策變量對應的粒子向量。算法2通過依次遍歷粒子位置向量，通過算法第3行和第4行獲取對應的決策變量的下標(即任務類型和機器類型)，從而實現(xiàn)粒子向量到二維決策變量的轉換。

PSO首先要對所有粒子進行隨機的初始化，根據式(5)中的規(guī)劃問題，必須考慮約束問題，為了在能夠保持約束的情形下可以隨機生成粒子位置P數(shù)據，最后的數(shù)據只能根據約束條件計算得出。生成粒子位置P數(shù)據的同時，要對所有粒子的最優(yōu)位置Pk(k=1,2,…,D)和群體最優(yōu)位置Xk進行初始化。在每一輪迭代中，通過公式計算每個粒子的新速度和新位置，速度和位置都是D維向量。之后可以根據粒子的個體適應度更新粒子個體的最佳位置和粒子群體的最佳位置。迭代完成后得到的是一個D維的粒子位置向量，必須轉換為目標的t×m的決策矩陣x，才能再根據x對任務進行最終的分配。上述過程可以由算法3來實現(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用來來指示當前的迭代次數(shù)?；镜牧Ｗ尤核惴ㄊ窃谶B續(xù)空間中進行搜索，而本文的目標值都是離散值，所以計算出新的位置之后要進行離散化，一般可以直接取近似值，同時還要保證每種類型任務數(shù)目守恒的約束，以上可以通過算法4中的getBoundP()函數(shù)實現(xiàn)。算法中對粒子位置適應度的計算通過算法5中的getFitness()函數(shù)來完成。迭代完成后調用算法2中的transferToX()函數(shù)將粒子群體最佳位置向量轉換為決策矩陣x，然后調用算法6中的assignMachines()函數(shù)對任務進行最終的分配。

算法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計算粒子位置的適應度

輸入：粒子位置向量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對各類型機器進行任務分配

輸入：二維決策變量x。

輸出：完工時間MS。

1.ProcedureassignMachines(x)

2.forj=1:mdo

3. z←φ

4.fori=1:tdo

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

6.endfor

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

9.r←arcminMachineTimej

10.分配y中第k個任務到j類型的第r臺機器

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

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

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

3 實 驗

3.1 實驗設置

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

p=γEmin

(12)

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

(13)

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

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

3.2 實驗數(shù)據集

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

3.3 實驗結果及分析

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

(a) γ=1.2

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

(a) γ=1.2

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

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

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

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

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

3.4 任務類型數(shù)目和機器類型數(shù)目對實驗結果的影響

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

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

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

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

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

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

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

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

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

4 結 語

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

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