姚東鈮

(陜西學(xué)前師范學(xué)院 實(shí)驗(yàn)室與設(shè)備管理處， 陜西 西安　710100)

?

基于0-1互換算法的網(wǎng)格同構(gòu)平臺(tái)任務(wù)調(diào)度

姚東鈮

(陜西學(xué)前師范學(xué)院 實(shí)驗(yàn)室與設(shè)備管理處， 陜西 西安710100)

摘要：網(wǎng)格計(jì)算及其衍生的云計(jì)算是近年來興起的新技術(shù)，能夠給人們提供一個(gè)高級(jí)、強(qiáng)大的計(jì)算服務(wù)和信息數(shù)據(jù)資源管理平臺(tái).網(wǎng)格的核心是資源共享，其核心問題之一就是任務(wù)調(diào)度，它直接決定了資源的有效利用.針對(duì)網(wǎng)格計(jì)算中同構(gòu)計(jì)算平臺(tái)下的獨(dú)立任務(wù)的調(diào)度問題,采用局部搜索策略設(shè)計(jì)了一種基于0-1互換的調(diào)度算法，并使用MATLAB編寫程序，對(duì)算法進(jìn)行測(cè)試，結(jié)果表明該算法具有迭代次數(shù)少、調(diào)度效果好等優(yōu)點(diǎn).

關(guān)鍵詞：網(wǎng)格計(jì)算； 同構(gòu)平臺(tái)； 任務(wù)調(diào)度； 0-1互換算法

0引言

網(wǎng)格是一種計(jì)算和數(shù)據(jù)管理的基礎(chǔ)設(shè)施，能為各種社會(huì)活動(dòng)提供信息化支持，它是一個(gè)高級(jí)、強(qiáng)大的計(jì)算服務(wù)和信息數(shù)據(jù)資源管理平臺(tái).網(wǎng)格中的資源具有分布性、共享性、自相似性、動(dòng)態(tài)性、多樣性、自治性與管理的多重性等特點(diǎn).網(wǎng)格計(jì)算及其衍生的云計(jì)算是近年來興起的新技術(shù)[1-3]，網(wǎng)格的核心是資源共享，其任務(wù)調(diào)度直接決定了資源的有效利用而成為網(wǎng)格計(jì)算最核心的問題之一[4].

網(wǎng)格任務(wù)調(diào)度負(fù)責(zé)引導(dǎo)用戶提交任務(wù)并按照任務(wù)類型、所需資源及可用資源等情況安排運(yùn)行日程和策略.任務(wù)調(diào)度根據(jù)任務(wù)的需求，首先發(fā)現(xiàn)滿足條件的計(jì)算資源，然后從滿足條件的計(jì)算資源中根據(jù)特定的算法策略選擇一個(gè)合適的資源分配給任務(wù).在網(wǎng)格環(huán)境中，任務(wù)和資源的數(shù)目都比較大，任務(wù)和資源之間的關(guān)系也相對(duì)復(fù)雜，因此任務(wù)調(diào)度問題[5,6]是一項(xiàng)繁復(fù)而困難的工作.研究人員常常會(huì)對(duì)任務(wù)模型、資源模型等進(jìn)行若干假設(shè)的化繁為簡(jiǎn).本文中將對(duì)同構(gòu)計(jì)算平臺(tái)下獨(dú)立任務(wù)的調(diào)度算法進(jìn)行研究與分析.

1算法思想

1.1問題定義

與同構(gòu)相對(duì)的是異構(gòu)，異構(gòu)體現(xiàn)在網(wǎng)格中的計(jì)算資源是由若干處理機(jī)通過網(wǎng)絡(luò)連接起來的，其處理機(jī)之間的類型和處理速度各不相同.類型異構(gòu)的處理機(jī)結(jié)構(gòu)過于復(fù)雜，現(xiàn)實(shí)的需求也不是很高，并且通過虛擬機(jī)制(比如Java虛擬機(jī))可以在一定程度上解決處理機(jī)類型異構(gòu)的問題，因此通常的任務(wù)調(diào)度不考慮類型異構(gòu).在此基礎(chǔ)上，如果再假設(shè)任一獨(dú)立任務(wù)在所有處理機(jī)上具有相同的計(jì)算時(shí)間，那么問題就簡(jiǎn)化為平臺(tái)同構(gòu).

1.2基于0-1互換算法的任務(wù)調(diào)度

實(shí)際的調(diào)度中通常難以達(dá)到最優(yōu)化結(jié)果，即任務(wù)調(diào)度的下界.然而從一個(gè)初始解開始，每一步通過最小化各個(gè)處理機(jī)上的任務(wù)負(fù)載，在當(dāng)前鄰域內(nèi)尋找到一個(gè)更優(yōu)解，使得各個(gè)處理機(jī)負(fù)載基本相同，從而得到更短的調(diào)度長(zhǎng)度，實(shí)現(xiàn)目標(biāo)函數(shù)逐步優(yōu)化，直到不能進(jìn)一步改進(jìn)為止.上述過程是可以通過算法實(shí)現(xiàn)的.

圖1　0-1互換算法的任務(wù)調(diào)度流程圖

本文采用局部搜索[8-10]的策略，構(gòu)建0-1互換算法(IC)對(duì)同構(gòu)平臺(tái)的獨(dú)立任務(wù)調(diào)度問題進(jìn)行研究，其流程圖如圖1所示.具體地，先利用LS算法[11,12]進(jìn)行初始調(diào)度，將獨(dú)立任務(wù)調(diào)度到處理機(jī)；然后尋找負(fù)載最大和最小的處理機(jī)并計(jì)算其負(fù)載的差值；如果負(fù)載最大的處理機(jī)上和負(fù)載最小的處理機(jī)上存在任務(wù)滿足特定的交換條件：交換這兩個(gè)任務(wù)能夠減少調(diào)度長(zhǎng)度，則將這兩個(gè)任務(wù)交換；按照這樣的策略對(duì)當(dāng)前已調(diào)度的任務(wù)進(jìn)行不斷的調(diào)整以得到一個(gè)更優(yōu)化的調(diào)度結(jié)果，直到處理機(jī)的負(fù)載平衡或者找不到滿足交換條件的任務(wù)為止.完整的算法描述如下：

輸入：

任務(wù)集T={t1,t2,…,tn};處理機(jī)P={p1,p2,…,pm};

輸出：

Initial_LS(P,T); //利用LS算法進(jìn)行初始調(diào)度.

While(1)

{

//尋找負(fù)載最大和最小的處理機(jī)pmax和pmin

Lpmax=Lpmin=L(p1);pmax= pmin=p1;

For(i=2;i<=n;i++)

{

If(Lpmax

If(Lpmin>L(pi))then{Lpmin=L(pi);pmin=pi;}

}

//計(jì)算最大負(fù)載Lpmax與最小負(fù)載Lpmin差值

Diff=Lpmax-Lpmin;

If(Diff>Limit) then //預(yù)設(shè)閾值Limit

{

Flag=0；

//搜索負(fù)載最大的處理機(jī)pmax上的任務(wù)

For(i=1;i<= Num(pmax);i++)

{

Ti= pmax[i]; //pmax上的第i個(gè)任務(wù)

//搜索負(fù)載最小的處理機(jī)pmin上的任務(wù)

For(j=1;j<=Num(pmin);j++)

{

Tj= pmin[j]; //pmin上的第j個(gè)任務(wù)

Delta=Ti-Tj;

If(Delta>0 AND Delta

{

Flag=1; //滿足交換條件

//將Ti和Tj交換，并修改相應(yīng)的負(fù)載

pmax[i]=Tj;pmin[j]= Ti;

Break; //結(jié)束本輪循環(huán)搜索

}

}

}

//不滿足交換條件，返回結(jié)果1

If(Flag==0) then Exit(1);

}

else

{

Exit(0); //負(fù)載已經(jīng)平衡，返回結(jié)果0

}

}

在初始化階段使用常見的LS算法進(jìn)行初始化調(diào)度，由于后續(xù)任務(wù)調(diào)整階段的存在，初始調(diào)度算法選擇的基本思想是簡(jiǎn)單有效.

在任務(wù)調(diào)整階段首先需要的問題是選擇哪些處理機(jī)進(jìn)行任務(wù)交換.這里采用選擇負(fù)載最大和最小的處理機(jī)的策略；其次是選擇哪些任務(wù)進(jìn)行交換，這是算法的關(guān)鍵，基本原則是僅在兩個(gè)任務(wù)的交換能夠減少應(yīng)用的完成時(shí)間時(shí)才對(duì)兩個(gè)任務(wù)進(jìn)行交換.算法中采用的條件是0

在循環(huán)過程中不斷搜索負(fù)載最大和最小的處理機(jī)并比較其負(fù)載差值，若小于預(yù)先設(shè)定的閾值Limit則認(rèn)為已經(jīng)負(fù)載平衡.在上述的交換條件約束下，每次交換都會(huì)使得應(yīng)用的完成時(shí)間嚴(yán)格縮短.通過多次循環(huán)，直到處理機(jī)的負(fù)載已經(jīng)平衡或者不存在滿足交換條件的任務(wù)時(shí)，算法終止.

2仿真結(jié)果

實(shí)驗(yàn)先通過一個(gè)例子說明算法的運(yùn)行效果，然后通過比較對(duì)算法的調(diào)度質(zhì)量進(jìn)行分析，最后對(duì)算法時(shí)間性能進(jìn)行分析.實(shí)驗(yàn)使用MATLAB編寫程序進(jìn)行仿真，運(yùn)行環(huán)境為處理器Intel Core2 Duo T6500主頻2.1 GHz，內(nèi)存2 GB，操作系統(tǒng)Windows XP.

例子：任務(wù)數(shù)n為50，處理機(jī)數(shù)m為5，任務(wù)集合 {56,23,62,8,46,92,14,44,84,79,41,96,16,40,76,27,93,58,92,58,25,99,61,12,63,50,25,11,9,91,46,89,55,17,59,70,59,47,15,19,13,40,59,48,71,56,80,56,56,43}.使用LS算法進(jìn)行初始化調(diào)度，結(jié)果如表1所示，任務(wù)的初始調(diào)度長(zhǎng)度為522.LS的初始調(diào)度負(fù)載很不均衡，最大的負(fù)載差值為39.

表1　LS的初始調(diào)度

表2　調(diào)整后的調(diào)度

基于IC算法的調(diào)度過程：第一次負(fù)載最重的處理機(jī)p3的負(fù)載為522，負(fù)載最輕的處理機(jī)p2的負(fù)載為483，差值為39.依次檢查p2和p3的任務(wù)，發(fā)現(xiàn)任務(wù)t2=23和任務(wù)t11=41滿足交換條件，將它們交換.第二次負(fù)載最重的處理機(jī)p1和負(fù)載最輕的處理機(jī)p2的負(fù)載差值為18，交換其上的任務(wù)t1=56和任務(wù)t11=41.第三次負(fù)載交換p1的任務(wù)t11=41和p4的任務(wù)t31=46.依照算法經(jīng)過8次交換后得到的任務(wù)調(diào)度結(jié)果如表2所示，最大的負(fù)載差值已經(jīng)降低至1，可見該算法是有效的.

我們?cè)偻ㄟ^對(duì)比0-1互換算法(IC)和LS算法、BF(Bacterial Foraging)算法[13,14]的調(diào)度長(zhǎng)度，可以評(píng)價(jià)算法的調(diào)度質(zhì)量.這里使用平均負(fù)載作為參考值對(duì)算法得到的調(diào)度長(zhǎng)度做歸一化處理.歸一化的結(jié)果值越小則表明算法得到的結(jié)果越接近平均負(fù)載，調(diào)度長(zhǎng)度越小[15].對(duì)于正態(tài)分布的執(zhí)行時(shí)間，其均值Lmin=100，方差為10，處理機(jī)數(shù)m=16，任務(wù)數(shù)為100到1 000，步長(zhǎng)為100.結(jié)果如圖2所示，可見相比于LS算法和BF算法， 0-1互換算法(IC) 在不同的任務(wù)個(gè)數(shù)下的調(diào)度長(zhǎng)度最短，非常接近最優(yōu)值，具有很好的調(diào)度質(zhì)量.

圖2　不同算法調(diào)度長(zhǎng)度的比較

圖3　IC算法迭代次數(shù)隨處理機(jī)數(shù)的變化

圖4　IC算法迭代次數(shù)隨任務(wù)數(shù)的變化

迭代次數(shù)直接反應(yīng)了算法的運(yùn)行時(shí)間，可以用來分析算法的時(shí)間性能.下面對(duì)滿足正態(tài)分布(均值為100，方差為10)的任務(wù)執(zhí)行時(shí)間在不同任務(wù)數(shù)n和處理機(jī)數(shù)m下進(jìn)行仿真實(shí)驗(yàn)并記錄相應(yīng)迭代次數(shù).首先，當(dāng)n分別為1 000、2 000和3 000時(shí)，隨著m由4增加到24(步長(zhǎng)為4)迭代次數(shù)逐步增加，如圖3所示.其次，當(dāng)m分別為4、12和24時(shí)，隨著n由100增加到3 000(步長(zhǎng)為100)迭代次數(shù)略有增加，且當(dāng)任務(wù)數(shù)比較多時(shí)穩(wěn)定在一個(gè)固定的迭代次數(shù)水平附近，如圖4所示.對(duì)比圖3和圖4可以看出，本文中的IC算法迭代次數(shù)隨處理器數(shù)增加而增長(zhǎng)的較快，但隨任務(wù)數(shù)增加而增長(zhǎng)的不明顯.因此對(duì)于需要在相對(duì)固定的硬件處理設(shè)備上執(zhí)行大量計(jì)算任務(wù)時(shí)該算法是非常適用的.最后，在不同任務(wù)數(shù)n和處理機(jī)數(shù)m下進(jìn)行了180次仿真實(shí)驗(yàn)，記錄相應(yīng)迭代次數(shù)，如圖5所示，結(jié)果表明即使對(duì)于較大的任務(wù)數(shù)和處理器數(shù)，迭代次數(shù)都很少超過180，可見算法具有非常好的時(shí)間性能.

圖5　IC算法迭代次數(shù)的變化

3結(jié)論

網(wǎng)格計(jì)算及其衍生的云計(jì)算是近年來興起的新技術(shù)，其核心問題之一的任務(wù)調(diào)度決定了資源是否有效利用.0-1互換算法作為一種局部搜索調(diào)度算法，具有迭代次數(shù)少、調(diào)度效果好等優(yōu)點(diǎn).本文就網(wǎng)格計(jì)算中同構(gòu)計(jì)算平臺(tái)下的獨(dú)立任務(wù)的調(diào)度問題設(shè)計(jì)了基于0-1互換的優(yōu)化算法，并使用MATLAB編寫了算法程序.仿真結(jié)果表明，該算法是可行的，并收到了良好的效果.

參考文獻(xiàn)

[1] 都志輝,陳渝,劉鵬.網(wǎng)格計(jì)算[M].北京:清華大學(xué)出版社,2002.

[2] 胡引翠.網(wǎng)格計(jì)算技術(shù)的應(yīng)用及其發(fā)展趨勢(shì)[J].測(cè)繪通報(bào),2005(3):23-26.

[3] 王義立,陳曉江,馮健,等.網(wǎng)格計(jì)算:現(xiàn)狀與進(jìn)展[J].微電子學(xué)與計(jì)算機(jī),2006,23(10):181-183,186.

[4] 羅作民,張景,李軍懷,等.網(wǎng)格計(jì)算及其關(guān)鍵技術(shù)綜述[J].計(jì)算機(jī)工程與應(yīng)用,2003,39(30):18-22.

[5] 許元飛.網(wǎng)格計(jì)算中任務(wù)調(diào)度算法的仿真研究[J].計(jì)算機(jī)仿真,2011,28(8):134-137.

[6] 崔玉寶,賈振華,侯志國(guó),等.網(wǎng)格任務(wù)調(diào)度算法研究[J].微計(jì)算機(jī)信息,2006,22(15):109-111.

[7] 康一梅,鄭應(yīng)平.同等并行處理機(jī)上獨(dú)立任務(wù)的調(diào)度[J].自動(dòng)化學(xué)報(bào),1997,23(1):81-84.

[8] 鄒恒明.算法之道[M].北京:機(jī)械工業(yè)出版社,2010.

[9] 唐晉韜,王挺,王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報(bào),2011,22(10):2 279-2 290.

[10] 陳濤.基于加速遺傳算法的選擇性支持向量機(jī)集成[J].計(jì)算機(jī)應(yīng)用研究,2011,28(1):139-141.

[11] 李紅英.機(jī)器有使用限制的兩臺(tái)同類機(jī)排序的在線LS 算法[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,32(9):1 134-1 137.

[12] 丁偉.速度相同的具有m-2臺(tái)通用機(jī)的兩組工件的LS算法分析[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,49(6):1-5.

[13] 周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(20):16-21.

[14] 朱云龍,陳瀚寧,申海.生物啟發(fā)計(jì)算[M].北京:清華大學(xué)出版社,2013.

[15] 劉宴兵,尚明生,肖云鵬.網(wǎng)格高性能調(diào)度及資源管理技術(shù)[M].北京:科學(xué)出版社,2010.

Analysis of 0-1 interchange algorithm for task scheduling

in isomorphic platform of grid computing

YAO Dong-ni

( Department of Laboratory and Equipment Management, Shaanxi Xueqian Normal University, Xi′an 710100, China)

Abstract:Grid computing and cloud computing is booming at present,providing advanced and powerful computing services and information management platforms to the whole society.Task scheduling is one of the most important technologies of grid computing.The paper is to analyze the 0-1 interchange algorithm for task scheduling in isomorphic platform of grid computing.It contains choiceness of algorithm steps based on local search principle and building up test program in MATLAB for performance estimation,etc.Results of simulation show that the algorithm is effective and reliable.

Key words:grid computing； isomorphic platform； task scheduling； 0-1 interchange algorithm

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1000-5811(2015)02-0169-04

作者簡(jiǎn)介:姚東鈮(1982-)，女，陜西西安人，工程師，研究方向：計(jì)算機(jī)數(shù)據(jù)挖掘技術(shù)、實(shí)驗(yàn)室管理

收稿日期:*2014-11-12 *2014-12-23