1、 自適應(yīng)鄰域的多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法摘要:針對(duì)網(wǎng)格計(jì)算中的多目標(biāo)網(wǎng)格任務(wù)調(diào)度問題,提出了一種基于自適應(yīng)鄰域的多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法。該算法通過求解多個(gè)網(wǎng)格任務(wù)調(diào)度目標(biāo)函數(shù)的非劣解集,采用自適應(yīng)鄰域的方法來保持網(wǎng)格任務(wù)調(diào)度多目標(biāo)解集的分布性,嘗試解決網(wǎng)格任務(wù)調(diào)度中多目標(biāo)協(xié)同優(yōu)化問題。實(shí)驗(yàn)結(jié)果證明,該算法能夠有效地平衡時(shí)間維度和費(fèi)用維度目標(biāo),提高了資源的利用率和任務(wù)的執(zhí)行效率,與min-min和max-min算法相比具有較好的性能。關(guān)鍵詞:網(wǎng)格任務(wù)調(diào)度算法;多目標(biāo)進(jìn)化算法;自適應(yīng)鄰域;任務(wù)調(diào)度multi-objective evolutionary algorithm forgrid job sc

2、heduling based on adaptive neighborhood英文作者名yang ming1,2*, xue sheng-jun2, chen liang1, liu yong-sheng1英文地址(1.zhejiang meteorological information network center, hangzhou zhejiang 310017, china;2.college of computer and software, nanjing university of information science and technology, nanjing jian

3、gsu 210044, china)abstract: a new adaptive neighborhood multi-objective grid task scheduling algorithm (anmo-gtsa) was proposed in this paper for the multi-objective job scheduling collaborative optimization problem in grid computing. in the anmo-gtsa, an adaptive neighborhood method was applied to

4、find the non-inferior set of solutions and maintain the diversity of the multi-objective job scheduling population. the experimental results indicate that the algorithm proposed in this paper can not only balance the multi-objective job scheduling, but also improve the resource utilization and effic

5、iency of task execution. moreover, the proposed algorithm can achieve better performance on time-dimension and cost-dimension than the traditional min-min and max-min algorithms.key words: grid job scheduling algorithm; multi-objective evolutionary algorithm; adaptive neighborhood; job scheduling0引言

6、在資源異構(gòu)高效的網(wǎng)格計(jì)算中,網(wǎng)格環(huán)境涉及網(wǎng)格用戶、網(wǎng)格資源管理者、虛擬組織管理者等多個(gè)實(shí)體,不同實(shí)體間對(duì)管理機(jī)制、平安策略、調(diào)度時(shí)間和費(fèi)用等目標(biāo)都不同,有的甚至相互沖突。因此,如何通過資源管理與調(diào)度算法協(xié)調(diào)這些不同實(shí)體間和同類實(shí)體內(nèi)部的不同目標(biāo)要求是當(dāng)前網(wǎng)格計(jì)算中的熱點(diǎn)問題1。近年來,國內(nèi)外研究人員提出了不少高效的網(wǎng)格任務(wù)調(diào)度算法,其中比擬典型的有min-min、max-min和sufferage等2-5,這些調(diào)度算法主要以任務(wù)完成時(shí)間作為單一調(diào)度目標(biāo)。針對(duì)多目標(biāo)任務(wù)的調(diào)度算法有min-min啟發(fā)式調(diào)度算法6和多目標(biāo)沖突度遺傳算法7等,這些算法主要采用權(quán)重法將多個(gè)目標(biāo)函數(shù)聚合成單一的目標(biāo)函數(shù),

7、進(jìn)行單目標(biāo)求解。權(quán)重法具有時(shí)間復(fù)雜度低、便于實(shí)現(xiàn)的特點(diǎn)。但是,這些算法主要通過調(diào)整權(quán)重來平衡多個(gè)目標(biāo),而權(quán)重的取值具有隨意性,影響了調(diào)度算法的性能,這些算法自身也存在一些固有的缺陷,很難滿足網(wǎng)格環(huán)境用戶同時(shí)對(duì)多個(gè)目標(biāo)的需求。另外,單目標(biāo)優(yōu)化算法僅能根據(jù)聚合函數(shù)來得到?jīng)Q策空間中一個(gè)可行解,降低了最終解的質(zhì)量,缺乏靈活性與可擴(kuò)展性。而多目標(biāo)優(yōu)化問題的解并非唯一的,它存在一個(gè)最優(yōu)解集或非支配解集(non-dominated solutions set, ndset),集合中元素稱為pareto最優(yōu)解或非劣最優(yōu)解8-9。因此,更為合理的途徑是采用多目標(biāo)最優(yōu)化算法來解決多目標(biāo)網(wǎng)風(fēng)格度問題。鑒于此,本文通

8、過網(wǎng)格任務(wù)調(diào)度的多個(gè)效用函數(shù)指標(biāo),運(yùn)用多目標(biāo)最優(yōu)化理論及其算法來解決網(wǎng)格任務(wù)調(diào)度中多目標(biāo)協(xié)同問題,提出了一種基于自適應(yīng)鄰域的多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法(a new adaptive neighborhood multi-objective grid task scheduling algorithm, anmo-gtsa)。該算法采用一種新的基于自適應(yīng)鄰域修剪策略,不僅可以獲得多個(gè)相互沖突的調(diào)度目標(biāo)的最優(yōu)解,還可以改善負(fù)載均衡的問題。在通常情況下,最短任務(wù)完成時(shí)間目標(biāo)和最低費(fèi)用目標(biāo)在一般情況下是沖突的,無法在這兩個(gè)目標(biāo)上同時(shí)獲得最優(yōu)的調(diào)度結(jié)果,通過該算法可以平衡這兩個(gè)目標(biāo),使得計(jì)算節(jié)點(diǎn)的分配更均勻

9、,并且將其與傳統(tǒng)算法min-min和max-min進(jìn)行了比照實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果驗(yàn)證了新算法的優(yōu)越性。1調(diào)度模型和問題定義從用戶的角度來說,總是希望分配到的資源能夠用最少的時(shí)間、最小的費(fèi)用完成所有提交的任務(wù);而從資源提供者角度看,完成時(shí)間越少、資源性能越高,定價(jià)費(fèi)用自然也會(huì)越高。資源的可用性越高,它完成單位計(jì)算量的費(fèi)用越高;請(qǐng)求資源的用戶數(shù)量越多,資源的價(jià)格越高。資源的價(jià)格和任務(wù)完成時(shí)間對(duì)網(wǎng)格用戶的本錢起決定作用,都是評(píng)估模型中重要的指標(biāo)。網(wǎng)格任務(wù)調(diào)度相關(guān)定義如下:1)用集合r=r1,r2,rm表示m個(gè)計(jì)算資源,其中rj表示第j個(gè)資源。2)用集合t=t1,t2,tn表示n個(gè)任務(wù),其中ti表示第i個(gè)任

10、務(wù)。3)任務(wù)的執(zhí)行時(shí)間用mn階矩陣et表示;eti j表示任務(wù)ti在處理節(jié)點(diǎn)rj上的預(yù)期執(zhí)行時(shí)間,eti j=表示任務(wù)ti不能在處理節(jié)點(diǎn)rj上執(zhí)行。下面給出網(wǎng)格任務(wù)調(diào)度方面的最優(yōu)跨度和費(fèi)用效能這兩個(gè)問題的描述。最優(yōu)跨度問題假設(shè)不考慮計(jì)算任務(wù)的跨節(jié)點(diǎn)執(zhí)行,用戶向系統(tǒng)提交的任務(wù)就是網(wǎng)風(fēng)格度單元進(jìn)行任務(wù)分配的最小單位,大型計(jì)算任務(wù)的分解由用戶來完成,并且任務(wù)之間是獨(dú)立的。任務(wù)調(diào)度問題是將n個(gè)任務(wù)集t以合理的方式調(diào)度到m個(gè)處理節(jié)點(diǎn)集r上執(zhí)行,以盡可能地到達(dá)預(yù)定目標(biāo)。任務(wù)調(diào)度的結(jié)果用nm的二維矩陣w來表示,當(dāng)wi j=1(wi jw)表示將任務(wù)將ti調(diào)度到處理節(jié)點(diǎn)rj上執(zhí)行;否那么wi j=0。為了便于

11、描述,定義以下參數(shù)和符號(hào):makespan表示最優(yōu)跨度;bj表示處理節(jié)點(diǎn)rj的最早可用時(shí)間;cti j表示任務(wù)ti在處理節(jié)點(diǎn)rj上的預(yù)期完成時(shí)間。一般有cti j=bj+eti j。當(dāng)任務(wù)ti被調(diào)度到處理節(jié)點(diǎn)rj上執(zhí)行時(shí),令cti=cti j,表示任務(wù)ti執(zhí)行完成的時(shí)間,那么任務(wù)集t的執(zhí)行完成時(shí)間makespan(t)= maxtit(cti),調(diào)度目標(biāo)是要獲得盡量小的makespan,即min(makespan)。第3期 楊明等:自適應(yīng)鄰域的多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法計(jì)算機(jī)應(yīng)用 第32卷費(fèi)用效能問題當(dāng)需要縮短運(yùn)行時(shí)間時(shí),需要犧牲更多的cpu使用費(fèi)用來補(bǔ)償,即處理能力越高的cpu,其使用費(fèi)用通常越

12、高。因此,如何能使cpu的使用費(fèi)用和運(yùn)行時(shí)間同時(shí)到達(dá)最小值,是一個(gè)復(fù)雜的問題。假設(shè)cost表示應(yīng)該執(zhí)行完所有任務(wù)所需的總費(fèi)用;uj表示資源rj在單位時(shí)間內(nèi)的價(jià)格;ci j表示任務(wù)ti在資源rj上的費(fèi)用,那么任務(wù)ti的執(zhí)行費(fèi)用ci j和總費(fèi)用cost可表示為:ci j=eti juj(1)cost=ni=1mj=1ci j(2)那么調(diào)度求解目標(biāo)是盡量小的cost,即min(cost)?；谏厦嫣岢龅淖顑?yōu)跨度和費(fèi)用效能兩個(gè)問題的模型,多目標(biāo)網(wǎng)格任務(wù)調(diào)度的總目標(biāo)函數(shù)可以表示為：min f(makespan, cost)(3)式(3)表示任務(wù)調(diào)度的目標(biāo)是在執(zhí)行完所有任務(wù)后,取得盡量少的總執(zhí)行時(shí)間和盡量

13、小的總花費(fèi),使該兩個(gè)目標(biāo)同時(shí)到達(dá)最優(yōu)。2自適應(yīng)鄰域多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法2.1自適應(yīng)鄰域策略為了防止算法的分布性在進(jìn)化中受到破壞的現(xiàn)象以及解決鄰域半徑的取值問題,首先,應(yīng)使半徑變化率的自適應(yīng)調(diào)整曲線在davg處緩慢改變,從而提高距離接近平均距離的個(gè)體的鄰域半徑。其次,當(dāng)davg和dmin相差較大時(shí),確保自適應(yīng)調(diào)整曲線不會(huì)趨于直線型。最后,保證種群中較優(yōu)個(gè)體仍具有一定的分布性。同時(shí),為了能盡可能地保存較好的分布性,應(yīng)更平滑davg處的自適應(yīng)調(diào)整曲線。如圖1所示。圖片圖1自適應(yīng)調(diào)整曲線由于sigmoid函數(shù)在線性和非線性行為之間顯現(xiàn)出較好的平衡9,所以采用sigmoid函數(shù)作為自適應(yīng)調(diào)整曲線。求解

14、鄰域半徑的自適應(yīng)調(diào)整公式如式(4)所示。r=rmax-rmin1+expa(r-dmin)davg-dmin+rmin,ddminrmin,dn,那么利用算法3進(jìn)行修剪操作,降低其大小,直到其規(guī)模等于任務(wù)數(shù)n;假設(shè)|ndset|n,那么從r(g)中選取支配個(gè)體填滿,直到其規(guī)模等于任務(wù)數(shù)n。第6步結(jié)束條件。以進(jìn)化代數(shù)作為終止條件,假設(shè)滿足終止條件,那么將ndset中的所有非支配個(gè)體作為最終的輸出群體;否那么,ndset保存到x(g+1)中,令g=g+1,轉(zhuǎn)第3步。3實(shí)驗(yàn)分析為了檢驗(yàn)所提自適應(yīng)鄰域多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法模型的性能,首先討論了實(shí)驗(yàn)的參數(shù)設(shè)置,然后通過與其他網(wǎng)格任務(wù)調(diào)度算法,如max-

15、min和min-min算法進(jìn)行了比擬分析,說明了anmo-gtsa算法的優(yōu)越性。3.1實(shí)驗(yàn)參數(shù)設(shè)置在網(wǎng)格環(huán)境中,由于任務(wù)到達(dá)時(shí)間的隨機(jī)性以及計(jì)算資源的動(dòng)態(tài)性,所以網(wǎng)格環(huán)境中一般需要?jiǎng)討B(tài)調(diào)度算法10。本節(jié)在批處理模式下分別針對(duì)不同的任務(wù)數(shù)和處理節(jié)點(diǎn)數(shù)進(jìn)行了實(shí)驗(yàn)。模擬實(shí)驗(yàn)的參數(shù)設(shè)置如下:1)anmo-gtsa算法采用實(shí)數(shù)編碼,交叉概率0.85,變異概率0.01,種群規(guī)模為100,進(jìn)化代數(shù)為300,適應(yīng)度評(píng)價(jià)次數(shù)為30000,算法的運(yùn)行代數(shù)為評(píng)價(jià)個(gè)體的數(shù)目除以種群規(guī)模。2)每個(gè)任務(wù)在各個(gè)處理節(jié)點(diǎn)上的執(zhí)行時(shí)間滿足均勻分布;任務(wù)的到達(dá)時(shí)間服從泊松分布。3)處理節(jié)點(diǎn)的失效率在區(qū)間110-4110-3內(nèi)均勻

16、選擇。4)在不同數(shù)目的任務(wù)集進(jìn)行實(shí)驗(yàn)時(shí),處理節(jié)點(diǎn)數(shù)為10,任務(wù)數(shù)的范圍是1001000,間隔為100;在不同數(shù)目的處理節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)時(shí),任務(wù)數(shù)為500,處理節(jié)點(diǎn)數(shù)為10100,間隔為10。每個(gè)實(shí)驗(yàn)都分別選擇了不同任務(wù)集和計(jì)算節(jié)點(diǎn)集進(jìn)行了100 次,將100次實(shí)驗(yàn)結(jié)果取平均得到最終的實(shí)驗(yàn)結(jié)果。3.2實(shí)驗(yàn)結(jié)果與性能分析仿真實(shí)驗(yàn)分為兩局部:1)網(wǎng)格系統(tǒng)是由10個(gè)網(wǎng)格資源節(jié)點(diǎn)組成,任務(wù)數(shù)為1001000的任務(wù)集合組成,間隔為100;2)網(wǎng)格系統(tǒng)是由500個(gè)任務(wù)數(shù)組成,網(wǎng)格資源數(shù)為10100的網(wǎng)格資源節(jié)點(diǎn)集合組成,間隔為10。為了使實(shí)驗(yàn)數(shù)據(jù)具有穩(wěn)定性,每組實(shí)驗(yàn)均進(jìn)行屢次,用其平均值進(jìn)行性能分析。圖3為在不

17、同任務(wù)數(shù)情況下，各種調(diào)度算法得到的執(zhí)行時(shí)間和費(fèi)用性能比擬曲線圖。圖4為在不同資源節(jié)點(diǎn)數(shù)情況下，各種調(diào)度算法得到的執(zhí)行時(shí)間和費(fèi)用性能比擬曲線圖。時(shí)間維度定義為調(diào)度方案中所有的任務(wù)所獲得的時(shí)間性能效用總和。從圖3(a)和圖4(a)可看出,anmo-gtsa時(shí)間性能效用優(yōu)于max-min和min-min算法。費(fèi)用維度定義調(diào)度方案中所有的任務(wù)所獲得的費(fèi)用性能效用總和。從圖3(b)和圖4(b)可看出,anmo-gtsa費(fèi)用性能效用優(yōu)于max-min和min-min算法。從實(shí)驗(yàn)結(jié)果數(shù)據(jù)可看出,由于anmo-gtsa算法綜合考慮了執(zhí)行時(shí)間和費(fèi)用性能效用,所以其執(zhí)行時(shí)間和費(fèi)用性能效用都優(yōu)于max-min和mi

18、n-min算法。圖片圖3anmo-gtsa、max-min和min-min在不同任務(wù)數(shù)下的性能比擬圖片圖4anmo-gtsa、max-min和min-min在不同網(wǎng)格資源節(jié)點(diǎn)數(shù)下的性能比擬為了分析算法在負(fù)載均衡方面的性能,從第一局部實(shí)驗(yàn)中,選擇由100個(gè)任務(wù)數(shù)組成,網(wǎng)格資源節(jié)點(diǎn)數(shù)為10的網(wǎng)格資源節(jié)點(diǎn)集合組成的網(wǎng)格系統(tǒng)。圖5顯示了各種調(diào)度算法的映射能力。從圖中可看出,anmo-gtsa算法在負(fù)載均衡性能方面比max-min和min-min算法有較大改善。主要由于以下原因:anmo-gtsa算法具有解決多個(gè)任務(wù)調(diào)度目標(biāo)的最優(yōu)解的能力,能在一定程度上平衡負(fù)載。而min-min算法中每個(gè)資源的負(fù)載極不

19、平衡,主要原因在于該算法將執(zhí)行時(shí)間最短的任務(wù)分配在負(fù)載最小的資源處理節(jié)點(diǎn)上,這導(dǎo)致執(zhí)行時(shí)間長的任務(wù)分配到負(fù)載較大的資源處理節(jié)點(diǎn)上。綜上所述,本文提出的anmo-gtsa算法在不同的網(wǎng)格系統(tǒng)下都表現(xiàn)得較好,在處理執(zhí)行時(shí)間和費(fèi)用這兩個(gè)任務(wù)調(diào)度目標(biāo)時(shí),能使這兩個(gè)目標(biāo)同時(shí)到達(dá)最優(yōu),驗(yàn)證了anmo-gtsa算法的可行性和有效性。圖片圖5anmo-gtsa、max-min和min-min在10個(gè)網(wǎng)格資源節(jié)點(diǎn)和100個(gè)任務(wù)數(shù)下的映射圖4結(jié)語網(wǎng)格任務(wù)調(diào)度問題是網(wǎng)格計(jì)算中一個(gè)至關(guān)重要的問題,它的調(diào)度算法將直接影響到網(wǎng)格環(huán)境中任務(wù)執(zhí)行的效率與結(jié)果。另外,傳統(tǒng)的單目標(biāo)任務(wù)調(diào)度方式無法有效地滿足網(wǎng)格環(huán)境個(gè)體的多目標(biāo)需

20、求,必須有合理的管理模式和多目標(biāo)調(diào)度算法才能充分地發(fā)揮網(wǎng)格的特性。本文針對(duì)網(wǎng)格任務(wù)調(diào)度的特點(diǎn)提出了一個(gè)基于自適應(yīng)鄰域多目標(biāo)網(wǎng)格任務(wù)調(diào)度模型;根據(jù)當(dāng)代種群本身的情況,設(shè)計(jì)了一種基于自適應(yīng)鄰域多目標(biāo)網(wǎng)風(fēng)格度算法,該算法采用的自適應(yīng)鄰域的策略,改善了算法的性能;通過與max-min和min-min算法的比照實(shí)驗(yàn)說明，該算法在處理網(wǎng)格任務(wù)調(diào)度的多目標(biāo)問題,表現(xiàn)出較優(yōu)秀的效果,使用該算法處理網(wǎng)格任務(wù)調(diào)度問題,是一個(gè)有效的方法。參考文獻(xiàn):1都志輝, 陳渝, 劉鵬. 網(wǎng)格計(jì)算m.北京:清華大學(xué)出版社,2023:3-16.2maheswaran m, ali s, siegel h j, et al. dyn

21、amic matching and scheduling of a class of independent tasks onto heterogeneous computing systems c/ hcw99: proceedings of the 8th heterogeneous computing workshop. washington, dc: ieee computer society, 1999:30-44.3maheswaran m, ali s, siegel h j, et al. a comparison of dynamic strategies for mappi

22、ng a class of independent tasks onto heterogeneous computing systems r. west lafayette, indiana: purdue university, school of electrical and computer engineering, 1999.4wu m y, shu w, zhang h. segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems c/ proceedings of the 9th ieee heterogeneous computing workshop. washington, dc: ieee computer society, 2000:375-385.5casanova h, legrand a, zagorodnov d,