計算密集型與數據密集型混合網格作業調度算法*

郝永生，盧俊文，劉冠峰，溫 娜

(1.南京信息工程大學網絡信息中心,江蘇 南京 210044;2.廈門理工大學，福建 廈門 361024；3.蘇州大學先進數據分析研究中心，江蘇 蘇州 215006；4.南京信息工程大學大氣科學學院，江蘇 南京 210044)

計算密集型與數據密集型混合網格作業調度算法*

郝永生1，盧俊文2，劉冠峰3，溫 娜4

(1.南京信息工程大學網絡信息中心,江蘇 南京 210044;2.廈門理工大學，福建 廈門 361024；3.蘇州大學先進數據分析研究中心，江蘇 蘇州 215006；4.南京信息工程大學大氣科學學院，江蘇 南京 210044)

針對計算密集型作業與數據密集型作業混合情況，在一個作業有時間限制的動態環境中，對傳統的網格作業調度方法進行擴展，提出了三種網格作業調度啟發式算法:Emin-min、Ebest、Esufferage。并在一個由多個Cluster組成的、通過高速網絡連接的網格模型上，對三種算法進行驗證。與Min-min算法的比較結果顯示：三種算法均優于Min-min算法。與ASJS算法比較結果顯示：Emin-min減少了等待時間與作業的makespan; Esufferage算法以減少作業完成量為代價，減少了作業的等待時間及makespan; Ebest在完成作業數量上與ASJS基本保持一致，但卻增加了作業的等待時間與makespan。總體上，Emin-min具有比較大的優勢。

計算密集；數據密集；作業調度；平均執行時間

1 引言

傳統的網格作業調度算法，或者是針對計算密集型作業[1,2]，或者是針對數據密集型[3,4]作業,只有少數網格作業調度算法同時考慮這兩種作業[4,5]。

基于計算密集型的網格作業調度方法包括：Min-min、Max-min、Sufferage、Fast-fit、Best-fit等[1,2]。Min-min的思想是：計算參與映射事件的每個任務在各個機器上的期望完成時間，找到每個任務的最早完成時間及其對應的機器；從中找出具有最小最早完成時間的任務，將該任務指派給取最小完成時間的機器，直至所有作業完成。Max-min算法非常類似于Min-min算法，同樣要計算每一任務在任一可用機器上的最早完成時間，不同的是Max-Min算法首先調度大任務，即選擇最早完成時間最大的任務映射到所對應的機器上。Sufferage通過計算每個作業Sufferage值，再選擇使Sufferage值最大時的作業-資源配對進行分配。一個作業的Sufferage值指這個作業最小完成時間與次小完成時間的差，其值部分反映了如果不進行這樣分配帶來的損失。Fast-fit試圖將作業分配給最快的資源節點。Best-fit總是分配給最適合的作業，即在確保完成時間(Deadline)的情況下，盡量推遲作業的完成時間。

Venugopal S[3]針對數據密集型作業提出了一種基于集合覆蓋問題(Set Covering Probelm)的調度算法。任務由若干作業組成，不同作業需要訪問不同的數據塊，通過不同策略復制這些數據塊，達到提高執行速度的目的。Kolodziej J等人[4]從數據復制、數據分割、數據權限控制、數據傳輸等方面對數據密集型作業進行了分析，提出了數據感知模型(Data-Aware Schedulers)，并與傳統的數據調度算法相結合，以適應數據密集型作業調度的要求。Chang R-S等[5]提出了一種自適應的評分機制ASJS(Adaptive Scoring Job Scheduling algorithm)，根據資源的特性及網絡特性對資源評分，優先分配給得分高的資源。Valliyamma C[6]認為資源調度就是一種交易，交易雙方既考慮資源本身的特性(處理器速度、內存、硬盤等)，又考慮網絡特性(帶寬、數據丟失率等)，雙方依據這些特性進行資源分配。一些基于QoS(Quality of Service)[7]的網格作業調度算法既可用于計算密集型作業，又可用于數據密集型作業，他們往往將作業的指令數量和輸入輸出文件的大小、資源的處理速度及網絡帶寬當作不同的屬性進行分配調度。

考慮作業的時間(Deadline)[8,9]限制，使計算密集型與數據密集型作業混合情況下的調度問題變得更加困難。本文詳細分析了計算密集型與數據密集型作業混合情況下的網格作業調度問題，通過對傳統的網格作業調度算法進行擴展，提出了三種調度算法：Emin-min、Ebest、Esufferage。并在Gridsim平臺上，與ASJS及Min-min算法進行了比較，分析了其各自的特點。選擇這兩個算法進行比較的原因是：Min-min算法在過去的驗證中顯示了比較好的性能，而ASJS算法適合于處理多種作業混合情況下的調用。

2 網格模型

我們采用的網格模型與文獻[5]的基本相同。假設用戶與路由器、Portal、Job Scheduler之間由高速網絡互連(如圖1所示)。圖1中p是數據密集型作業的比率，則計算密集型作業的比率為1-p。對于數據密集型作業，根據其文件大小又可分為大數據密集型作業(簡稱大作業)及小數據密集型作業(簡稱小作業)。q是大作業的比率，則小作業的比率為1-q。就全部作業而言，大作業的比率為pq，小作業比率為p(1-q)。為討論方便，做如下假設：

文件大小在[1 500 MB，3 000 MB]為大文件，其概率為q；

文件大小在[500 MB，1 500 MB]為小文件，其概率為1-q。

作業的文件大小是指輸入輸出文件大小之和。對于多個輸入輸出文件當作一個文件對待。

Figure 1 System model圖1 系統結構

作業的描述如下:jobi(ini,fsize,deadline,avi)。jobi.ini、jobi.fsize、jobi.deadline、jobi.avi分別指作業的指令數量、作業輸入輸出文件大小、作業的時間期限及作業到達時間。對于計算密集型作業，其輸入輸出的文件大小為0。資源描述如下:rj(proc,bw,avai)。rj.proc、rj.bw、rj.avai分別指資源的處理速度、網絡帶寬及空閑的時間點。假設所有資源都是空間共享(space-shared)型,即同一時間內，一個資源只能被分配一個作業。

jobi若分配給rj，其執行時間Ext(i,j)為：

(1)

rj的開始空閑時間為rj.avai，若jobi分配給rj，則jobi的完成時間c(i,j)為：

c(i,j)=Ext(i,j)+rj.avai

(2)

為確保作業在時間期限(deadline)前執行完成：

(3)

如果jud(jobi,rj)的值為1，則jobi可以在rj上按照deadline要求執行；否則,不能執行。

若系統真正將jobi分配給rj，則資源rj再次可接收作業的時間rj.avai為:

rj.avai=Ext(i,j)+rj.avai

(4)

rj.avai表示資源分配作業后，下次可接收作業的時間。實際上，由于準確估計作業的執行時間是比較困難的，在實際系統中，這個值以作業完成時間為準。

作業數量為jend，所有作業集合為：

(5)

資源數量為rend，所有資源集合為：

(6)

更一般地描述，假設每個作業有l個屬性(這里的屬性可以包括帶寬、內存、CPU速度等)，則J描述如下：

(7)

同樣，資源也具有l個屬性,資源描述如下：

(8)

RJ是一個l×l矩陣，若資源ri的所有屬性均滿足jobj的要求，則RJ(i,j)=1;若ri存在屬性不能滿足jobj的要求，則RJ(i,j)=0。jobj在ri上可以被執行的條件是：

(?temp)ri.atttemp>jobj.atttemp,1

(9)

根據公式(3)，令：

RJ(i,j)=jud(jobi,rj)

(10)

3 具有截止時間的作業調度算法

在網格中，作業調度問題是一個NP問題，一般借助啟發式算法解決。傳統的以最小作業完成時間為目標的批處理啟發算法包括Min-min、Max-min、Fast-fit、Best-fit、Sufferage等等。本節以Min-min、Best-fit、Sufferage算法為框架，提出了計算密集型作業和數據密集型作業混合情況下的三種啟發式算法，即Emin-min、Ebest、Esufferage。

在考慮到作業具有deadline的情況下，采用緊迫型作業優先調度原則，即如果能保證作業在deadline前完成的資源有限，那么立即調度這個作業。實際應用中，以可以按要求執行這個作業的資源比率rrat為準。如果小于這個比率，那么這個作業是緊迫型作業，立即執行。

3.1Emin-min

算法思想：首先根據公式 (1)和公式(2)，對每個作業計算在各個資源上的完成時間，取最小值的作業-資源對進行分配，更新被分配資源的下次可用時間Ext(i,j)，直至所有滿足條件的作業被完成。這里滿足條件是指先前能被執行的作業，有些作業因為有deadline要求，等待時間超過期限，導致不能被執行。

算法1Emin-min

輸入：資源集合R及作業集合J;

輸出：作業分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 計算 jud(jobi,rj)；

8.Ifjud(jobi,rj)==1

9. 計算Ext(i,j)；

10.If(minvalue> Ext(i,j))

11. selectr= rj;

12. selectj= jobi;

13. minvalue= Ext(i,j);

14.Endif

15.Endif

16.Endfor

17.Endfor

18. 將selectj分配給selectr；

19. 更新selectj.avai;

20. 對緊迫型作業進行調度；

21.While(所有適合要求的作業都被完成)

算法中，minvalue用于記錄最小的完成時間，selectr和selectj分別記錄最小完成時間時所選擇的資源和作業。第2～第4行是算法初始化，第5～第7行尋找執行時間最小的資源-作業配對，第18～第20行完成資源分配。

3.2 Ebest

為了得到一個更好的調度效果，使更多的作業能被執行，我們優先考慮時間期限緊迫的作業。jobi若分配給rj，其執行完成時間為c(i，j)，其與jobi.deadline的差距ts(i,j)反映了這個作業的緊迫程度。

ts(i,j)=jobi.deadline-c(i,j)

(11)

若ts(i，j)<0，則說明這樣分配不能保證作業在指定時間內完成，選擇其值為非負且最小的作業-資源進行映射。算法描述如下:

算法2Ebest

輸入：資源集合R及作業集合J;

輸出：作業分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 計算ts(i,j)；

8.If((minvalue> ts(i,j) &ts(i,j)>=0) )

4. selectr= rj;

5. selectj= jobi;

6. minvalue= ts(i,j);

7.Endif

8.Endfor

9.Endfor

10. 將selectj分配給selectr；

11. 更新selectj.avai;

12. 對緊迫型作業進行調度；

13.While(所有適合要求的作業都被完成)

這里可以將作業的deadline當作作業一個屬性處理，此作業在某個資源上的完成時間當作這個資源的一個屬性對待。第2～第4行是算法初始化，第5～第7行尋找使公式(11)取最小值的資源-作業配對，第15～第17行完成資源分配。

3.3 Esufferage

算法思想：分別計算每個作業的最小完成時間和次小完成時間，選擇兩者值相差最大的作業-資源進行配對。

算法3Esufferage

輸入：資源集合R及作業集合J;

輸出：作業分配方案。

1.Do

2. maxvalue=0;

3. selectr=-1;

4. selectj=-1;

5. first(i)記錄jobi最小完成時間；

6. second(i)記錄jobi次小完成時間；

7.Foreveryjobi∈J

8.Foreveryrj∈R

9. 計算c(i,j)；

10.Endfor

11.Endfor

12. 計算first(i),i∈{1,2,…,jend}；

13. 計算second(i),i∈{1,2,…,jend}；

14.Foreveryjobi∈J

15.If(maxvalue<(second(i)- first(i)) )

16. selectr= rj;

17. selectj= jobi;

18. maxvalue=max(second(i)-first(i));

19.Endif

20.Endfor

21. 將selectj 分配給selectr；

22. 更新selectj.avai;

23. 對緊迫型作業進行調度；

24.While(所有適合要求的作業都被完成)

maxvalue記錄最小完成時間與次小完成時間差的最大值。first(i)、second(i)分別記錄jobi最小完成時間及次小完成時間。第2～第4行是算法初始化，第5～第13行計算每個作業的最小完成時間和次小完成時間，第14～第20行尋找最小完成時間與次小完成時間的最大差值，第21～第23行進行資源分配并更新資源狀況。

4 仿真實驗

4.1 仿真環境

采用Gridsim[10]作為模擬器，Gridsim可以實現比較復雜的網格調度模擬。基于HaoY等人[8]先前的工作，對于Gridsim進行了關于時間期限的擴展。因此，采用Gridsim模擬數據密集型作業和計算密集型作業的混合調度。

作業數量為10 000，作業到達速率為20、22、24、26、28、30。數據密集型作業的比率(p)為0.30、0.50、0.70。大數據密集型作業比率(q)為0.30，0.50，0.70。作業需要傳輸的文件大小(jobi.ini)是[500，3 000](單位：百萬條指令)的一個整數，大數據密集型作業的文件大小(jobi.fsize)是[1 500MB,3 000MB]的一個隨機整數，小數據密集型作業的文件大小(jobi.fsize)是[500MB，1500MB]的一個隨機整數。系統有50個資源節點。資源帶寬(rj.bw)是[1.1，1.2，1.3，1.4，1.5]中的一個數值(單位Gs)，資源處理速度是[5，15]的一個隨機整數。作業的deadline是[1，5]的一個隨機整數。這些參數均服從均勻分布。模擬結果是10次模擬所得平均數。在實驗中采用緊迫型作業優先調度原則，令rrat=20%。ASJS對于資源的帶寬屬性和計算能力屬性分配不同的權重，根據ChangR-S[5]的模擬結果，其權重取值如表1所示。

Figure 2 Average makespan of different arrival rates圖2 不同到達率下的平均makespan AMJ

p計算能力權重帶寬權重0.30.30.70.50.50.50.70.70.3

在模擬實驗中，考察的參數包括：未完成的作業數量(UFJ)、平均等待時間(AWT)、平均makespan(AMJ)。makespan指從作業進入等待隊列開始到作業被執行的時間。

4.2 仿真結果與性能分析

圖2～圖4分別描述系統的UFJ、AWT、AMJ。總體上，AWT、AMJ都隨著作業到達速率、p、q的增加而增加，這是因為隨著到達速率、p、q的增加，系統負載也隨著增加，使作業的makespan及等待時間增大。當到達速率小于22時，各個算法的完成數量總體保持相同；當到達速率超過26后，各個算法未完成作業數量的增加速度明顯加快，這是因為系統趨于過載狀態，不能在有效時間內完成的作業越來越多。

AMJ(圖 2)與AWT(圖 3)具有相同的趨勢。總體上，平均等待時間與makespan隨著到達率的增加而增加。這是因為系統負載的增加延長了作業的等待時間和執行時間。這五種算法的AMJ及AWT值從大到小的順序是：Min-min、ASJS、Ebest、Emin-min、Esufferage。與Min-min相比、Ebest、Emin-min、Esufferage三種算法的執行時間分別減少了8.32%、15.51%、24.20%。

未完成作業的數量隨著p、q及到達率(ArrivalRate)的增加而增加。Min-min算法具有最大的未完成作業數量(如圖4所示)。與Min-min相比、Ebest、Emin-min、Esufferage三種算法的未完成作業數量分別減少了18.74%、22.18%、5.33%。這是因為Min-min沒有考慮到資源的特性及作業的deadline，所以表現較差。Eminmin、Ebest、ASJS算法的未完成的作業數量基本保持一致且均小于Min-min及Esufferage。

Esufferage以丟棄部分作業為代價獲得了最小的makespan和等待時間(圖2和圖3中，Esufferage的AMJ和AWT均保持最小值)。Ebest由于總是盡量推遲作業的執行時間，導致了作業的等待時間與makespan值最大，但同時也保證了系統完成的作業數量增加(圖2和圖3中，Ebest具有較大的AWT和AMJ。圖4中，Ebest具有較小的UFJ)。

Figure 3 Average waiting time of different arrival rates圖3 不同到達率下的平均等待時間AWT

Figure 4 Unfinished job number of different arrival rates圖4 不同到達率下的平均未完成作業數量UFJ

ASJS采用最高評分的方式選取資源，這在計算密集與數據密集型作業情況下選擇“最快”的策略基本相同。所以，Emin-min與ASJS在各個參數上均有近似的表現(如圖2～圖4所示)。 Emin-min與ASJS的平均等待時間AWT、平均執行時間AMJ、未完成作業的平均比值分別為：0.9645∶ 1，0.9828∶1，1.0155∶1。ASJS的評分雖然具有動態性，但并沒有考慮資源的特性，評分高的資源，并不能保證所有作業都適合執行。如果一個具有大的輸入輸出文件的作業被分配到一個帶寬小卻具有快速處理能力(資源評分高)的資源節點上，那么這個作業也不能在很短的時間內完成，導致了作業執行時間增加。采用緊迫型作業優先調度的Emin-min算法，則在各個方面均表現出色。

5 結束語

本文提出了Esufferage、Ebest及Emin-min算法，用于混合作業的調度，并在模擬網格上對三個算法進行驗證。仿真實驗表明，Esufferage以少完成部分作業為代價，減少了等待時間及makespan；Ebest雖然具有比較大的等待時間及makespan，但卻減少了未完成作業數量；Emin-min與ASJS相比，在保證完成作業的同時，減少了作業的平均等待時間和makespan。實驗顯示，這三種算法均優于傳統的Min-min算法。

本文在動態環境下，對計算密集型作業和數據密集型作業進行了分析,但缺少對QoS[9]的研究。由于不同的用戶對QoS有不同要求，對用戶的QoS偏好[12]選擇，也是一個需要進一步研究的課題。

[1] Maheswaran M,Ali S, Siegel H J, et al. Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop,1999:30-44.

[2] Braun T D,Siegel H J,Beck N,et al. A comparison study of static mapping heuristics for a class of metatasks on heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop, 1999:15-29.

[3] Venugopal S, Buyya R. An SCP-based heuristic approach for scheduling distributed data-intensive applications on global grids[J]. Journal of Parallel and Distributed Computing,2008, 68(4):471-487.

[4] Kolodziej J, Xhafa F,Barolli L, et al. A taxonomy of data scheduling in data grids and data centers:Problems and intelligent resolution techniques[C]∥Proc of 2011 International Conference on Emerging Intelligent Data and Web Technologies (EIDWT),2011:63-71.

[5] Chang Ruay-Shiung, Lin Chih-Yuan, Lin C F. An adaptive scoring job scheduling algorithm for grid computing[J]. Information Sciences,2012,207:79-89,DOI:10.1016/j.ins.2012.04.019.

[6] Valliyamma C,Somasundaram T S. A grid resource brokering strategy based on resource and network performance in grid[J]. Future Generation Computer Systems,2012, 28(3):491-499.

[7] Wang W, Luo J Z,Song A B. A GQoP guaranteed grid QoS adaptive scheduling algorithm[J]. Journal of Computer Research and Development, 2011,48(7):1168-1177.(in Chinese)

[8] Hao Yong-sheng,Liu Guan-feng,Wen Na. An enhanced load balancing mechanism based on deadline control on GridSim[J].Future Generation Computer Systems,2012.28(4):657-665,DOI:10.1016/j.future.2011.10.010.

[9] Li X, Hu Z G, Hu Z J, et al. Grid workflow scheduling algorithms based on deadline Satisfaction[J]. Journal of Computer Research and Development, 2011,48(5):877-884.(in Chinese)

[10] GridSim Toolkit 5.0,GridSim:A toolkit for modeling and simulating grid computing environments [EB/OL].[2013-05-01]. http://www.buyya.com/gridsim/.

[11] Albodour R, James A, Yaacob N. High level QoS-driven model for grid applications in a simulated environment[J]. Future Generation Computer Systems,2012, 28(7):1133-1144.

[12] Xiong Run-qun, Luo Jun-zhou, Song Ai-bo, et al. QoS preference-aware replica selection strategy in cloud computing[J]. Journal on Communications, 2011,32(7):93-102.(in Chinese)

附中文參考文獻:

[7] 王巍,羅軍舟,宋愛波.一種具有GQoP保證的網格QoS自適應調度算法[J].計算機研究與發展,2011,48(7):1168-1177.

[9] 李璽,胡志剛,胡周君,等.基于截止時間滿意度的網格工作流調度算法[J].計算機研究與發展,2011,48(5):877-884.

[12] 熊潤群,羅軍舟,宋愛波,等.云計算環境下QoS 偏好感知的副本選擇策略[J].通訊學報,2011,32(7):93-102.

HAOYong-sheng,born in 1980,MS,engineer,his research interest includes grid computing, and cloud computing.

盧俊文(1983-),男，福建廈門人，碩士，講師，研究方向為網格計算和云計算。E-mail:swordmenstory@163.com

LUJun-wen,born in 1983,MS,lecturer,his research interests include grid computing, and cloud computing.

劉冠峰(1983-),男，山東青島人，博士，副教授，研究方向為網格計算和云計算。E-mail:gfliu@suda.edu.cn

LIUGuan-feng,born in 1983,PhD,associate professor,his research interests include grid computing, and cloud computing.

Threegridjobschedulingmethodsheuristicsfordata-intensiveandcomputing-intensivejobs

HAO Yong-sheng1,LU Jun-wen2,LIU Guan-feng3,WEN Na4

(1.Network Center,Nanjing University of Information Science & Technology,Nanjing 210044；2.Xiamen University of Technology,Xiamen 361024;3.Soochow Advanced Data Analytics Lab,Soochow University,Suzhou 215006;4.College of Atmospherics Science,Nanjing University of Information Science & Technology,Nanjing 210044,China)

Most of the existing grid job scheduling methods focus on either data-intensive jobs or computing-intensive jobs.In the dynamic environment where every job has its deadline,we extend the traditional grid job scheduling methods to propose three new grid job scheduling methods:Emin-min,Ebest and Esufferage.The three methods are validated on the Grid model with clusters that are connected by the high speed network.Simulation results demonstrate that our proposed methods are better than Min-min.The comparison between the three methods and ASJS shows that,Emin-min reduces the waiting time and makespan,Esufferage reduces the waiting time and the makespan greatly with the sacrifice of some jobs,and Ebest gives the same performance in unfinished jobs but has a larger value in waiting time and makespan than ASJS. In general,Eminmin has a better performance than Min-min and ASJS.

computing-intensive;data-intensive;job scheduling;average makespan

1007-130X(2014)08-1423-07

2013-03-20;

：2013-05-20

福建省教育廳科技項目B類(JB09199)；國家自然科學基金資助項目(41005048)；科技部資助項目(GYHY201106037，GYHY200906023)

TP391.9

：A

10.3969/j.issn.1007-130X.2014.08.001

郝永生(1980-),男，安徽懷寧人，碩士，工程師，研究方向為網格計算和云計算。E-mail:hyslove@163.com

通信地址：210044 江蘇省南京市南京信息工程大學網絡信息中心

Address:Network Center,Nanjing University of Information Science & Technology,Nanjing 210044,Jiangsu,P.R.China