一種多目標最優資源聚類的網格調度算法

邱 昕，趙俊杰，林 琳

（營口職業技術學院 遼寧 營口 115000）

0 引言

目前，網格技術在基礎研究、制造業、工業等諸多領域，發揮了空前的作用。網格環境具有資源規模龐大的特點，在資源查找上所耗費的大量時間，對于調度是一大難題，因此對資源進行聚類預處理的方式，不但可以提高資源的定位效率，而且可以節省調度時間。

在構建模型方面，有文獻提出用超圖構建模型，這樣可在問題描述方面提供很多便利，有利于實際問題的解決。超圖（Hypergraph）是二元對H=(V,E)，其中V={v1,v2,...,vn}表示超圖的n個頂點，E={e1,e2,...em}表示超圖的m條超邊，超圖的圖形表示[1-2]，見圖1。

本文結合超圖理論，提出了一種資源聚類算法MORC，該方法主要針對大規模任務調度，并且在資源規模龐大的情況下，能夠快速有效地進行調度。首先運用超圖理論，構建了資源超圖模型，很好地描述了資源整合的能力，這對資源聚類、調度時間都有直接的影響；進而運用遺傳算法對資源進行聚類預處理，追求類內距離小，類間距離大，并且類內節點數量均衡的多目標優化轉單目標優化，能夠充分結合網格資源的特點，自適應的尋優完成聚類；在負載均衡方面，設置閾值來控制資源的可用性；調度時，以最小化完成時間為目標。該方法與經典算法Min-min算法相比，縮短了任務與資源相匹配的時間，從而縮短了整個調度時間，并且在資源負載均衡方面有了很大提高。

1 任務模型

建立任務模型，在任務模型中描述了任務節點，任務均為計算任務，且都是元任務，即任務之間沒有相互依賴關系，可以獨立執行。任務描述如下：

任務描述：RV=｛rv1，rv2，……，rvrn｝是任務節點的集合，其中，rvi=｛rID，rCa，rS｝是任務的屬性的集合，其中i∈[1，rn]。

（1）rID表示任務的ID標識。

（2）rCa是任務計算量。

（3）rS是任務的狀態，表示方法見表1。

表1 任務的狀態表示方法

任務調度的過程中，任務起初是空閑狀態，儲存在未調度集合T中，然后與資源進行匹配，匹配成功后傳輸到資源節點上，在等待列隊中等待執行，待任務執行完畢后，任務的狀態為完畢。

2 資源超圖模型

利用超圖理論構建資源超圖模型，超圖由資源節點和超邊組成，資源節點是一個六元組，即資源ID、資源處理和通信能力、綜合性能值、資源狀態和負載[2]。資源描述如下：

H=（X，E）是資源模型的超圖表示。

（1）X=｛v1，v2，……，vn｝是資源節點的集合，其中vi=｛ID，P，C，PC，S，Load｝是資源節點的屬性集合，i∈ [1，n]。

①ID為資源的ID標識。

②P為資源的處理能力。

③C為資源通信的能力。

④PC是資源的綜合性能值，由資源的處理能力和通信能力組成。考慮到處理能力與通信能力差值過大問題，采用歸一化的方法得到綜合性能值公式如下：

其中，r1、r2是權重系數，Pi是資源vi的處理能力，Ci是資源vi的通信能力。

⑤S是資源的狀態，包括有效資源狀態valid和無效資源狀態invalid。表示方法如下，S=｛valid，invalid｝

有效資源狀態是指此時資源可以接受任務，無效資源狀態是指此時資源不可以接受任務。資源的狀態由接受和拒絕閾值來控制，這樣做的目的是為了均衡資源節點的負載問題[3]。當資源節點負載值大于拒絕閾值θa時，資源為無效資源，直到資源的負載值小于接受閾值θr時，資源才可以變為有效狀態。

⑥Load表示資源的負載，等待列隊中任務計算量和已匹配且未進入等待列隊的任務計算量的和稱為資源負載，公式表示如下：

其中，Loadk是資源k的負載，Rwaitk是資源k上等待集合中任務的計算量總和，Rmatchk是已經與資源k匹配，但是還未傳到資源上的任務的計算量總和。

（2）E=｛e1，e2，……，em｝是超邊集合，m=|E|是超邊數，超邊ej的權值Wj是該超邊所包含的資源節點的平均性能值。

其中，PCi是vi的綜合性能值，|ej|是超邊ej內所包含資源節點的數量。資源聚類后，質心代表聚類的情況，因此質心的綜合性能值就是Wj，|ej|是聚類中資源節點的個數，即聚類內節點的平均綜合性能值。

3 資源聚類

對網格資源采用遺傳算法進行聚類預處理，可以將資源很好地進行分類，節省任務與資源的匹配時間。本文用多目標轉化為單目標的方式，采用遺傳算法對資源進行聚類預處理，通過資源節點間的相似程度進行聚類，減少了調度過程中選擇資源所花費的時間，從而提高調度的效率[4]。首先根據資源節點的相似程度，構建3個目標：類內距離、類間距離、類內節點個數方差，追求類內距離小，類間距離大，類內節點個數均衡，將三目標轉為單目標函數，并作為遺傳算法的評價函數，然后用遺傳算法對資源節點進行聚類。

3.1 目標函數

網格資源聚類是將多個目標轉化為單一目標函數的方式進行聚類。以類內距離和類間距離為指標，距離是指任意兩個資源節點的性能距離，即兩節點間性能距離越小，說明兩節點綜合性能值越相似。類內距離應該最小化，以確保聚類結果的密度，這樣可以保證質心傾向密度區域。類間距離是質心節點間的平均距離，應該最大化使質心盡量分布均勻。同時，為了保證各類內節點數量均衡，引入了節點個數的方差公式，使之最小化，以保證節點數量均衡。以這3個目標為基準，最終轉化為一個目標函數，再用遺傳算法進行聚類。

資源節點之間的相似程度由性能距離來定義：

類內距離：

類間距離：

聚類內節點個數的方差：

其中，m為聚類數，n為節點數，hi：第i個聚類的中心結點，Di：節點i所在的聚類，xi是第i個聚類內節點個數，是平均值。

為了共同達到以上3個目標，還需將多目標轉化為單目標并作為遺傳算法聚類的評價函數：

在多目標聚類中，類內距離f1表示類內節點的性能距離，我們希望將性能值接近的節點放在一個聚類內，因此類內距離f1越小越好。類間距離f2表示類與類之間的性能值差異，因此類間距離f2越大越好。聚類內節點個數的方差f3表示類內節點的數量均衡程度，希望各個類內的節點數量均衡，方差表示均衡的差異性，因此聚類內節點個數的方差f3越小越好，綜上所述，多目標轉化為但目標之后，評價函數f的值應該越小越好。

資源聚類結合超圖理論，就是比較資源超圖中的各超邊的權值，即綜合性能值，應用遺傳算法，將權值相近的超邊進行合并，權值相差較大的超邊進行分解，經過不斷的超邊合并分解，最終形成資源聚類超圖。追求類內距離小，類間距離大，即超邊內節點性能距離小，各超邊權值性能距離較大，且各聚類內節點個數均衡。

3.2 遺傳算法聚類

遺傳算法聚類以資源節點ID編碼，交叉時，為了避免實數編碼產生后代的不合法性，采用部分映射交叉（PMX）。變異時，變異位的取值范圍不包含其基因中其他位，即染色體X=（x1，x2，…，xn），變異位為xk（1≤k≤n），變異范圍U=[1,N]，N為資源ID，且｛x1，x2，…，xk-1，xk+1，…,xn｝?U。選擇時，采用輪盤賭的方式，輪盤賭公式見式（9），采用父代子代一起選的方式。不斷循環，直至染色體收斂。

經過遺傳算法聚類后見圖2，每個類稱為超邊，類內節點即為超邊內節點，類心的綜合性能值代表其所在超邊內所有節點綜合性能值的均值，類心還能顯示其所在超邊內是否有有效資源，所有類心形成另一條超邊，即上層超邊，稱為超樹。調度時，首先檢索超樹內的節點，再檢索該類心所在超邊的節點。

4 調度策略

針對大規模網格計算，先將資源節點進行聚類，聚類后各個聚類中心形成頂層超樹。調度時，在超樹中尋找有有效資源的綜合性能值高的節點，然后在此節點所在聚類中尋找負載低的資源進行調度。

任務預計完成時間（ACT）包括傳輸時間、等待時間和執行時間三者之和。任務傳到資源的時間（TM）是任務計算量與資源的通信能力的比值。等待時間（WT）是任務總計算量與資源處理能力的比值，這里的任務包括等待列隊中的任務和已經與資源匹配但是還未傳到資源上的任務[5]。任務的執行時間（ET）是任務計算量與資源處理能力之比。

因此，任務rvi在資源vj上的預計完成時間，見式（10）。

Makespan為任務的最優跨度，即任務的最大完成時間，見式（11）。

資源聚類在調度前只需執行一次，因此資源聚類預處理可以有效減少資源查找時間，從而減少調度時間，而且給資源設定負載閾值，還可以有效均衡資源負載。

5 仿真分析

假設當資源數為1 000時，聚類數為100時，在任務數不同的情況下，對比MORC算法和Min-min算法的makespan、runtime、加速度Speedup和資源利用率P，見圖3。

由圖3（a）可以看出任務數在3 000以內時，隨著任務數的增加，MORC算法和Min-min算法的makespan都在不斷增加，但是可以明顯看出兩種算法的makespan前者小于后者。由圖3（b）可以看出runtime隨著任務數的增加而增加，但MORC算法的整體runtime都要小于Min-min算法。圖3（c）是任務數不同時，加速度Speedup的比較，Speedup是體現調度算法性能優劣的重要指標，表示串行執行時間與并行執行時間的比，并行執行時間越小則加速度Speedup越大，因此可以明顯看出MORC算法的調度性能較好。圖3（d）是資源利用率的比較結果，資源利用率是資源利用程度的性能指標，資源利用率越接近于1，表明資源的利用程度越廣，由圖可知MORC算法在資源利用程度上較優。經過以上4個圖的詳細分析，不論從任務最大完成時間makespan、調度時間runtime、算法加速度Speedup和資源利用率P這4個方面中的哪個方面來看，本文所設計的多目標最優資源聚類的網格調度算法MORC在各方面都要優越于Min-min算法。

6 結語

本文設計的一種多目標最優資源聚類網格調度方法MORC，針對元任務調度，資源首先進行多目標最優預先聚類，在此前提下設計了一種以最小調度時間為主要目標，并兼顧負載均衡的網格任務調度算法，在調度時間、資源利用率、負載均衡方面均有較大提高。