基于分段思想的改進的Min-Min網格調度算法

摘要：以傳統、經典的Min-min調度算法為基礎，提出了一種基于“分段”思想的改進策略，并且采用HypelSim網格模擬器對算法進行了仿真。改進的算法較好地解決了傳統Min-Min算法存在的負載不平衡的問題。仿真結果表明，改進的算法合理，具有較高的性能。

關鍵詞：調度Min-Min Divided-Min-Min模擬HyperSim

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

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

以完成時間為優化目標的任務一資源映射是一個NP完全問題，所以需要輔助的啟發式算法。對于傳統的Min-Min、Max-Min、A*和GA等靜態啟發式算法，TracyD.Braun等人已經做了詳細的研究。結果表明，GA算法在不同ETC矩陣下的性能是最好的，Min-Min和A*次之。并且Tracy D.Braun的研究表明：對于每個ETC矩陣，CA算法的平均執行時間是60秒，而A*算法是20分鐘。由于算法中各項參數是通過NWS等服務得到的一些提前預測值，因此在參數隨時問劇烈變化的網格環境下，GA或A*的計算時間會顯得很長，因而得到的調度策略也很不合理。

Min-Min算法仍然是目前網格調度算法的研究基礎之一。該算法的主要思想是：當需要調度的任務集合非空時，反復執行如下操作直至集合為空：

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

(2)設第k個元素是MinTime數組中最小的，其對應的主機為b，把任務k分配到機器b上；

(3)在任務集合中把任務k刪除。
由于btin-Min算法總是優先調度短任務，當機器空閑時一些執行時間較長的任務才能得以執行，這樣便導致了主機負載不均衡，利用率降低。對此，本文提出一個改進的算法來優先調度執行時間長的任務，即分段Min-Min算法Dmm(Divided-Min-Min)。

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

(1)計算每一個任務的排序值keyi。在阿格異構環境下，同一任務在不同機器上的執行時間是不同的，這被稱為網格的任務異構。考慮到任務異構性，在確定排序值時測試了三種子策略——平均、最小、最大預期執行時間。

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

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

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

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

與Min-Min算法不同的是，Dmm算法在調度執行之前先進行任務排序，這意味著執行時間長的任務較早被調度。然后在每個任務段內局部運用Min-Min算法。該算法的關鍵就是如何確定任務的排序值，確保長任務能夠優先調度。

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

3 仿真實驗及結果分析
這里使用HyperSim模擬器對改進的算法進行仿真研究。HyperSim實際上是一個基于C++開發的通用離散事件模擬庫，提供了一系列庫函數，用以建立特定計算環境或專業應用領域的模擬器。HyperSim提供了豐富的類，諸如事件發生器、統計分析器、自動軌跡仿真器、事件操縱器等來構造仿真環境。它遵循事件圖模型，這種模型可以優化模擬速度、提高可擴展性。相對其他模擬器而言，HyperSim最大的優點就是運行速度快，可以用來模擬大規模的網格環境。此外，它還具有通用性，可擴展性和易配置等特點。

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

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

實驗結果證明Dmm算法的執行時間比Min-Min算法短，因為Min-Min需要在整個ETC矩陣中尋找具有最短執行時問的任務，而Dmm算法采用分段的方法，只需在每段內搜索具有最小完成時間的任務。這種分段的方法不僅降低了makespan，而且縮短了運行時間。

本文對目前最常用的Min-Min算法進行了深入的分析，在此基礎上提出了性能更優越、負載平衡性更好的Dmm算法。利用HyperSim模擬器對Dmm算法進行了仿真驗證。仿真結果表明Dmm算法相對于Min-Min算法有很多的優勢。由于Min-Min算法是網格調度中非常基礎的算法，因此改進后的算法將對現有的調度算法有很大的幫助，尤其對那些建立在Min-Min基礎上的調度算法，可以進一步提高該類算法的效率。