基于分段思想的改進(jìn)的Min-Min網(wǎng)格調(diào)度算法

基于分段思想的改進(jìn)的Min-Min網(wǎng)格調(diào)度算法

摘要：以傳統(tǒng)、經(jīng)典的Min-min調(diào)度算法為基礎(chǔ)，提出了一種基于“分段”思想的改進(jìn)策略，并且采用HypelSim網(wǎng)格模擬器對(duì)算法進(jìn)行了仿真。改進(jìn)的算法較好地解決了傳統(tǒng)Min-Min算法存在的負(fù)載不平衡的問題。仿真結(jié)果表明，改進(jìn)的算法合理，具有較高的性能。

關(guān)鍵詞：調(diào)度Min-Min Divided-Min-Min模擬HyperSim

網(wǎng)格(Grid)技術(shù)是當(dāng)今計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)之一。在網(wǎng)格技術(shù)飛速發(fā)展的同時(shí)，網(wǎng)格計(jì)算中的任務(wù)調(diào)度問題也變得越來越重要。網(wǎng)格環(huán)境中各處理器的運(yùn)行速度、主機(jī)的負(fù)載、網(wǎng)絡(luò)通信的時(shí)間等都是動(dòng)態(tài)變化的，資源的管理和調(diào)度十分復(fù)雜，多機(jī)環(huán)境下的任務(wù)調(diào)度問題便成為一個(gè)眾所周知的NP問題。目前，圍繞著網(wǎng)格計(jì)算中的任務(wù)調(diào)度算法，國內(nèi)外已經(jīng)做了大量的研究工作，先后提出了各種靜態(tài)和動(dòng)態(tài)的調(diào)度算法。本文對(duì)傳統(tǒng)的、經(jīng)典的Min-Min調(diào)度算法進(jìn)行深入的分析和研究，指出該算法存在的缺陷，并在此基礎(chǔ)上提出一個(gè)基于“分段”思想的改進(jìn)算法，并且在網(wǎng)格模擬器環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果驗(yàn)證了改進(jìn)后算法的合理性和有效性。

1 Min-Min算法概述
在網(wǎng)格環(huán)境下，高效的調(diào)度策略或算法可以充分利用網(wǎng)格系統(tǒng)的處理能力，從而提高應(yīng)用程序的性能。任務(wù)調(diào)度同題的實(shí)質(zhì)就是在一個(gè)由m個(gè)需要調(diào)度的任務(wù)和n個(gè)可用的任務(wù)執(zhí)行單元(主機(jī)或集群)構(gòu)成的網(wǎng)格環(huán)境下，把m個(gè)任務(wù)T={t1,t2,……tm]以合理的方式調(diào)度到n個(gè)主機(jī)H={h1,h2,……h(huán)n}上去，目的是得到盡可能小的總執(zhí)行時(shí)間(Makespan)。m個(gè)任務(wù)在n個(gè)不同機(jī)器上的預(yù)測(cè)執(zhí)行時(shí)間ETC(Expected Time to Compute)是一個(gè)m×n的矩陣。ETC(i，j)表示第i個(gè)任務(wù)在第j臺(tái)機(jī)器上的預(yù)測(cè)執(zhí)行時(shí)間，矩陣中的每一行代表某一任務(wù)在n臺(tái)機(jī)器上的不同執(zhí)行時(shí)間，每一列代表在同一臺(tái)機(jī)器上m個(gè)任務(wù)的不同執(zhí)行時(shí)間。

以完成時(shí)間為優(yōu)化目標(biāo)的任務(wù)一資源映射是一個(gè)NP完全問題，所以需要輔助的啟發(fā)式算法。對(duì)于傳統(tǒng)的Min-Min、Max-Min、A*和GA等靜態(tài)啟發(fā)式算法，TracyD.Braun等人已經(jīng)做了詳細(xì)的研究。結(jié)果表明，GA算法在不同ETC矩陣下的性能是最好的，Min-Min和A*次之。并且Tracy D.Braun的研究表明：對(duì)于每個(gè)ETC矩陣，CA算法的平均執(zhí)行時(shí)間是60秒，而A*算法是20分鐘。由于算法中各項(xiàng)參數(shù)是通過NWS等服務(wù)得到的一些提前預(yù)測(cè)值，因此在參數(shù)隨時(shí)問劇烈變化的網(wǎng)格環(huán)境下，GA或A*的計(jì)算時(shí)間會(huì)顯得很長，因而得到的調(diào)度策略也很不合理。

Min-Min算法仍然是目前網(wǎng)格調(diào)度算法的研究基礎(chǔ)之一。該算法的主要思想是：當(dāng)需要調(diào)度的任務(wù)集合非空時(shí)，反復(fù)執(zhí)行如下操作直至集合為空：

(1)對(duì)集合中每一個(gè)等待分配的任務(wù)ti，分別計(jì)算出把該任務(wù)分配到n臺(tái)機(jī)器上的最小完成時(shí)間，記為MinTime(i)，可以得到一個(gè)含有m個(gè)元素的一維數(shù)組MinTime；

(2)設(shè)第k個(gè)元素是MinTime數(shù)組中最小的，其對(duì)應(yīng)的主機(jī)為b，把任務(wù)k分配到機(jī)器b上；

(3)在任務(wù)集合中把任務(wù)k刪除。
由于btin-Min算法總是優(yōu)先調(diào)度短任務(wù)，當(dāng)機(jī)器空閑時(shí)一些執(zhí)行時(shí)間較長的任務(wù)才能得以執(zhí)行，這樣便導(dǎo)致了主機(jī)負(fù)載不均衡，利用率降低。對(duì)此，本文提出一個(gè)改進(jìn)的算法來優(yōu)先調(diào)度執(zhí)行時(shí)間長的任務(wù)，即分段Min-Min算法Dmm(Divided-Min-Min)。

2 基于分段思想改進(jìn)的Min-Min算法
Dmm算法首先根據(jù)任務(wù)的ETC進(jìn)行排序，即根據(jù)平均ETC或最小眥或最大ETC將任務(wù)歸為一個(gè)從大到小的有序序列；然后將這個(gè)任務(wù)序列分成相同大小的段，先調(diào)度長任務(wù)段，后調(diào)度短任務(wù)段。對(duì)于每個(gè)任務(wù)段，仍然使用Min-Min算法進(jìn)行任務(wù)調(diào)度。Dram算法描述如下：

(1)計(jì)算每一個(gè)任務(wù)的排序值keyi。在阿格異構(gòu)環(huán)境下，同一任務(wù)在不同機(jī)器上的執(zhí)行時(shí)間是不同的，這被稱為網(wǎng)格的任務(wù)異構(gòu)?？紤]到任務(wù)異構(gòu)性，在確定排序值時(shí)測(cè)試了三種子策略——平均、最小、最大預(yù)期執(zhí)行時(shí)間。

子策略l：Dmm-avg計(jì)算ETC矩陣中每一行的平均值：

子策略2：Dmm-min計(jì)算ETC矩陣中每一行的最小值：

子策略3：Dram-max計(jì)算ETC矩陣中每一行的最大值：

(2)根據(jù)排序值，降序排列任務(wù)集合，形成一個(gè)有序序列。
(3)將任務(wù)序列平均分為N段。
(4)運(yùn)用Min—Min算法依次調(diào)度各任務(wù)段。

與Min-Min算法不同的是，Dmm算法在調(diào)度執(zhí)行之前先進(jìn)行任務(wù)排序，這意味著執(zhí)行時(shí)間長的任務(wù)較早被調(diào)度。然后在每個(gè)任務(wù)段內(nèi)局部運(yùn)用Min-Min算法。該算法的關(guān)鍵就是如何確定任務(wù)的排序值，確保長任務(wù)能夠優(yōu)先調(diào)度。

Dmm算法的第三步是將任務(wù)序列分為N段，重點(diǎn)在于如何選擇最優(yōu)的N值。一方面,N值越大負(fù)載越趨于均衡；另一方面，N值過大會(huì)使Min-Min算法降低效率。圖1中的曲線表明，在選取不同的N值時(shí)，采用Dmmavg子策略的Dmm算法相對(duì)Min-Min算法的改進(jìn)度。如圖1所示。當(dāng)c=m/n的值較小時(shí)，也就是平均分配到每臺(tái)機(jī)器上的任務(wù)數(shù)量較少時(shí)，Dmm算法就表現(xiàn)出良好的性能。無論c取值多大，圖l中的曲線總是在_N值為4或5時(shí)達(dá)到最高的算法改進(jìn)度。因此，將N的值定為4，在任務(wù)序列劃分時(shí)通常都分為4段。

3 仿真實(shí)驗(yàn)及結(jié)果分析
這里使用HyperSim模擬器對(duì)改進(jìn)的算法進(jìn)行仿真研究。HyperSim實(shí)際上是一個(gè)基于C++開發(fā)的通用離散事件模擬庫，提供了一系列庫函數(shù)，用以建立特定計(jì)算環(huán)境或?qū)I(yè)應(yīng)用領(lǐng)域的模擬器。HyperSim提供了豐富的類，諸如事件發(fā)生器、統(tǒng)計(jì)分析器、自動(dòng)軌跡仿真器、事件操縱器等來構(gòu)造仿真環(huán)境。它遵循事件圖模型，這種模型可以優(yōu)化模擬速度、提高可擴(kuò)展性。相對(duì)其他模擬器而言，HyperSim最大的優(yōu)點(diǎn)就是運(yùn)行速度快，可以用來模擬大規(guī)模的網(wǎng)格環(huán)境。此外，它還具有通用性，可擴(kuò)展性和易配置等特點(diǎn)。

HyperSim提供了一系列的庫函數(shù)，可以方便地隨機(jī)生成不同的主機(jī)處理能力、網(wǎng)絡(luò)帶寬、通信延遲等參數(shù)。本文設(shè)計(jì)了一個(gè)模擬程序，以檢驗(yàn)改進(jìn)后的算法性能。?、糁禐?，計(jì)算資源數(shù)量為10，并且每個(gè)任務(wù)的預(yù)測(cè)執(zhí)行時(shí)間給定。圖2是網(wǎng)格任務(wù)中包含不同的任務(wù)數(shù)量時(shí)，調(diào)度到lO臺(tái)處理機(jī)的模擬結(jié)果。圖中每個(gè)點(diǎn)表示的是均取5次模擬結(jié)果的平均值。從圖中可以看出，Dram算法的三個(gè)子策略性能均優(yōu)于Min-Min算法；Dmm-min的性能在有些情況下優(yōu)于Dmm-avg，但多數(shù)情況下不如Dmm-avg；而Dmm-max的性能總是低于Dmm-avg。因此，采用Dmm-avg子策略作為Dmm算法。模擬結(jié)果表明，Dmm-avg算法的性能比Min-Min算法提高了4.2％-6.1％。

圖3給出了四種算法的負(fù)載均衡性比較。其中，Min-Min算法中每個(gè)處理機(jī)的負(fù)載極不平衡，主要原因在于Min-Min算法將執(zhí)行時(shí)問最短的任務(wù)分配在負(fù)載最小的機(jī)器上，這導(dǎo)致執(zhí)行時(shí)間長的任務(wù)分配到負(fù)載較大的機(jī)器上。Dram算法的負(fù)載均衡性均高于Min-Min算法。其中，Dmm-avg的曲線最平滑，說明該算法的負(fù)載均衡性最高。

實(shí)驗(yàn)結(jié)果證明Dmm算法的執(zhí)行時(shí)間比Min-Min算法短，因?yàn)镸in-Min需要在整個(gè)ETC矩陣中尋找具有最短執(zhí)行時(shí)問的任務(wù)，而Dmm算法采用分段的方法，只需在每段內(nèi)搜索具有最小完成時(shí)間的任務(wù)。這種分段的方法不僅降低了makespan，而且縮短了運(yùn)行時(shí)間。

本文對(duì)目前最常用的Min-Min算法進(jìn)行了深入的分析，在此基礎(chǔ)上提出了性能更優(yōu)越、負(fù)載平衡性更好的Dmm算法。利用HyperSim模擬器對(duì)Dmm算法進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明Dmm算法相對(duì)于Min-Min算法有很多的優(yōu)勢(shì)。由于Min-Min算法是網(wǎng)格調(diào)度中非常基礎(chǔ)的算法，因此改進(jìn)后的算法將對(duì)現(xiàn)有的調(diào)度算法有很大的幫助，尤其對(duì)那些建立在Min-Min基礎(chǔ)上的調(diào)度算法，可以進(jìn)一步提高該類算法的效率。