一種基于預測的反饋網(wǎng)格作業(yè)調度模型
2006-12-31 00:00:00程宏兵楊庚
計算機應用研究 2006年8期
(1.南京郵電大學 計算機科學與技術系， 江蘇 南京 210003; 2.江蘇廣播電視大學 信息工程學院， 江蘇 南京 210017)
摘 要：網(wǎng)格計算中的資源是動態(tài)和異構的，常規(guī)的靜態(tài)作業(yè)調度方法不適宜網(wǎng)格計算環(huán)境，對于網(wǎng)格計算中一類并行計算的有效執(zhí)行有賴于網(wǎng)格資源（CPU和網(wǎng)絡帶寬等）與作業(yè)的有效匹配。提出了一種基于資源預測結果對作業(yè)進行調度的策略，首先闡述了網(wǎng)格主機負載預測的研究成果——IAR模型，并提出了一種預測網(wǎng)絡帶寬的工具——網(wǎng)絡性能平面，利用資源預測結果構造了一種反饋作業(yè)調度模型并對一類基于時間平衡的作業(yè)進行實驗。結果表明，該模型在與其他諸多方法比較中，取得了執(zhí)行時間較短和穩(wěn)定性較好的效果。
關鍵詞：資源預測； 網(wǎng)格計算； 負載平衡； 作業(yè)調度
中圖法分類號：TP315文獻標識碼：A
文章編號：1001 3695(2006)08 0022 03
Feedback Job Scheduling Model in Grid Computing Based on Resource Prediction
CHENG Hong bing 1，2， YANG Geng1
(1.Dept. of Computer Science Technology， Nanjing University of Posts Telecommunications， Nanjing Jiangsu 210003， China; 2.School of Information Engineering， Jiangsu Radio TV University， Nanjing Jiangsu 210017， China)
Abstract:The resources in grid computing environments is heterogeneous and dynamic. The normal ways of job scheduling are not fit to grid computing. Efficient execution of a kind of parallel computations can require mappings of tasks to grid resources(including CPU load and net bandwidth， etc). The paper proposes a job scheduling model that based on the result of resources prediction. Firstly present techniques: an improved AR model developed in previous work， then address a tool: net surface which can predict the capability of net bandwidth， finally present a feedback model based on the results of resources prediction and experiment it on a kind of time balancing job， the result of these experiments demonstrate the model can produce execution times that are both significantly faster and less variable than other models.
Key words:Resource Prediction; Grid Computing; Load Balancing; Job Scheduling
網(wǎng)格是一個集成的計算與資源環(huán)境，其目標是要把分布在不同地方的各種資源，如CPU、存儲器、程序、數(shù)據(jù)等聯(lián)合起來，形成一個虛擬的、統(tǒng)一的、強大的計算環(huán)境[1]，把這些分散的資源統(tǒng)一成一個能協(xié)同工作的網(wǎng)絡計算機。作業(yè)調度是網(wǎng)格計算中的一個關鍵技術，直接影響到網(wǎng)格計算性能的好壞，網(wǎng)格環(huán)境中作業(yè)調度遇到的一個困難就是各種資源是動態(tài)和異構的。每個處理器的速度是不一樣的，網(wǎng)絡帶寬也是動態(tài)變化的，用常規(guī)的靜態(tài)調度方法不能滿足網(wǎng)絡異構和動態(tài)的特性。對于作業(yè)調度，國外計算機界提出了不少方法，如負載均衡的調度方法；J.M，Schopf等人分析了隨機調度算法（Stochastic Scheduling）[2]；L.Y. Yang等人研究了保守調度作業(yè)方法[3]。國內對網(wǎng)格作業(yè)調度算法也進行了積極的研究，并已取得了一些研究成果。查禮和徐志偉討論了一種數(shù)據(jù)與計算密集混合元任務的調度算法TCR(Transfer Computation Ratio)[4]；Jian Zhang等人提出了一種動態(tài)調度算法[5]；金海等人開發(fā)了一種容錯計算網(wǎng)格作業(yè)調度的隨機Petri網(wǎng)模型，并給出了網(wǎng)格作業(yè)分派策略和計算站點內的作業(yè)選擇策略[6]；G. Yang等人研究了把整個任務分成幾個子任務的塊 Broyden算法[7]，并將其應用于非線性方程組的并行求解。
1 資源預測建模和作業(yè)執(zhí)行時間建模
網(wǎng)格環(huán)境中包括各種資源，如CPU、網(wǎng)絡帶寬、存儲器、程序、數(shù)據(jù)等，其中CPU和網(wǎng)絡帶寬是網(wǎng)格環(huán)境中決定性的資源，是我們預測的主要對象，下面分別討論。
1.1CPU負載預測建摸
本文使用我們先前的研究成果，即網(wǎng)格計算中自動回歸改進（IAR）模型對CPU負載進行預測，下面具體給出該改進模型。
AR模型是一種常見的分析時間序列的模型[8]。p階的AR模型可以記為AR(p)，用數(shù)學公式表達為
其中，{Xt}稱為AR(p)序列，a=(a1，a2，…，ap)T稱為AR(p)模型的自回歸系數(shù)，{εt}是滿足正態(tài)分布N(0，σ2)的白噪聲。
自回歸系數(shù)a=(a1，a2，…，ap)T決定了AR(p)模型的性質，其可由Yule-Walker方程解出，即由γ=Γa得到a=Γ-1γ，其中γ=(γ1，γ2，…，γp)T，Γ是一個矩陣。
γk是序列{Xt}的自協(xié)方差。當解出這個模型后，便可由Xt-1，Xt-2，…，Xt-p來預測Xt的值。
線性時間序列模型AR(p)只有當其階數(shù)p大于一定的值時才能取得較好的預測效果，從式(1)可知由采集的歷史數(shù)據(jù)Ct-1，Ct-2，…，Ct-p來預測Xt的值，其中Ct-1，Ct-2，…，Ct-p是p個距離Xt最近的主機負載的歷史采集結果。
現(xiàn)給出IAR(p)模型的具體步驟和算法：對于已知的歷史主機時間負載序列設為T，假設對其采樣頻率為f，則在時間T內共有T×f個采集樣點簡記為n，采集樣點序列記為C1，C2，…，Cn。再設有一網(wǎng)格作業(yè)預計時間為Tj，則按照聚合算法可知用于預測該作業(yè)未來運行時間段時須將C1，C2，…，Cn以m=Tj×f為聚合度進行聚合，記聚合后的序列為X1，X2，…，Xi。假設對AR(p)模型設p=pk，現(xiàn)就i的取值情況分以下三種情況討論。
(1)當i＜pk時，此時使用X1，X2，…，Xi; Cn-pk+i，…，Cn序列作為AR(p)預測模型輸入值進行預測 (此處實驗時我們選擇Cn-pk+i，…，Cn序列作為預測補足序列的理由是選擇較接近被預測對象的采集點效果會更符合實際預測值，在實際操作時視具體情況而定)。
(2)當i=pk時，此時使用X1，X2，…，Xi序列作為AR(p)預測模型輸入值進行預測。
(3)當i＞pk時，此時依［i/pk］為聚合度再次對X1，X2，…，Xi進行聚合，以所得聚合結果序列S1，S2，…，Sp作為AR(p)預測模型輸入值進行預測。其中，聚合公式為
利用IAR預測到的是在未來作業(yè)預計運行時間Tj的主機負載平均值，在我們早前的主機負載實驗中，IAR取得了很好的效果，性能優(yōu)于AR。
我們進行主機負載預測一個基本思想就是當負載變化很大的時候，需要把負載預測值加上一個變化量作為作業(yè)調度的負載依據(jù)，我們以序列{ai}的標準差σt表示它的變化量，即
σt即為在未來Tj內CPU負載可能的變化量，在IAR模型中，用at+1+σt+1作為負載預測的最終結果來調度任務。
1.2網(wǎng)絡帶寬的預測
相關研究表明[9]，對于網(wǎng)絡性能的預測至少要包括以下三個因素：①通信量；②通信時間；③通信終結點。在文中，使用網(wǎng)絡性能平面來刻畫網(wǎng)絡帶寬的預測情況，并提出一種四元組表示網(wǎng)絡性能預測結果，下面介紹具體方法。
定義Netsurface(t，M)=p(t/M)。其中Netsurface(t，M)是由參數(shù)M，t決定的二維平面。M是通信量集合，t是通信時間。下面給出實驗時當通信量固定在M=960KB，M=1600KB，M=2240KB時的時延概率分布圖（圖1中X軸代表通信時間即時延，Y軸代表概率）。
現(xiàn)在由以上信息產生，提出了網(wǎng)絡性能平面模型圖（其中X軸代表通信時間即時延，Z軸代表概率，Y軸代表通信量）。產生網(wǎng)絡性能平面可以考慮以下兩種途徑：①窮盡所有的信息量的時延概率分布情況；②使用Monte Carlo近似方法的情況。顯然①不合實際，對于②可以使用一種網(wǎng)絡性能測試基準算法（如Network Weather System）在網(wǎng)絡所有的節(jié)點上隨機地進行。通信節(jié)點之間的選擇、通信量的大小都是隨機的，試驗結果表明基于Monte Carlo方法使用網(wǎng)絡性能測試基準算法對網(wǎng)絡性能隨機的抽樣測試來對網(wǎng)絡性能進行預測是可以很好地刻畫實際網(wǎng)絡性能的。下面給出使用Monte Carlo方法獲得的網(wǎng)絡性能平面示意圖，如圖2所示。
我們用四元組（T1，T2，M，t）表示網(wǎng)絡性能預測的結果，其中TT1，和T2表示兩個通信終端，M表示通信量，t表示通信量M在T1和T2終端完成通信最大概率的時間。
1.3作業(yè)執(zhí)行時間建模
在此采用一種基于時間平衡的作業(yè)執(zhí)行時間模型，對于一類數(shù)據(jù)并行性(Dataparallel)網(wǎng)格應用，我們希望各個CPU負載均衡，即每個子任務的處理時間都一樣。可用公式表示
其中，Di表示分配給處理器i的待處理數(shù)據(jù)，Dtotal表示總共待處理的數(shù)據(jù)，Ei(Di)表示處理器i處理數(shù)據(jù)Di所花的時間。現(xiàn)在我們已經預測得到了兩個數(shù)據(jù)，即在未來Tj時間內CPU負載的平均值at+1、變化量σt和刻畫網(wǎng)絡性能的四元組，于是可以利用這三種數(shù)據(jù)進行調度。調度的根本目的就是要把任務平均分配給各個參加計算的處理器，使得每個子任務在各個處理器上的執(zhí)行時間相同，同時充分考慮把通信量大的任務分配給帶寬較大的節(jié)點，從而使得整個任務的執(zhí)行時間最短。為了實現(xiàn)這個目的，必須利用已經得到的處理器信息對處理器有任務競爭時的性能進行建模，模型的好壞直接關系到調度算法的好壞。對于Ei(Di)，我們采用如下的模型：
其中，start_up表示初始化的時間，T0＝Trans(1，NetworkCapacity)表示在網(wǎng)絡帶寬為NetworkCapacity的情況下，傳輸單個數(shù)據(jù)單元需要的時間；C0＝Comp(1，CPUCapacity)，表示在CPU計算能力為CPUCapacity的情況下，計算單個數(shù)據(jù)單元需要的時間。顯然，還有其他的應用程序要占用網(wǎng)絡帶寬、競爭CPU資源，我們引入?yún)?shù)α和β，α表示由于其他應用程序占用帶寬使得傳輸時間增大的因子，β表示由于其他應用程序競爭CPU資源使得計算時間增加的因子。α，β應當是隨實際的網(wǎng)絡帶寬和CPU負載變化而變化的，即α=α(Effective Network Capacity)，β=β(Effective CPU Load)。
2 作業(yè)調度系統(tǒng)及調度方法
基于上面的研究結果我們已經獲得了一些數(shù)據(jù)參數(shù)，如預測到的主機負載加變化量和預測得到的網(wǎng)絡帶寬四元組以及作業(yè)執(zhí)行時間模型的執(zhí)行時間和數(shù)據(jù)傳輸時間等一些數(shù)據(jù)參數(shù)，在此構建一種基于資源預測的反饋調度模型，如圖3所示。
該模型中的調度器我們采用資源預測結果和作業(yè)資源需求進行最佳匹配的方法，進行作業(yè)的調度。
下面介紹一些常見的調度模型：
（1）利用單步預測的CPU負載值Ct+1進行調度，即相當于m=1，稱這種算法為單步調度OSS（One Step Scheduling）。
（2）利用聚合后預測得到的平均CPU負載at+1進行調度，稱這種算法為預測平均值調度算法PMIS(Predicted Mean Interval Value)。
（3）利用靜態(tài)聚合后獲得的CPU平均負載at+1加上變化量σt+1進行調度[12]，即相當于m是一個固定的值，稱這種算法為固定聚合保守算法FACS(Fixed Aggregation Conservative Scheduling)。
（4）利用歷史信息C1，C2，…，Ct的平均值進行調度[8]，稱這種算法為歷史平均調度算法HMS(History Mean Schedul)。
（5）利用歷史信息C1，C2，…，Ct的平均值加上它的變化量方差進行調度[2]，稱這種算法為歷史保留調度算法HCS（History Conservative Scheduling）。
3 實驗
3.1實驗方法
為了檢驗模型的有效性，參考一些實驗方法和手段[10～12]，通過編程我們進行了一系列實驗測試。與常用的一些作業(yè)調度模型進行了比較，我們的作業(yè)調度模型采用資源預測反饋調度模型，記為RPFS(Resource Prediction Feedback Scheduling)。我們在六臺機器上進行了算法的實驗，這六臺機器的配置分別為： Intel Celeron2.0GHz，Intel Celeron 800MHz和AMD Athlon 1600MHz及三臺P4 1.8GHz。采用Dinda開發(fā)的工具Load Trace Playback Tool[13]來產生各個機器上的背景工作負載，模擬對CPU資源的競爭。我們采用20階的IAR模型，通過計算16000個歷史數(shù)據(jù)點求解該模型。考慮了四種情況的背景工作流：高平均值高標準差的工作流、高平均值低標準差的工作流、低平均值高標準差的工作流和低平均值低標準差的工作流。
3.2實驗結果
下面給出我們實驗的重復次數(shù)、平均值、標準差、最小值和最大值等統(tǒng)計數(shù)據(jù)，如表1～表4所示。
3.3結果分析
從以上數(shù)據(jù)可以看出，我們提出的基于資源預測的反饋調度模型方法都是較優(yōu)的，在表1、表3和表4中是最優(yōu)的。這說明RPFS模型能很好地適應CPU負載高度變化的情況。由于單步預測OSS不能有效預測子任務整個執(zhí)行期間的CPU平均負載，因此OSS模型算法的性能較壞。在CPU負載低標準差的情況下，HCS和HMS模型算法的性能與RPFS模型算法的性能相接近，這說明在CPU負載變化很小的情況下，利用歷史數(shù)據(jù)的平均值進行調度是可行的。但是在CPU負載變化較大的情況下，HMS的性能變得不是很好，這說明僅僅用歷史信息的平均值進行預測在負載變化很大的情況下不是很有效。從總體上來說，RPFS，F(xiàn)ACS和HCS三種模型算法的性能要高于PMIS，OSS和HMS，這說明如果把CPU負載的變化情況考慮進來進行調度可以提高調度的性能。從具體數(shù)量來看，RPFS模型算法的平均時間要比PMIS少5.31%～15.67%，比HMS少3.94%～28.43%，比HCS少2.35%～10.84%。對于標準差，在高負載的情況下，RPFS模型算法的標準差明顯小于其他算法，例如，比PMIS要少58.02%～70.60%，比HMS要少31.40%～66.59%，比HCS要少49.22%～53.51%。但是在負載較小時，這種優(yōu)勢不太明顯。對于每種模型算法的標準差與平均值的比值，RPFS是2.04%～4.33%，F(xiàn)ACS是1.67%～6.09%，HCS是0.74%～8.39%，HMS是0.16%～10.34%，OSS是0.52%～2.51%，PMIS是2.84%～13.56%。可見，RPFS模型算法有較好的穩(wěn)定性。
4 結束語
作業(yè)調度是網(wǎng)格計算中的一個關鍵技術。
對于一類數(shù)據(jù)并行性應用，通過有效地預測出作業(yè)的執(zhí)行時間及在該時間內的平均CPU負載，同時把CPU負載的變化考慮到我們的調度模型中來，提出了一種基于資源預測結果的反饋作業(yè)調度模型。實驗表明，這種模型能有效地適應CPU負載高度變化的情況。在本文的研究中主要解決如何有效地進行作業(yè)同CPU資源和網(wǎng)絡帶寬的映射問題，我們假設在調度過程中，所有參與計算的機器數(shù)目是固定的，并且在計算的過程中不會退出或者出現(xiàn)故障，每臺機器都是單CPU的。對這些動態(tài)情況的研究是我們下一步的研究課題，將是很有意義的。
由于文中所提到的資源預測模型（CPU負載預測、網(wǎng)絡帶寬預測）、作業(yè)運行時間建模模型雖然在一定的條件下能取得較好的效果，但對它們的刻畫還欠精確。今后我們希望能夠對CPU負載和網(wǎng)絡帶寬的概率統(tǒng)計特性進行精確的數(shù)學描述，使我們提出的調度模型更加精確，所有這些都是我們未來的研究方向。
參考文獻：
[1]Ian Foster， Carl Kesselman. The Grid: Blueprint for a New Computing Infrastructure(2nd Edition)[M]. San Francisco: Morgan Kaufmann Publishers， Inc.， 2004.
[2]Schopf J M， Berman F. Stochastic Scheduling[C]. Portland: Proceedings of the 1999 ACM Conference on Supercomputing， 1999.48-58.
[3]Yang L Y， Schopf J M， Foster I. Conservative Scheduling: Using Predicted Variance to Improve Scheduling Decisions in Dynamic Environments[C]. Phoenix: Supercomputing’03， 2003.
[4]查禮，徐志偉，林國璋，等.數(shù)據(jù)和計算密集混合元任務的網(wǎng)格調度算法[J].計算機工程與設計，2003，24(10):1-4.
[5]Jian Zhang， Xinda Lu. A Dynamic Job Scheduling Algorithm for Computational Grid[C]. Proceeding of the 2nd International Workshop on Grid and Cooperative Computing(GCC2003)， 2003.40-47.
[6]金海，陳剛，趙美平.容錯計算網(wǎng)格作業(yè)調度模型的研究[J].計算機研究與發(fā)展， 2004，41(8):1382-1388.
[7]楊庚.一類求解非線性方程組算法的并行性能分析[J].計算機學報， 2000，23(10):1035-1039.
[8]Dinda P A， O’HallaronD R. Host Load Prediction Using Linear Models[J]. ClusterComputing， 2000，3(4):132-145.
[9]Kumar S， Das S K， Biswas R. Graph Partitioning for Parallel Applications in Heterogeneous Grid Environments[C]. Florida: International Parallel and Distributed Processing Symposium(IPDPS2002)， 2002.787-792.
[10]楊庚，王紹棣，沈金龍.基于曙光并行機的超大規(guī)模非線性方程組并行算法研究[J].計算機學報， 2002，25(4):397-402.
[11]Geng Yang， Chunming Rong， Daiyue Ping. A Distributed Honeypots for Grid Security[C]. Proceedings of the 2nd Int. Workshop on Grid and Cooperative Computing(GCC2003)， 2003.1083-1087.
[12]Yang L Y， et al. Conservative Scheduling:Using Predicted Variance to Improve Scheduling Decisions in Dynamic Environments[C]. Phoenix: Supercomputing’03， 2003.454-461.
[13]http://www.cs.northwestern.edu/~pdinda//LoadTraces/， 2004 12-09[EB/OL].
作者簡介：程宏兵(1979-)，男，江西九江人，博士研究生，主要研究方向為信息安全、網(wǎng)格計算、計算機網(wǎng)絡；楊庚(1961-)，男，江蘇建湖人，IEEECS，SIAM會員，教授，博導，主要研究方向為計算機通信與網(wǎng)絡、并行與分布式計算、信息安全。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
