基于主機負載預(yù)測的動態(tài)任務(wù)調(diào)度算法研究

摘要:提出一種基于遺傳神經(jīng)網(wǎng)絡(luò)的主機負載預(yù)測模型，并基于該模型設(shè)計了集中式任務(wù)調(diào)度算法CJD-HLP。CJD-HLP采用預(yù)測法提前獲得主機負載信息，保證了任務(wù)調(diào)度時使用決策信息的實時性、準確性，避免了負載遷移的抖動問題。實驗結(jié)果表明，該算法較基于實測法的其他任務(wù)調(diào)度算法在性能上有較大提高。

關(guān)鍵詞:負載預(yù)測;動態(tài)任務(wù)調(diào)度;網(wǎng)絡(luò)并行計算;PVM

中圖分類號:TP301.6文獻標識碼:A 文章編號:1009-3044(2010)02-388-03

Research on Dynamic Task Scheduling Algorithm Based on Host Load Prediction

XIE Fang-qing， TAN Yi

(Zhongkai University of Agriculture and Engineering， Guangzhou 510225， China)

Abstract: A host load prediction model based on heredity-neural network is proposed， and center task scheduling algorithm CJD-HLP based on the model is designed. CJD-HLP algorithm adopts prediction method to get the host load information earlier， ensure that the information for decision-making is real-time and accurate and avoid the load transfer jitter problem. Experimental results demonstrate that the algorithm performance is greatly enhanced compared with the algorithm based on actual measurement.

Key words: load prediction; dynamic task scheduling; network parallel computing; PVM

1 概述

網(wǎng)絡(luò)并行計算由于可以利用網(wǎng)絡(luò)中空閑資源進行計算而得到廣泛研究，然而經(jīng)常會出現(xiàn)某些處理機負載過重而另外一些處理機很輕甚至空閑的情況，即負載不均衡現(xiàn)象。負載的不均衡大大降低了整個系統(tǒng)的資源利用率，直接影響到并行計算的性能。而實現(xiàn)負載均衡的關(guān)鍵是設(shè)計好的任務(wù)調(diào)度算法。PVM本身只提供了靜態(tài)任務(wù)調(diào)度方法[1]，即在進行任務(wù)分配時采用二次均分法，該方法不考慮處理機負載情況，將待分配任務(wù)平均分配到各個結(jié)點上，并且在運行時負載不能重新分配;而在目前提出的動態(tài)任務(wù)調(diào)度方法中，大都采用實測法收集結(jié)點負載的實時值作為任務(wù)調(diào)度的依據(jù)，但實測法存在以下幾個缺點[2]:

1)實測法系統(tǒng)開銷大。需要直接或間接利用系統(tǒng)調(diào)用來測量負載，系統(tǒng)調(diào)用需要從用戶態(tài)到核心態(tài)的切換，時間開銷很大，極大地影響了系統(tǒng)效率。

2)實測法存在信息過時問題。負載信息從開始收集到傳遞給調(diào)度結(jié)點存在傳遞時延，調(diào)度結(jié)點依據(jù)負載信息進行調(diào)度決定又存在決策時延，過多的時延使收集的實時負載信息與調(diào)度后的負載狀況有較大的差異，從而造成依據(jù)實時負載信息作出的調(diào)度決定不能實現(xiàn)有效的負載平衡。

3)實測法存在收集代價問題。指任務(wù)調(diào)度方法帶來的性能上的提高與信息收集帶來的系統(tǒng)消耗之間的比較關(guān)系，如果信息收集的系統(tǒng)消耗太大，將抵消動態(tài)任務(wù)調(diào)度帶來的性能上的提高。

因此，如果能夠采用快速高效的預(yù)測算法，預(yù)先獲得結(jié)點的負載信息，則在進行動態(tài)任務(wù)調(diào)度時就會有提前量，就可以避免因各種時延使決策信息過時而引起進程遷移的抖動，從而使整個系統(tǒng)的負載均衡性能得到較大提高。本文基于Windows XP+WPVM平臺組成的機群系統(tǒng)，采用遺傳神經(jīng)網(wǎng)絡(luò)預(yù)測主機結(jié)點的負載，并基于負載預(yù)測提出CJD-HLP算法實現(xiàn)任務(wù)的動態(tài)調(diào)度，有效提高了網(wǎng)絡(luò)并行計算的性能。

2 負載的選擇

負載指標被負載平衡機制用于決定任務(wù)放置的位置，目前對結(jié)點機負載指標的評價還沒有統(tǒng)一適用的標準。一般常用的負載指標包括CPU處理能力，CPU利用率，運行隊列中的進程數(shù)，磁盤及內(nèi)存可用空間，I/0利用率，進程響應(yīng)時間等。考慮到通常的實驗環(huán)境是在同一個實驗室的局域網(wǎng)內(nèi)，各機器一般都是由實驗室統(tǒng)一購買，機器之間的性能差別很小，故CUP和內(nèi)存等負載指標的影響處于次要地位。同時，為了降低收集系統(tǒng)負載的開銷，避免各負載指標因量綱和單位不同難以統(tǒng)一標準化的問題，本文采用單一指標法進行負載定義，即將運行隊列中的進程數(shù)作為負載指標。

3 主機負載預(yù)測模型

主機負載由于受到多種因素的影響，對主機負載預(yù)測是一件非常困難的事。負載的變化具有嚴重的非線性、極大的不確定性和隨機性，因此很難對其建立起精確的數(shù)學預(yù)測模型，而應(yīng)用遺傳神經(jīng)網(wǎng)絡(luò)則可以較好地解決這一問題。

遺傳神經(jīng)網(wǎng)絡(luò)是將遺傳算法應(yīng)用到BP神經(jīng)網(wǎng)絡(luò)中，以實現(xiàn)對BP神經(jīng)網(wǎng)絡(luò)初始權(quán)閾值的優(yōu)化。由于遺傳算法具有全局搜索、收斂速度快的特點，將其與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合，不僅能發(fā)揮神經(jīng)網(wǎng)絡(luò)的泛化映射能力，還可以使神經(jīng)網(wǎng)絡(luò)克服收斂速度慢和容易陷入局部誤差極小點等缺點[3]。

就主機負載的短期預(yù)測而言，如何允分利用單因索時間序列所提供的信息就顯得至關(guān)重要。為此，本文采用將一維時間序列通過向空間擴維，變化為多維時間序列模式的分析思想，充分挖掘一維時間序列所提供的信息，根據(jù)時間序列數(shù)據(jù)重建動態(tài)模型以實現(xiàn)對負載變化的預(yù)測。可以通過實驗測試，確定某一時間延遲k，使序列中下一個抽樣時刻t+T時刻的觀測值與當前時刻t之前的k個時段的觀測值(l(t)，l(t-T)，l(t-2T)，...，l(l-KT))之間有較好的相關(guān)關(guān)系。并以l(t)，l(t-T)，l(t-2T)，...，l(l-kT)為控制參數(shù)作為網(wǎng)絡(luò)的輸入變量，l(t+T)為網(wǎng)絡(luò)的輸出變量，由此來建立一個k個輸入，1個輸出的遺傳神經(jīng)網(wǎng)絡(luò)。

應(yīng)用遺傳神經(jīng)網(wǎng)絡(luò)對主機負載建立一種非線性自回歸預(yù)測模型，其模型的差分方程可表示為:

l(t+T)=f(l(t)，l(t-T)，l(t-2T)，...，l(l-kT)) (1)

其中t為當前時間，l(t)為當前時刻t時的負載;l(t+T)為輸出向量，表示t+T時刻的預(yù)測負載;f是非線性函數(shù)。現(xiàn)已有資料證明大部分的非線性系統(tǒng)都可用式(1)表示。實驗證明，通過對歷史樣本數(shù)據(jù)進行反復(fù)訓練，可以使該遺傳神經(jīng)網(wǎng)絡(luò)的負載誤差控制在10%以內(nèi)。建立的主機負載預(yù)測模型如圖1所示。

4 算法實現(xiàn)與調(diào)度策略

在PVM環(huán)境下，通過研究PVM的函數(shù)以及PVM的實現(xiàn)機制發(fā)現(xiàn)，PVM主要是利用函數(shù)pvm_spawn()來實現(xiàn)子任務(wù)的生成的，其函數(shù)說明如下[4]:

int numt=pvm_spawn(char*task，char **argv，int flag，char*where，int ntask，int tids)

通過修改主結(jié)點中的該函數(shù)，可以實現(xiàn)動態(tài)任務(wù)調(diào)度算法。另外，負載信息收集和負載信息的預(yù)測以及進程的遷移都以守護進程Daemon方式運行在機群系統(tǒng)中的各個結(jié)點上。遺傳神經(jīng)網(wǎng)絡(luò)學習過程可以事先進行，所以學習速度并不是關(guān)鍵所在。為了便于算法的描述，先給出以下名稱定義:

定義1 負載狀態(tài):為了避免抖動，達到穩(wěn)定性，本文采用了雙閾值Lmax和Lmin，它們是根據(jù)系統(tǒng)總的負載情況動態(tài)可調(diào)的。根據(jù)結(jié)點的負載與閥值的關(guān)系，將結(jié)點分成分為三類:

1)重載:負載值L>Lmax

2)適載:Lmin<負載值L

3)輕載:負載值L

其中，Lmax是根據(jù)系統(tǒng)的整體負載水平動態(tài)變化的，任務(wù)主要由處于重載的結(jié)點遷移到申請任務(wù)的輕載結(jié)點上。

定義2 發(fā)送者和接收者:在一次任務(wù)遷移中，任務(wù)遷移的源結(jié)點為發(fā)送者，任務(wù)遷移的目的結(jié)點為接收者。

本文在充分借鑒集中式任務(wù)調(diào)度算法CJD(Center Job Dispatcher)[5]的基礎(chǔ)上，對該該算法加以改進，設(shè)計出基于主機負載預(yù)測的集中式任務(wù)調(diào)度算法CJD-HLP(Center Job Dispatcher Based on Host Load Predicted)。在該算法中，主結(jié)點中維護著兩個信息表(子節(jié)點中無需信息表)，即發(fā)送者表和接收者表，其中發(fā)送者表記錄系統(tǒng)中的發(fā)送者結(jié)點的數(shù)據(jù)結(jié)構(gòu)，接收者表記錄接收者結(jié)點數(shù)據(jù)結(jié)構(gòu)。算法采用接收者驅(qū)動和子結(jié)點主動匯報的方式，并且只有子結(jié)點的負載狀況由忙變閑時才向主結(jié)點主動匯報負載情況，匯報周期可以采取自適應(yīng)方式。圖2為CJD-HLP算法模型。

下面分別描述主結(jié)點與子結(jié)點調(diào)度算法。

4.1 主結(jié)點調(diào)度算法

Step1:系統(tǒng)初始化，將主結(jié)點中的發(fā)送者表和接收者表清空，

Step2:等待子結(jié)點發(fā)送來的請求任務(wù)消息。

Step3:if(在t時刻收到子結(jié)點iNode發(fā)來的請求任務(wù)消息) 轉(zhuǎn)(1)進行處理;

else轉(zhuǎn)Step2;

1)更新信息表，向系統(tǒng)內(nèi)的所有其他子結(jié)點廣播任務(wù)請求信號，包括接收者iNode的地址Raddr，請求的任務(wù)數(shù)量Rtask;

2)指示系統(tǒng)內(nèi)其他子結(jié)點機停止抽樣，并詢問它們在下一時間段t+T的負載情況;

3)主結(jié)點轉(zhuǎn)入wait狀態(tài);接收響應(yīng)信號，更新信息表。將t到t+T時間段內(nèi)收到的所有重載結(jié)點發(fā)來的響應(yīng)信息(包括發(fā)送者地址Saddr、待分配的任務(wù)數(shù)Wtask等)記錄到發(fā)送者表中。

4)根據(jù)構(gòu)造的效益函數(shù)f=benifit(i，j)-cost(i，j)計算發(fā)送者表中的所有發(fā)送者的任務(wù)遷移效益，其中benifit(i，j)和cost(i，j)分別為從結(jié)點i遷移到結(jié)點j帶來的收益和系統(tǒng)開銷。根據(jù)f的值對各發(fā)送者進行排序;

5)選擇效益最高的發(fā)送者jNode，指示其將過載任務(wù)遷移到iNode，更新信息表。

Step4: 算法結(jié)束

4.2 子結(jié)點調(diào)度算法

Step1:所有子結(jié)點在抽樣時刻t調(diào)用守護進程對下一個抽樣時間段t+T內(nèi)的負載進行預(yù)測。

Step2:if(預(yù)測到在t+T時間段內(nèi)處于輕載)轉(zhuǎn)Step3，調(diào)度接收者算法;

else if(預(yù)測到在t+T時間段內(nèi)處于重載) 轉(zhuǎn)Step4，調(diào)用發(fā)送者算法;

else (子結(jié)點處于適載) 轉(zhuǎn) Step1

Step3:接收者算法:

1) 向主結(jié)點發(fā)送任務(wù)請求信號，包括接收者iNode的地址Raddr，請求的任務(wù)數(shù)量Rtask;

2) 停止抽樣，進入wait狀態(tài);

3) 收到主結(jié)點的響應(yīng)指令，接收從發(fā)送者遷移的任務(wù);

4) 轉(zhuǎn) Step1

Step4:發(fā)送者算法:

1) 向主結(jié)點發(fā)送響應(yīng)信號(包括發(fā)送者地址Saddr、待分配的任務(wù)數(shù)Wtask等信息);

2) 停止抽樣，等待主結(jié)點發(fā)來的遷移指令;

3) if(收到遷移任務(wù)指令)向接收者iNode遷移任務(wù);

else轉(zhuǎn)Step1

Step5: 算法結(jié)束

5 實驗結(jié)果及分析

本文作者組建了一個機群系統(tǒng)，軟硬件配置如下:1)軟件環(huán)境:WPVM 3.4 on Windows XP，VC++6.0，TCP/IP，2)硬件環(huán)境:P4 2.66 CPU，512M DRAM，100Mbps Ethernet。

對BP神經(jīng)網(wǎng)絡(luò)進行如下參數(shù)設(shè)置:根據(jù)仿真實驗，1)式中的k取10效果最好，抽樣周期取T=2秒，這樣BP神經(jīng)網(wǎng)絡(luò)的輸入層節(jié)點數(shù)為10;根據(jù)Hecht-Nielsen理論，隱含層節(jié)點數(shù)為2N+1，其中N為輸人節(jié)點數(shù)。綜合考慮網(wǎng)絡(luò)的收斂速度和輸出精度，將隱含層節(jié)點數(shù)設(shè)置為18;輸出層為預(yù)測負載(主機上運行的進程數(shù))，所以輸出為1。這樣，得到網(wǎng)絡(luò)的拓撲結(jié)構(gòu)為10×18×1。網(wǎng)絡(luò)隱含層神經(jīng)元變換函數(shù)采用tansig型，輸出層采用purelin型線性函數(shù)。

為了測試該算法的性能，現(xiàn)取5臺上述配置的PC組成一個機群系統(tǒng)，并以典型的求素數(shù)做為算例。由于求素數(shù)程序的循環(huán)迭代相互獨立，而且每次迭代的執(zhí)行時間也不相同，能夠很好的反映在實際的并行系統(tǒng)上任務(wù)的運行情況。本文分別采用二次均分法，CJD算法和本文提出的CJD-HLP算法并行執(zhí)行求素數(shù)程序，并采用加速比做為各算法在不同規(guī)模下進行比較的指標，比較結(jié)果如表1所示。

實驗結(jié)果顯示，在當計算的規(guī)模比較小時，以上三種算法的并行效果沒有顯著差別，但是當數(shù)據(jù)規(guī)模非常大時，尤其是各結(jié)點任務(wù)變化很大時，動態(tài)任務(wù)調(diào)度算法加速比高于靜態(tài)調(diào)度算法，并且基于預(yù)測的任務(wù)調(diào)度算法加速比明顯高于其他兩種算法，這主要是由于:

1)隨著計算規(guī)模的增大，動態(tài)任務(wù)調(diào)度帶來的好處遠遠大于調(diào)度帶來的額外開銷。

2)采用接收者主動匯報方法，各子結(jié)點之間無需交換信息，降低了通訊開銷。

3)通過有效調(diào)度，各結(jié)點不會出現(xiàn)空閑狀態(tài)，從而提高了機群系統(tǒng)的整體并行效率。

6 結(jié)束語

本文提出基于遺傳神經(jīng)網(wǎng)絡(luò)的主機負載預(yù)測模型，并基于該模型設(shè)計實現(xiàn)了CJD-HLP算法。采用預(yù)測法獲得主機負載，有效地避免了因各種時延導致決策信息陳舊而引起進程遷移的抖動，提高了任務(wù)調(diào)度的實時性、準確性，提高了機群系統(tǒng)的并行性能。

參考文獻:

[1] 鞠九濱，王勇.調(diào)度PVM任務(wù)[J].計算機學報，1997，20(5):470-474.

[2] 李慶華，郭志鑫.一種面向工作站網(wǎng)絡(luò)的系統(tǒng)負載預(yù)測方法[J].華中科技大學學報，2002，30(6):49-51.

[3] 閻平凡，張長水.人工神經(jīng)網(wǎng)絡(luò)與模擬進化計算[M].北京:清華大學出版社，2000:396-421.

[4] 張建軍，蔣廷耀，郭志鑫.PVM中動態(tài)負載平衡的設(shè)計和實現(xiàn)[J].計算機工程，2005，31(7):63-64.

[5] 李慶華，尹杜紅.一個基于預(yù)測的負載平衡策略[J].計算機與數(shù)字工程，2003，31(4):54-57.