基于0-1互換算法的網(wǎng)格同構平臺任務調度

姚東鈮

(陜西學前師范學院 實驗室與設備管理處， 陜西 西安　710100)

?

基于0-1互換算法的網(wǎng)格同構平臺任務調度

姚東鈮

(陜西學前師范學院 實驗室與設備管理處， 陜西 西安710100)

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

關鍵詞：網(wǎng)格計算； 同構平臺； 任務調度； 0-1互換算法

0引言

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

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

1算法思想

1.1問題定義

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

1.2基于0-1互換算法的任務調度

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

圖1　0-1互換算法的任務調度流程圖

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

輸入：

任務集T={t1,t2,…,tn};處理機P={p1,p2,…,pm};

輸出：

Initial_LS(P,T); //利用LS算法進行初始調度.

While(1)

{

//尋找負載最大和最小的處理機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;}

}

//計算最大負載Lpmax與最小負載Lpmin差值

Diff=Lpmax-Lpmin;

If(Diff>Limit) then //預設閾值Limit

{

Flag=0；

//搜索負載最大的處理機pmax上的任務

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

{

Ti= pmax[i]; //pmax上的第i個任務

//搜索負載最小的處理機pmin上的任務

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

{

Tj= pmin[j]; //pmin上的第j個任務

Delta=Ti-Tj;

If(Delta>0 AND Delta

{

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

//將Ti和Tj交換，并修改相應的負載

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

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

}

}

}

//不滿足交換條件，返回結果1

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

}

else

{

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

}

}

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

在任務調整階段首先需要的問題是選擇哪些處理機進行任務交換.這里采用選擇負載最大和最小的處理機的策略；其次是選擇哪些任務進行交換，這是算法的關鍵，基本原則是僅在兩個任務的交換能夠減少應用的完成時間時才對兩個任務進行交換.算法中采用的條件是0

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

2仿真結果

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

例子：任務數(shù)n為50，處理機數(shù)m為5，任務集合 {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算法進行初始化調度，結果如表1所示，任務的初始調度長度為522.LS的初始調度負載很不均衡，最大的負載差值為39.

表1　LS的初始調度

表2　調整后的調度

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

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

圖2　不同算法調度長度的比較

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

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

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

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

3結論

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

參考文獻

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

[2] 胡引翠.網(wǎng)格計算技術的應用及其發(fā)展趨勢[J].測繪通報,2005(3):23-26.

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

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

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

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

[7] 康一梅,鄭應平.同等并行處理機上獨立任務的調度[J].自動化學報,1997,23(1):81-84.

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

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

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

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

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

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

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

[15] 劉宴兵,尚明生,肖云鵬.網(wǎng)格高性能調度及資源管理技術[M].北京:科學出版社,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

中圖分類號：TP393

文獻標志碼：A

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

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

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