一種基于神經網絡的網格實時調度算法

摘 要：提出一種在指定的最終期限內，利用隊列技術來模擬調度動態資源，構建一個數學神經模型調度應用的子任務，使用GridSim 工具測試的調度算法，通過大約90%的模擬實驗說明了模型調度任務是成功和高效的。

關鍵詞：調度；網格計算；神經網絡；并行計算

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2009)06-2095-03

doi:10.3969/j.issn.1001-3695.2009.06.028

Grid real-time scheduling algorithm based on neural network

LI Sheng-xin1，2，DUAN Sheng1

(1.Dept. of Computer Science， Xiangnan University， Chenzhou Hunan 423000， China；2.School of Computer Communication， Hunan University，Changsha 410082，China）

Abstract:Within specified deadlines，this paper modeled performance dynamism of resources with the help of queuing techniques.Employed a mathematical neural model afterwards， to schedule subtasks of the application.Implemented the proposed model on GridSim toolkit to evaluate the performance of scheduling algorithms.Simulation experiments show that in approximately 90% of cases，this model schedules tasks successfully and efficiently.

Key words:scheduling; grid computing; neural networks; parallel computing

0 引言

網格計算是利用硬件和軟件資源來提供可靠的、可調節的和方便的接口來完成高端計算量^[1]。一個共享環境的實現包括可提供持久穩固的和標準的服務配置，這些配置支持更新、資源共享和分布的群體^[2]。真正的難題是在網格環境下對于同等資源的共享和動態地解決問題及多制度的虛擬組織^[3]。

對于大多數分布式計算平臺，一個要求就是利用可用資源充分調度分布的申請以達到高的執行效率。在傳統的并行和分布式系統中，調度算法集中將這些作為一個基本問題來研究，而傳統的調度模式在實踐中通常提出單一的網格調度，原因如下^[4]：所有的資源均按照一個單一的管理模式，提供單一系統模型，調度控制所有的資源并且資源池是不變的。現在問題的焦點是加入的申請能夠根據某一方法調度管理，但是對于能夠提供每一個申請都被很好執行的固定點的性能有影響。

設計基于網格的調度算法要考慮很多獨特性，包括異構自治、動態執行、資源選擇、計算數據分離，重點就是實時應用的調度。實時應用通常定義為在有限的時間內響應，大多是指隊列中緊急請求。一個緊急請求有一個最終期限通常認為是：最終期限直到服務開始和最終期限直到服務結束。前者，消費者停留在系統中直到完成服務需求；后者，消費者可以取消服務因為超過了最終期限。分別處理兩種消費者：通過網格調度的實時應用的最終期限為直到服務結束，來自于本地調度的緊急請求的最終期限為直到服務開始。網格中實時應用的調度作為在并行隊列的一種路由實時應用，每種資源看做是一服務隊列，假設實時應用對象由幾個獨立的任務組成，每個任務有最終期限直到服務結束，以最終期限均滿足的方式來調度這些任務。首先根據隊列技術模擬動態資源的執行，接著使用神經網絡的數學模型來調度應用的子任務。當前的一些研究只是在非緊急應用中，對于緊急應用的情況很少涉及，本文提出了一種在網格調度中包括了緊急和非緊急應用的模式，其優點如下：在非專用的分布式系統中調度執行考慮了緊急任務；在時間約束和異構資源下提出了有效和快速的并行調度算法，在并行機中執行時間復雜度為O(1)。

1 神經網絡實現網格調度

神經網絡應用于組合優化問題首先是由Hopfield等人^[5]在1985年提出。他們使用了事先定義的能量函數E，二次方程式如下：

E=Ni=1Nj=1WijViVj+Ni=1ViIi（1）

其中：Wij表示第i個神經元到第j個神經元間的突觸連接長度，并且Wij=Wji總是滿足；Ii是第i個神經元的常量斜線。Hopfield給出了第i個神經元的動作方程式如下：

dUi/dt=-Ui/τ-E/Vi（2）

隨著持續的非遞減的輸出，可微函數叫做S型函數如下： 

Vi=f(Ui)=1/2(tan h(λ0Ui)+1)(3)

λ0是常量，叫做腰槽，決定S型函數的斜面。

1.1 神經網絡數學模型

虛擬的神經網絡數學模型由兩部分組成^[6]，即神經元和突觸連接。輸出信號傳輸從一個神經元到其他的神經元通過突觸連接。一個神經元輸入信號的決定來自其他神經元的輸入信號的線性權值和，各自的權值是突觸連接的長度。每個虛擬的神經元有輸入U和輸出V，第i個神經元的輸出為Vi =f (Ui)， f叫做神經元的輸入或輸出函數。第i個神經元與被確定的其他神經元的互相聯絡通過一個動作方程式，第i個神經元輸入狀態的變化被提出通過部分與第i個神經元輸出有關的計算能量函數E，E是一個N個變量函數：E（V1，V2，…，Vn）。第i個神經元的動作方程式為 

dUi/dt=-E(V1，V2，…，Vn)/Vi=-dE/dVi（4）

通常神經網絡計算的目標是優化構造的計算能量函數。能量函數不僅決定了有多少神經元可被用于系統而且還指定了在神經元之間突觸連接的長度，甚至可根據給出問題的信息來進行構造，考慮了必需的限制及價值函數。能量函數定義為

E=∫dE=-∫dUi/dtdVi（5）

基于歐拉第一理論U(t+1)的值確定為

U(t+1)=U(t)+ΔU(t)×Δt（6）

ΔU(t)在式（4）中給出，終止條件為

ΔU(t)=0（7）

式（7）的條件意味著限制均滿足。

1.2 用數學神經模型描述問題

因為數學神經模型是一個受限制的模型，首先所有的限制必須都被指定，接著需要一個合適的模型來包含這些限制，最后提出方法包含所有的限制。就像前面提到的，處理問題包括了對于某些資源涉及緊急任務的調度。因此，第一個限制是對于每個任務i需要最終期限（di）， 第二個是候選資源的數量，調度模型考慮了N個任務被調度在一些資源和關于問題域的下述假設，對于每個資源每個任務的執行時間是預知的，出于簡單考慮，一個任務不能被分派在不同的資源，也就是不允許在資源間移動任務，調度參數包括任務列表、需要的資源和時間變量如圖1所示。

X軸表示任務變量為1~N（被調度的任務總數），Y軸表示資源變量為1~M（候選資源總數），Z軸表示時間變量，K表示一個具體的時間小于或等于T（所有最終期限的和）。一個變量Vijk表示為任務i在某個時間k執行在資源j上。假設Vijk=1，表示任務i在時間k執行在資源j上；否則，Vijk=0。每個Vijk相當于提出的神經網絡模型中的神經元。

1.2.1 映射限制到動作方程式

為了執行調度的限制，兩類因素使用到動作方程式，即興奮和抑制因素。抑制因素阻止神經元當它將要違反問題條件時，興奮因素激勵神經元當所有的需求和條件均滿足時^[7]。

合并限制在動作方程式有以下六個抑制因素如下：

a)dUijk/dt=-ANi1=1i1≠iVijkVi1jk

b)-BMj1=1j1≠j Tk1=1VijkVij1k1

c)-CL(2(Tk1=1Vijk1-Pij))

d)-DK(2(Ni1=1Vi1jk-1))

e)-EH(k-(di-1))

f)-FH(Pij-di)(8)

全部的抑制和興奮因素在動作方程中的影響歸結為：第一個抑制狀態是一個資源j在某個時間k只能提供給任務i，如果任務i在時間k執行在資源j并且在同一時間一些其他的任務例如i1也執行在同一資源上，Vijk和 Vi1jk一定等于1，所以第一個抑制因素將會拒絕，結果神經元Vijk是失敗執行，任務i在時間k不能執行在資源j。第二個抑制因素是不允許移動，任務i只能執行在資源j或資源j1在任何時間，如果任務i執行在兩個資源j和j1上，那么Vijk和Vij1k1必須等于1對于時間k1，因此第二個抑制因素將會拒絕，神經元是失敗執行。第三個抑制因素或第一個興奮因素是任務i在資源j上的時間花費應該等于Pij，Pij是任務i在資源j上的估計完成時間。實際上，如果ΣTk1=1Vijk1也就是任務i在資源j上總共花費的時間小于Pij，那么任務i必須在資源j上執行長一點的時間，所以神經元Vijk鼓勵執行；相反，如果總共時間長于Pij，神經元就失敗。相似于第一個抑制因素，第四個抑制因素是一個任務只能在某個時間執行在一個指定的資源上，但不像第一個，該抑制因素阻止神經元執行不管Vijk的狀態，如果Vijk的值是0，阻止是可以的。由于其他任務在時間k執行在資源j上，而在第一個抑制因素如果Vijk是0，沒有阻止發生。第五和六個抑制因素是不允許超過最終期限。首先考慮第五個抑制因素，如果時間k大于任務i(di)的最終期限，那么對于調度是不合適的時間，所以這個因素被拒絕。同樣的在第六個抑制因素，如果任務i在資源j上的執行時間Pij大于任務的最終期限，資源不允許調度并且神經元Vijk對所有的時間k阻止執行。

函數L、K和H的定義如下：

L（α）=1 if α＞0

0if α=0

-1if α＜0， K(α)=α if α≥0

0 if α＜0， H(α)=1 if α＞0

0 if α≤0(9)

在動作方程式中抑制系統的振動行為插入滯后因素，使匯聚時間變得相當短，針對McCulloch-Pitts的神經模型插入了滯后因素，給出了第i個神經元的輸入或輸出函數如下：

Vi=f(Ui)=1if Ui＞UTP

0if Ui＜LTP

unchangedotherwise(10)

這是一個改進的Maximum神經模型的形式，UTP和LTP分別表示上行點和下行點。Maximum神經模型能保證得到滿意的解決方法，由M個集群組成，每個集群包括了N個神經元^[8]。在改進的Maximum神經模型中“winner-take-all”函數是內含的，預示著在每個集群中的N個神經元有且只有一個最大值鼓勵執行，相應地給出了第M個集群中第i個神經元輸入或輸出函數如下：

Vmi=1 if Umi=max{Um1，…，Umn}and

Umi≥Umj for i＞j

0otherwise(11)

1.2.2 調度算法

根據以上數學神經模型，本文設計了如下算法：

begin

initialize Uijk randomly

while (a set of conflicts is not empty) do

begin

for i:=1 to N do

for j:=1 to M do

for k: =1 to T do

begin

Uijk =Uijk＋ΔUijk

Vijk =f(Uijk)

end

for i:=1 to N do

begin

find the maximum Uijk.

determine a segment (j) in which the maximum Uijk exists. If there is tie remove it randomly.

the output of the other segment′s neurons is set to zero.

end

end

end.

其中：i表示任務變量為1~N；j表示資源變量為1~M；k表示時間變量為1~T；U和V分別為神經元的輸入與輸出函數，Vijk相當于提出的神經網絡模型中的神經元。算法用了異步的方法來更新處理，當用N.M.T處理元素時，算法執行所需的時間復雜度接近O(1)，因此調度的需求時間是可以忽略不計的。

2 測試環境

使用GridSim工具模擬所提出的方法，執行調度算法在一個單一的機器上：Pentium 4處理器和512 MB 內存。改變GridSim一些類來提供支持對于緊急、非緊急和本地任務，重寫SpaceShared類，定義了一些新類，如ImpatientGridlet、Patient-Gridlet和LocalGridlet分別對應于緊急、非緊急和本地任務。在SpaceShared類檢查了在任務隊列中每個緊急任務的最終期限，如果已到期，那么它將從隊列移除。對于每個資源都有緊急的、非緊急的和本地任務來使用，這些任務基于它們的時間范圍和每天的時間狀態都有一個預先到達率。一個資源的所有節點是同一的，除了不同資源可以有不同的節點類型，每個資源有多個任務，每個任務有多個節點，每個節點服務率μ是預先確定的，根據資源歷史調度情況可以完成。考慮了不同的測試環境，如圖2所示。

每個高速主干網的帶寬在圖2中描述了，延遲設為10 ms，每個資源的使用平臺對于非緊急的、緊急的和本地任務根據泊松方法分別為λp、λi、λ1，這些任務有一個最終期限直到服務結束。

3 模擬實驗及分析

表1描繪了預測每個資源的任務響應時間，這些值輸入到調度算法；表2顯示了調度結果，調度算法的執行時間可以忽略不計（少于1 s）。比較了表1和2，再一次驗證了調度的正確性。

為了顯示帶寬在模型中的影響，改變了對于任務3的連接帶寬為0.000 1~2.0 GB。在表3中對于資源每個任務的響應時間是減少的，在表4中對于R#3有四個任務被調度而在表2中只有兩個任務被調度，說明了在網格環境中調度帶寬的重要性。

表5中顯示了全面的結果，在不同的例子中使用了不同的網絡技術、資源、任務及參數，每個例子重復了10次，調度算法總是匯聚于一點，從表中可以看到大約90%的例子對于調度任務是成功的。

4 結束語

在大多數分布式計算平臺，利用可用資源對于分布應用的調度進行高性能計算是必要的。基于隊列理論提出了一種實時應用的并行調度算法，實時應用包含了幾個獨立的任務，并且每個任務有一個最終期限直到服務結束，對每個任務在每個資源上響應時間預測的執行使用了資源的動態運用模型。在這個模型中，考慮了帶寬、延遲和通信背景的影響。本文提出的方法主要集中在最佳的解決方法與被給的最終期限，調度能夠執行在并行機構，算法執行的時間復雜度為O(1)，模擬實驗證明了提及的模型特別是對于大資源服務率的任務預測響應時間是正確和可行的。在這個工作中，假設非緊急的、緊急的和本地任務的到達率也就是節點的服務率對于每個資源是預先確定的，而在網格調度中是很難預測的，特別是對于新資源，下一個目標是證明假設任務的泊松到達，考慮新增的資源和資源失敗的問題。

參考文獻：

［1］FOSTER I，KESSELMAN C.The grid，blueprint for a new computing infrastructure[M].San Francisco:Morgan Kaufmann Publishers，2004.

[2]谷清范，吳介一.網格調度機制研究綜述[J].計算機應用研究，2006，23(5):1-4.

[3]FOSTER I，KESSELMAN C，TUECKE S.The anatomy of the grid:enabling scalable virtual organizations[J].International Journal on Supercomputer Applications，2001，15(3):200-220.

[4]BERMAN F.High-performance schedulers[C]//Proc of Chapter in the Grid:Blueprint for a Future Computing Infrastructure.San Francisco:Morgan Kaufmann Publishers，1998.

[5]HOPFIELD J J，TANK D W.Neural computation of decision in optimization[J].Journal of Biological Cybernetics，1985，52:141-152.

[6]CHANG C Y，JENG M D.Experimental study of a neural model for scheduling job shop[J].IEEE International Conference on System， Man and Cybernetics，1995，1:536-540.

[7]HUANG Y M，CHEN R M.Scheduling multiprocessor job with resources and timing constraints using neural networks[J].IEEE Trans on System， Man and Cybernetics，1999，29(4)：490-502.

[8]TAKEFUJI Y.Neural network parallel computing[M].Norwell:Kluwer Academic Publishers，1992.