基于資源結點性能預測的啟發式調度算法研究

魏妮妮，宋 翌

（武漢生物工程學院 計算機與信息工程系，湖北 武漢 430415）

由于網格系統中的資源本身具有的動態性、分布性、異構性以及自治管理的特點，使得資源分配和任務調度問題一直是各界研究的核心。任務調度是個復雜問題，雖然已有深入和持久的研究，還是沒有得到很好的解決。有學者提出了一些調度算法，這些算法往往是基于假設條件下提出的，比如在文獻[1-4]中的調度模型是在假設任務得到處理機獨享、通信沒有費用、網絡容量無限和獨占網絡帶寬等條件提出的，這些算法用在現實網格系統中往往是不實際的，不但不能體現網格系統的優越性，甚至會導致網格系統的性能急劇下降。另外，任務調度問題也已經被證明是NP難題[5－6]，往往采用啟發式算法，或是啟發式算法的各種組合。在文獻[4-7]中對一些經典的啟發式任務調度算法進行了性能模擬試驗，證明這些啟發式算法花費的代價相對較小，但是這些已有的經典啟發式調度算法，比如 OLB、Min-Min、Max-Min、MCT、SA算法和遺傳算法等，往往是沒有考慮資源結點性能度量，雖然在某些領域得到較好的應用，但也有一定的缺陷存在，特別是對于大吞吐量任務調度應用效果不佳。同時上述調度算法在制定時忽略了網格中各個資源結點的性能度量，然而任務調度策略制定的重要依據就是資源結點的性能度量。為此，本文針對高吞吐量應用問題提出了一種新的任務調度。

1 網格資源結點性能預測模型

在制定任務調度策略時考慮資源的性能預測，并建立精準的性能預測模型，這在網格復雜的多任務并行處理環境中是非常重要的。通過對網格計算任務調度問題的深入分析，對在文獻[8-9]中提出過的考慮資源結點負載的任務完成時間的性能預測模型結構的基礎上進行改進，引入了資源帶寬監測和任務信息接收2個模塊。應用此模型可以預測出資源結點的任務完成時間，也可以監測結點負載情況，使用該模型進行任務調度不僅可以兼顧任務長短和結點負載平衡，而且用戶可以改變抽樣率、所需的資源性能參數、帶寬監測模式、調度策略等，用戶只需提交應用任務的相關描述信息和設置一些參數即可。

該模型的系統結構由8個模塊組成：用戶控制子模塊、測量子模塊、任務信息接收子模塊、結點負載預測子模塊、結點網絡帶寬監測子模塊、應用子模塊、實時預測子模塊和調度子模塊。任務完成時間的預測系統結構如圖1所示。

圖1 任務完成時間預測系統結構

用戶控制子模塊用以實現其他子模塊和用戶之間的信息交互。用戶可以改變抽樣率、所需的資源性能參數、帶寬監測模式、調度策略等，這些操作主要通過一種異步的請求／響應機制實現。測量子模塊用以實現對各個資源結點當前負載情況的測量和周期取樣，并把測量得到的量值存入到指定文件中。任務信息接收子模塊用以接收用戶提交應用任務的相關描述信息，比如任務完成的時間要求、任務需求的特殊資源等，并把接收的任務信息發送給調度子模塊。結點負載預測子模塊用以根據接收到的測量子模塊發送的測量值，預計下一時間段資源結點潛在的負載情況。結點網絡帶寬監測子模塊用以實現對各個資源結點帶寬使用情況進行周期性監測，并把監測值存入到指定文件中、發送給實時預測子模塊。應用子模塊用以把一些結點和應用的性能參數傳送給實時預測子模塊。實時預測子模塊根據網絡帶寬監測子模塊傳送的網絡帶寬和結點負載預測子模塊發送的結點負載情況、應用模塊傳送的資源結點的性能參數等來預測任務的完成時間。調度子模塊根據實時預測模塊得到的預測值和可用候選資源結點及任務信息接收模塊傳送的信息制定調度策略，以實現任務與資源結點的最佳匹配執行。

在完成時間預測模型的基礎上，得到任務執行時間的預測公式：

其中用load（t）表示在t時刻資源結點的負載，tunload表示任務在資源結點完全沒有負載情況下的執行時間，它可體現出任務對當前資源結點的CPU的需求，texe表示任務的執行時間。

如果給出tunload，測量子模塊通過周期采樣資源結點的負載，并把測量結果傳送給結點負載預測子模塊，就可計算資源結點在t時刻可能具有的負載load（t），實時預測子模塊根據結點負載預測子模塊傳送的數據，就可預測該任務的執行時間texe。

帶寬監測子模塊通過定期地發送一些數據包給資源結點，當某個資源結點接收到數據包后，不進行計算而是直接把接收到的數據包反傳給資源結點的帶寬監測模塊，這樣監測模塊可以根據傳送數據包來回的時延計算當前時刻結點所具有的網絡帶寬。

通過上述分析可知，使用任務完成時間預測模塊中的實時預測子模塊可以計算出各個任務在不同資源結點上的預測完成時間。本文提出的算法即是以此為依據來實施任務調度。

2 資源結點性能度量任務調度算法——BNPP算法

對于相同的資源和任務，在理想狀態下，當把任意一個任務gi分配到一個可用資源結點pj上執行時，任務gi是獨占結點pj的CPU處理能力和網絡帶寬的，網格資源發現服務的資源屬性表中提供了相應結點的網絡帶寬和CPU處理能力。這種條件下可求出任務的總的執行時間，即任務到達資源結點時間＋任務在資源結點上執行時間。任務總的執行時間為

其中：βij表示任務總的執行時間；Aij表示任務gi到達pj的時間，Aij＝gi的任務量／pj的網絡帶寬；Rij表示任務gi在pj上的執行時間，Rij＝gi的任務量／pj的CPU處理能力。

求出實際網格計算系統中1次任務調度的總的完成時間為

其中，cij表示任務gi分配給結點pj處理任務總的完成時間，aij表示實際的到達時間，rij表示任務的預測完成時間。

通過任務完成時間預測模型中的帶寬監測子模塊可得到aij的值，rij的值也可通過性能預測求得。可以定義1次任務調度完成時間為 maxt∈｛t1，t…，tn｝icij。顯然完成1次任務調度的時間越少，系統的性能就越好。

資源結點的性能是以處理所有任務的完成時間的平均值來進行度量的，對于資源集P中的任意一個資源結點pj處理任務集G中的所有任務總的平均執行時間為。avej的大小可以表示出資源結點處理能力的強弱。假設有2結點p1和p2，如果ave1＜ave2，則說明p2結點空閑時間比p1少，即資源結點p1的性能低于資源結點p2。

定義wj表示資源結點pj的性能的權值，則wj為pj處理任務集G中的所有任務總的平均執行時間除以資源集P中每個結點處理任務集G中的所有任務總的平均執行時間之和，用公式即可表示為：

坡向對于太陽的光照、住宅的采光度有著重要的影響。客家人對住宅選址、布局、門的朝向上講究“風水”，坡向(圖4b)也是影響客家人的建筑分布的一個因子。對DEM數據進行坡度提取得到梅縣區內地形的坡度數據(圖4c)。使用ArcGIS的分類功能，按照城市建設劃分標準中劃分為地平地、平地、平坡地、緩坡地、中坡地、陡坡地6種類型分別占總面積的0.21%、5.48%、14.22%、23.58%、48.03%、8.48%，平均坡度為12.5°，坡度標準差為8.23°。

其中，k表示資源結點的個數，且k≥1的正整數。

通過此式可求出資源集中的任意一個結點的性能的權值，資源集中所有資源結點的性能的權值之和為1。顯然結點的性能的權值越小，說明它完成任務所用的時間越小，則表明結點的性能就越好。

下面定義判斷任務完成的難易度。任務gi在資源集中所有結點上總的執行時間加權平均值用di表示，則。對于任意的2個任務g1和g2，如果d1＞d2，意味著相同的資源結點處理g1所花費的時間長于g2，表明任務g1相比于任務g2更難完成。通過上述計算和分析，就以任務完成的難易程度來進行排序，di的值越大表明其越難完成，在進行調度時與使它具有最快完成時間的資源進行匹配實施調度。

給出基于資源結點性能度量最難完成的任務分配給執行時間最短的結點算法的具體描述如下：

設網格計算系統中有n相互獨立的任務形成的集合G＝｛g1，g2，...，gn｝，m 個可用資源形成的集合P＝｛p1，p2，...，pm｝。di表示任務gi在所有結點上總的執行時間加權平均值，avej表示資源結點pj處理任務集G中的所有任務總平均執行時間。則算法調度實施簡要步驟描述如下：

（1）利用任務完成時間預測模型，計算任務集里的各個任務在可用資源集中各個資源結點上的預測完成時間；

（3）計算任務集中所有任務的難易指標di；

（4）找出具有最大di的任務及使它具有最小執行時間的對應結點，得出此時的任務最小預測完成時間；

（5）調度最難完成任務到性能最好的結點上；

（6）從任務集中刪除執行完任務，重復此過程直到完畢；

（7）更新任務集和資源信息；

（8）轉到（4）重復執行，直到任務集中所有任務完成。

3 仿真實驗與性能分析

針對BNPP算法，使用SimGrid進行仿真。創建1個中心結點，創建10個用戶結點作為計算資源，任意給出20個相互獨立的任務，任務采用文獻中使用的方式，即泊松分布進行提交。在實驗中規定任務的計算長度介于1000MI到100000MI之間。針對于相同的任務在仿真平臺上分別調用min-min、max-min、Sufferage和BNPP 4種調度算法在任務完成總的時間和系統資源利用率方面進行比較。仿真結果見表1和圖2。

表1 4種算法資源結點執行任務所花時間

圖2 4種算法任務總的完成時間對比

從圖2及表1中可得到分別應用上述4種啟發式算法調度總的任務完成時間：min-min算法為5.3s，max-min算法為4.5s，Sufferage算法為4.1s，BNPP算法為4.0s。因此，min-min算法、max-min算法和Sufferage算法的總的任務完成時間都大于本文的BNPP算法。min-min算法將具有最短完成時間的任務分配給最早完成此任務的結點，這就導致完成時間較長的任務被分配給負載重的結點去完成。本文提出的算法中大部分結點的任務完成時間要小于max-min算法，且各個資源結點隨時間變化比較平穩。

在資源結點數量性能不變的前提下，現將上面的仿真條件進行如下改變：將提交的相互獨立的任務的數量增加到1000個（高吞吐量應用），定義調度周期為6s，其他約束不變，4種算法進行任務調度資源利用率Y的對比見圖3。

圖3 網格系統資源利用率對比

圖3中，用任務完成率來進行資源結點的性能比較，Y軸的值為各個資源結點任務完成率的最大值與最小值之差。差值小說明資源結點利用率高，差值大說明資源結點的利用率低，可以既簡便又準確地表示出資源結點性能好壞。由圖3可以看出，本文提出的BNPP算法從系統資源利用率方面也優于其他3種算法。

4 結論

文中的BNPP調度算法在綜合考慮了網格系統自身特點、構成網格系統資源的動態特點，以及任務的某些要求下而設計的。通過仿真實驗并和以往應用較多的經典啟發式調度算法min-min、max-min及Sufferage進行比較，結果證明BNPP算法在任務總的完成時間和系統資源利用率方面都優于上述3種方法，BNPP算法既減少了任務總的完成時間，又平衡了資源結點的負載、提高了資源利用率，所以BNPP算法非常適合解決高吞吐率應用問題的任務調度。

（References）

[1]金海，袁平鵬，石柯譯.網格計算[M].北京：電子工業出版社，2004.

[2]Casanova H.Network Modeling Issues for Grid Application Scheduling[J].The International Journal of Foundations of Computer Science，2005，6（2）：145-162.

[3]丁敏敏.網格計算中改進 Min-Min算法的研究[D].西安：西北大學，2010：16-21.

[4]Li Lingjuan，Shi Xiangning，Wang Ruchuan.An Improved Ant Algorithm-Based Task Scheduling Strategy in Grid[J].Journal of Nan Jing Unicersity of Posts and Elecommunications：Natural Science，2008，28（3）：18-20.

[5]Yin Fei，Jiang Changjun，Deng Rong，et al.Gird resource management policies for load＿balanceing and energy＿saving by vacatior queuing theoy[J].Computer and Electrical Engineering，2009（35）：966-976.

[6]羅紅，慕德俊，鄧智群.網格計算中作業調度研究綜述[J].計算機應用研究，2005，22（5）：16-19.

[7]彭云海，李騫，李強.網格環境下資源負載均衡和優化調度研究[J].計算機工程與應用，2009（19）：104-106.

[8]吳成茂.基于免疫原理的網格任務調度算法 [J].計算機工程，2011（1）：164-166.

[9]唐闊.網格計算資源與任務的實時監測預報系統[D].長春：吉林大學，2010：32-37.