朱海, 王曉麗, 馬海明

(1.周口師范學(xué)院網(wǎng)絡(luò)工程學(xué)院, 466001, 河南周口; 2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院, 710071, 西安)

隨著物聯(lián)網(wǎng)和互聯(lián)網(wǎng)應(yīng)用的蓬勃發(fā)展,源源不斷的大數(shù)據(jù)涌入各行各業(yè),對(duì)高性能計(jì)算的需求不斷高漲。大規(guī)模計(jì)算平臺(tái)如云計(jì)算、網(wǎng)格計(jì)算、霧計(jì)算等應(yīng)運(yùn)而生。然而,不管是何種分布式計(jì)算平臺(tái)都離不開高效的任務(wù)調(diào)度策略[1]。

大數(shù)據(jù)任務(wù)[2],如大規(guī)模信號(hào)處理、圖像處理、矩陣運(yùn)算等,雖然數(shù)據(jù)規(guī)模龐大,但是任務(wù)往往具有可分性,即可以切分為任意大小的子任務(wù)且各子任務(wù)之間沒有優(yōu)先關(guān)系[3]?？煞秩蝿?wù)調(diào)度模型分為單趟調(diào)度和多趟調(diào)度兩大類,其中單趟調(diào)度將任務(wù)劃分為與服務(wù)器具有相同數(shù)目的子任務(wù),目標(biāo)是尋找最優(yōu)的任務(wù)分配方案使得任務(wù)的完成時(shí)間最短。近年來,針對(duì)各類分布式計(jì)算平臺(tái),如星型網(wǎng)絡(luò)[4]、多層樹網(wǎng)絡(luò)[5]、高斯網(wǎng)格[6]、云平臺(tái)[7]和非線性負(fù)載的線性網(wǎng)絡(luò)[8]等,已有文獻(xiàn)推導(dǎo)得到了最優(yōu)或近似最優(yōu)的任務(wù)分配方案的解析解。雖然單趟調(diào)度易于實(shí)現(xiàn),但是由于服務(wù)器存在較長(zhǎng)的等待時(shí)間,降低了服務(wù)器的利用率和完成任務(wù)的效率。

針對(duì)這一問題,Bharadwaj等提出了多趟調(diào)度模型,將任務(wù)劃分為數(shù)倍于服務(wù)器數(shù)的子任務(wù)并分多趟分配給各服務(wù)器[9]。通過減少服務(wù)器的等待時(shí)間提高完成任務(wù)的效率。多趟調(diào)度模型在各類計(jì)算平臺(tái)得到了廣泛應(yīng)用,如星型網(wǎng)絡(luò)[10]、K維網(wǎng)[11]、完全B-Ary樹網(wǎng)[12]和云平臺(tái)[13]等。與單趟調(diào)度模型相比,多趟調(diào)度模型求解的復(fù)雜度急劇增大。一是因?yàn)槟Ｐ鸵肓诵碌淖兞俊{(diào)度趟數(shù),二是多趟調(diào)度的任務(wù)分配方案不再是一個(gè)向量而是一個(gè)矩陣,其中矩陣的每個(gè)元素表示各趟調(diào)度中每個(gè)服務(wù)器的任務(wù)分配量。為了得到多趟調(diào)度的最優(yōu)解,Suresh等提出了一種混合實(shí)數(shù)編碼進(jìn)化算法[14],然而當(dāng)系統(tǒng)規(guī)模和調(diào)度趟數(shù)很大時(shí),算法很難在可容忍的時(shí)間范圍內(nèi)收斂到全局最優(yōu)解。為了得到問題的近似最優(yōu)解,Yang等提出了均勻多趟調(diào)度模型,將任務(wù)分配矩陣簡(jiǎn)化為向量,并推導(dǎo)得到了任務(wù)分配向量的解析解[15]。Shokripour等對(duì)模型進(jìn)一步優(yōu)化,提出了周期性多趟調(diào)度模型,將調(diào)度分為內(nèi)部調(diào)度和最后一趟調(diào)度兩部分[16]。最后一趟調(diào)度用來確保所有服務(wù)器同時(shí)完成計(jì)算,從而進(jìn)一步降低了任務(wù)的完成時(shí)間。但是,文獻(xiàn)[10-16]并沒有找到服務(wù)器的最優(yōu)調(diào)度順序,因此不能最小化任務(wù)的完成時(shí)間。鑒于此,本文以任務(wù)的完成時(shí)間最短為目標(biāo),建立了可分任務(wù)的周期性多趟調(diào)度優(yōu)化模型,并設(shè)計(jì)了全局優(yōu)化進(jìn)化算法對(duì)模型進(jìn)行求解,得到了最優(yōu)的服務(wù)器數(shù)、服務(wù)器調(diào)度順序、最優(yōu)調(diào)度趟數(shù)和最優(yōu)的任務(wù)分配方案。

1 周期性多趟調(diào)度優(yōu)化模型

分布式計(jì)算平臺(tái)由M+1臺(tái)服務(wù)器通過星型網(wǎng)絡(luò)互連,其中p0為主服務(wù)器,{pi|i∈{1,2,…,M}}為從服務(wù)器,li是連接p0和pi的通信鏈路,總?cè)蝿?wù)大小為W。p0負(fù)責(zé)劃分和調(diào)度任務(wù),并不參與任務(wù)計(jì)算。多趟調(diào)度過程分為內(nèi)部調(diào)度和最后一趟調(diào)度。設(shè)內(nèi)部調(diào)度趟數(shù)為n,則總趟數(shù)為n+1。設(shè)參與計(jì)算的從服務(wù)器數(shù)為m,且2≤m≤M。每趟調(diào)度所有服務(wù)器完成的任務(wù)量相同,記為V=W/(n+1)。

1.1 內(nèi)部調(diào)度

為了獲得最短的任務(wù)完成時(shí)間,內(nèi)部調(diào)度中每個(gè)服務(wù)器在相鄰兩趟調(diào)度之間不應(yīng)存在空閑時(shí)間。由圖1可以看出,t1～t2時(shí)間段內(nèi),服務(wù)器pσ1先后完成了子任務(wù)ασ1V的計(jì)算(sσ1+wσ1ασ1V)和傳輸(oσ1+z1ασ1V),同時(shí)pσ2先后完成了子任務(wù)ασ2V的傳輸(oσ2+z2ασ2V)和計(jì)算(sσ2+wσ2ασ2V),因此t1～t2時(shí)段內(nèi)可以建立恒等式關(guān)系。以此類推可得

ασ1V(zσ1+wσ1)+oσ1+sσ1=ασ2V(zσ2+wσ2)+

oσ2+sσ2=…=ασmV(zσm+wσm)+oσm+sσm

(1)

已知

ασ1+ασ2+…+ασm=1

(2)

利用式(1)將ασi用ασ1表示出來并代入式(2)得

圖1 可分任務(wù)的周期性多趟調(diào)度

定義下面2個(gè)新的變量

則式(3)可簡(jiǎn)化為

由式(1)(5)可得內(nèi)部調(diào)度的任務(wù)分配方案為

1.2 最后一趟調(diào)度

為了得到任務(wù)的最短完成時(shí)間,最后一趟調(diào)度中所有服務(wù)器必須同時(shí)完成計(jì)算,即所有服務(wù)器在T時(shí)刻同時(shí)完成計(jì)算,因此

sσi+wσiβσiV=oσi+1+zσi+1βσi+1V+sσi+1+wσi+1βσi+1V

(7)

為了簡(jiǎn)化公式,定義如下2個(gè)變量

式(8)可簡(jiǎn)化為

定義如下2個(gè)變量

由圖1可得任務(wù)的總完成時(shí)間為

T=n(ασ1V(zσ1+wσ1)+oσ1+sσ1)+
βσ1V(zσ1+wσ1)+oσ1+sσ1

(13)

調(diào)度的趟數(shù)越多,每趟調(diào)度分配的任務(wù)量就越少,服務(wù)器的空閑等待時(shí)間就越短。但是,由于平臺(tái)存在啟動(dòng)開銷,調(diào)度的趟數(shù)越多,額外的開銷越多,任務(wù)的總完成時(shí)間也就越大。任務(wù)的完成時(shí)間T隨調(diào)度趟數(shù)n的增加先減小后增加,因此可以通過尋找函數(shù)T(n)的轉(zhuǎn)折點(diǎn)找到調(diào)度趟數(shù)的最優(yōu)解。為此,需要首先確定n的上界和下界。由前文的分析可知,對(duì)于所有參與調(diào)度的服務(wù)器有βσi>0。展開式(12)可得

將V=W/(m+1)代入式(15),化簡(jiǎn)得

引入新的符號(hào)

1.4 σ的最優(yōu)解

給定服務(wù)器調(diào)度順序σ就可以求得最優(yōu)的n和m,從而可以通過式(6)(12)和(13)推導(dǎo)得到任務(wù)分配方案和任務(wù)的完成時(shí)間T。為了求得最優(yōu)的服務(wù)器調(diào)度順序,建立以下優(yōu)化模型

βσ1V(zσ1+wσ1)+oσ1+sσ1]

2 全局優(yōu)化進(jìn)化算法

所提模型僅含有一組變量σ=(σ1,σ2,…,σm),即服務(wù)器的調(diào)度順序,它是1～m的一個(gè)全排列?？梢?該問題屬于組合優(yōu)化問題。當(dāng)系統(tǒng)規(guī)模較大時(shí),傳統(tǒng)優(yōu)化算法很難在可容忍的時(shí)間范圍內(nèi)找到問題的全局最優(yōu)解或局部最優(yōu)解,往往需要借助智能優(yōu)化算法對(duì)問題進(jìn)行求解,而進(jìn)化算法作為智能優(yōu)化算法類的杰出代表,非常擅長(zhǎng)于求解組合優(yōu)化問題。因此,本文設(shè)計(jì)了一個(gè)新的全局優(yōu)化進(jìn)化算法求解多趟調(diào)度優(yōu)化模型。

2.1 編碼與適應(yīng)度函數(shù)

本文直接對(duì)模型的變量進(jìn)行編碼,即個(gè)體由I=(σ)來表示,其中σ表示服務(wù)器的調(diào)度順序。注意,為滿足模型的約束條件,個(gè)體的編碼必須包含所有參與計(jì)算的服務(wù)器編號(hào)且每個(gè)服務(wù)器編號(hào)僅能包含一次。任何服務(wù)器編號(hào)的缺失或者重復(fù)都將導(dǎo)致產(chǎn)生非法個(gè)體。

隨機(jī)產(chǎn)生N個(gè)個(gè)體作為初始種群。每產(chǎn)生一個(gè)個(gè)體,也就給定了一種服務(wù)器的調(diào)度順序,進(jìn)而可以求得當(dāng)前處理機(jī)調(diào)度順序下最優(yōu)的n和m,然后通過式(6)和式(12)可以推導(dǎo)得到任務(wù)的分配方案,最后通過式(13)求得T。將T的倒數(shù)作為個(gè)體的適應(yīng)度值,T越小,個(gè)體的適應(yīng)度值越大,表明個(gè)體越優(yōu)秀。

2.2 交叉與變異

本文采用部分匹配的交叉方法。對(duì)于任意兩個(gè)父代個(gè)體I1和I2

I1=(12,10,6,9,4,1,13,0,11,5,3,7,14,2,8)

I2=(14,12,10,8,4,11,6,13,5,2,1,0,9,3,7)

交叉的具體過程如下。

步驟1隨機(jī)選取兩個(gè)交叉點(diǎn)k1和k2,要求k1

I2=(14,12,10,8,4,|11,6,13,5,2,1,0,|9,3,7)

交叉產(chǎn)生的后代個(gè)體以概率ps進(jìn)行變異,本文采用對(duì)換變異的方法。對(duì)某一后代個(gè)體,隨機(jī)選取兩個(gè)變異位k1和k2,要求k1

交換這兩個(gè)位置的基因可以得到變異后的個(gè)體

p′=(12,10,6,9,3,1,13,0,11,5,4,7,14,2,8)

2.3 局部搜索算子

考慮到高性能分布式平臺(tái)的系統(tǒng)規(guī)模較為龐大,為了加快算法的收斂速度,本文為進(jìn)化算法引入局部搜索算子。其基本思想是對(duì)于任意一個(gè)個(gè)體I,計(jì)算個(gè)體的適應(yīng)度值f(I),搜索個(gè)體的鄰域空間,即按序交換其編碼相鄰兩位基因,更新個(gè)體I′,計(jì)算個(gè)體I′的適應(yīng)度值f(I′),若新個(gè)體I′的適應(yīng)度優(yōu)于原來的個(gè)體I,即f(I′)>f(I),則用新個(gè)體I′替換原來的個(gè)體I,并繼續(xù)在個(gè)體I′的鄰域空間內(nèi)執(zhí)行搜索;否則,不替換。

例如,對(duì)于個(gè)體p=(12,10,6,9,4,1,13,0,11,5,3,7,14,2,8),局部搜索的步驟為:交換第1位基因12和第2位基因10,得到新的個(gè)體p′=(10,12,6,9,4,1,13,0,11,5,3,7,14,2,8)。計(jì)算個(gè)體p和p′的適應(yīng)度值,如果p′的適應(yīng)度值大于p的適應(yīng)度值,即p′的任務(wù)完成時(shí)間小于p的任務(wù)完成時(shí)間,則交換這兩個(gè)基因位,否則,不交換。然后,對(duì)個(gè)體p的第2位和第3位基因執(zhí)行相同的操作,直到最后兩位完成試探交換。

2.4 全局優(yōu)化進(jìn)化算法

本文提出多趟調(diào)度全局優(yōu)化進(jìn)化算法的步驟如下。

步驟1初始化。產(chǎn)生初始種群P(t),設(shè)置代數(shù)t=0。

步驟2交叉。對(duì)于種群P(t)中的每個(gè)個(gè)體Ij,j=1,2,…,N,計(jì)算適應(yīng)度值,輪盤賭選擇N個(gè)個(gè)體存入交叉池。對(duì)交叉池中的N/2對(duì)個(gè)體按照交叉概率pc進(jìn)行部分匹配交叉,后代個(gè)體的集合記為O1,后代個(gè)體的數(shù)量記為R1。

步驟3變異。對(duì)于P(t)∪O1中的每個(gè)個(gè)體Ij,j=1,2,…,N+R1,隨機(jī)產(chǎn)生實(shí)數(shù)r∈[0,1],若r

步驟4局部搜索。對(duì)P(t)∪O1∪O2中的每個(gè)個(gè)體Ij,j=1,2,…,N+R1+R2,進(jìn)行局部搜索操作,更新后的個(gè)體集合記為O3。

步驟5選擇。首先根據(jù)精英保留策略從P(t)∪O3中選出E個(gè)最佳個(gè)體直接保存到下一代P(t+1)中,然后通過輪盤賭方法在P(t)∪O1∪O2中選擇剩下的N-E個(gè)個(gè)體放入P(t+1)中。

步驟6終止條件。若滿足終止條件,終止算法并輸出當(dāng)前種群的最優(yōu)個(gè)體。否則,跳到步驟2。

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

將本文算法與文獻(xiàn)[10-16]采用的IZ和IW方法以及Hsu等提出的ESCR算法[17]進(jìn)行了比較。平臺(tái)含有15臺(tái)服務(wù)器,每臺(tái)服務(wù)器的相關(guān)參數(shù)見表1。本文算法的相關(guān)參數(shù)設(shè)置如下:種群大小N=100,交叉概率pc=0.6,變異概率ps=0.02,精英保留數(shù)E=5,終止條件t=200。若增加平臺(tái)服務(wù)器的數(shù)量,可僅將終止條件的進(jìn)化代數(shù)適量調(diào)大,其他參數(shù)保持不變。給定測(cè)試任務(wù)大小W∈{100,500,1 000,5 000,10 000},表2給出了本文、IZ、IW和ESCR等4種調(diào)度算法的對(duì)比實(shí)驗(yàn)結(jié)果。由表2可以看出,給定任務(wù)量,4種調(diào)度算法求得的最優(yōu)調(diào)度趟數(shù)n、參與計(jì)算的處理機(jī)數(shù)m和處理機(jī)調(diào)度順序σ各不相同,因此任務(wù)的分配方案和最終獲得的任務(wù)完成時(shí)間也各不相同。對(duì)任一任務(wù),與其他調(diào)度算法相比,本文算法都能獲得最短的任務(wù)完成時(shí)間,可見模型和算法的有效性。

表1 分布式系統(tǒng)的參數(shù)

為了更直觀地體現(xiàn)各算法的性能差異,圖2給出了4種調(diào)度算法處理不同數(shù)量級(jí)任務(wù)的完成時(shí)間隨任務(wù)量的變化曲線,其中圖2a針對(duì)小規(guī)模任務(wù)W∈[100,1 000],圖2b針對(duì)中規(guī)模任務(wù)W∈[1 000,10 000],圖2c針對(duì)大規(guī)模任務(wù)W∈[10 000,100 000]。從圖2a可以看出,當(dāng)任務(wù)量相對(duì)較小時(shí),本文算法能夠獲得最短的任務(wù)完成時(shí)間,IW與IZ算法并沒有明顯的優(yōu)劣關(guān)系,而ESCR算法的任務(wù)完成時(shí)間最大。這是因?yàn)镋SCR算法并沒有令所有服務(wù)器同時(shí)完成任務(wù)計(jì)算,而且即便任務(wù)量較小的情況下也令所有的服務(wù)器都參與任務(wù)的計(jì)算,導(dǎo)致服務(wù)器的空閑等待時(shí)間較長(zhǎng),既降低了系統(tǒng)的資源利用率又沒有最大化任務(wù)的執(zhí)行效率。與已有算法相比,本文算法降低了至少25%的任務(wù)完成時(shí)間。從圖2b可以看出,當(dāng)任務(wù)量逐漸增大時(shí),ESCR和IW算法的時(shí)間性能并沒有明顯的優(yōu)劣之分, 而IZ和本文算法明顯優(yōu)于其他2種算法,本文算法時(shí)間性能最佳。從圖2c可以看出,當(dāng)任務(wù)量較大時(shí),各調(diào)度算法的時(shí)間性能差異隨著任務(wù)量的增大差距越來越大。ESCR算法獲得的任務(wù)完成時(shí)間最大(最差),其次是IW和IZ算法,本文算法在時(shí)間性能上有明顯的優(yōu)勢(shì),能夠最小化任務(wù)的完成時(shí)間。與已有算法相比,本文算法降低了至少43%的任務(wù)完成時(shí)間。

表2 4種算法的實(shí)驗(yàn)結(jié)果比較

(a)任務(wù)量從100到1 000

(b)任務(wù)量從1 000到10 000

(c)任務(wù)量從10 000到100 000圖2 4種算法的時(shí)間性能對(duì)比

4 結(jié) 論

隨著大數(shù)據(jù)時(shí)代的到來,對(duì)企業(yè)而言,數(shù)據(jù)即生產(chǎn)力,如何提高數(shù)據(jù)的處理效率受到越來越多的關(guān)注。本文以任務(wù)的完成時(shí)間最短為目標(biāo),建立了可分任務(wù)的周期性多趟調(diào)度優(yōu)化模型,并設(shè)計(jì)了全局優(yōu)化進(jìn)化算法對(duì)模型進(jìn)行求解,獲得了最優(yōu)的調(diào)度趟數(shù)、最優(yōu)的參與計(jì)算的服務(wù)器數(shù)、最優(yōu)的任務(wù)分配方案和最優(yōu)的處理機(jī)調(diào)度順序。實(shí)驗(yàn)結(jié)果表明,與已有調(diào)度算法相比,本文算法在任務(wù)執(zhí)行效率方面提升了至少25%的性能。