邱 昕，趙俊杰，林 琳

（營口職業(yè)技術(shù)學(xué)院 遼寧 營口 115000）

0 引言

目前，網(wǎng)格技術(shù)在基礎(chǔ)研究、制造業(yè)、工業(yè)等諸多領(lǐng)域，發(fā)揮了空前的作用。網(wǎng)格環(huán)境具有資源規(guī)模龐大的特點，在資源查找上所耗費的大量時間，對于調(diào)度是一大難題，因此對資源進行聚類預(yù)處理的方式，不但可以提高資源的定位效率，而且可以節(jié)省調(diào)度時間。

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

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

1 任務(wù)模型

建立任務(wù)模型，在任務(wù)模型中描述了任務(wù)節(jié)點，任務(wù)均為計算任務(wù)，且都是元任務(wù)，即任務(wù)之間沒有相互依賴關(guān)系，可以獨立執(zhí)行。任務(wù)描述如下：

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

（1）rID表示任務(wù)的ID標(biāo)識。

（2）rCa是任務(wù)計算量。

（3）rS是任務(wù)的狀態(tài)，表示方法見表1。

表1 任務(wù)的狀態(tài)表示方法

任務(wù)調(diào)度的過程中，任務(wù)起初是空閑狀態(tài)，儲存在未調(diào)度集合T中，然后與資源進行匹配，匹配成功后傳輸?shù)劫Y源節(jié)點上，在等待列隊中等待執(zhí)行，待任務(wù)執(zhí)行完畢后，任務(wù)的狀態(tài)為完畢。

2 資源超圖模型

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

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

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

①ID為資源的ID標(biāo)識。

②P為資源的處理能力。

③C為資源通信的能力。

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

其中，r1、r2是權(quán)重系數(shù)，Pi是資源vi的處理能力，Ci是資源vi的通信能力。

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

有效資源狀態(tài)是指此時資源可以接受任務(wù)，無效資源狀態(tài)是指此時資源不可以接受任務(wù)。資源的狀態(tài)由接受和拒絕閾值來控制，這樣做的目的是為了均衡資源節(jié)點的負(fù)載問題[3]。當(dāng)資源節(jié)點負(fù)載值大于拒絕閾值θa時，資源為無效資源，直到資源的負(fù)載值小于接受閾值θr時，資源才可以變?yōu)橛行顟B(tài)。

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

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

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

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

3 資源聚類

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

3.1 目標(biāo)函數(shù)

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

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

類內(nèi)距離：

類間距離：

聚類內(nèi)節(jié)點個數(shù)的方差：

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

為了共同達到以上3個目標(biāo)，還需將多目標(biāo)轉(zhuǎn)化為單目標(biāo)并作為遺傳算法聚類的評價函數(shù)：

在多目標(biāo)聚類中，類內(nèi)距離f1表示類內(nèi)節(jié)點的性能距離，我們希望將性能值接近的節(jié)點放在一個聚類內(nèi)，因此類內(nèi)距離f1越小越好。類間距離f2表示類與類之間的性能值差異，因此類間距離f2越大越好。聚類內(nèi)節(jié)點個數(shù)的方差f3表示類內(nèi)節(jié)點的數(shù)量均衡程度，希望各個類內(nèi)的節(jié)點數(shù)量均衡，方差表示均衡的差異性，因此聚類內(nèi)節(jié)點個數(shù)的方差f3越小越好，綜上所述，多目標(biāo)轉(zhuǎn)化為但目標(biāo)之后，評價函數(shù)f的值應(yīng)該越小越好。

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

3.2 遺傳算法聚類

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

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

4 調(diào)度策略

針對大規(guī)模網(wǎng)格計算，先將資源節(jié)點進行聚類，聚類后各個聚類中心形成頂層超樹。調(diào)度時，在超樹中尋找有有效資源的綜合性能值高的節(jié)點，然后在此節(jié)點所在聚類中尋找負(fù)載低的資源進行調(diào)度。

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

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

Makespan為任務(wù)的最優(yōu)跨度，即任務(wù)的最大完成時間，見式（11）。

資源聚類在調(diào)度前只需執(zhí)行一次，因此資源聚類預(yù)處理可以有效減少資源查找時間，從而減少調(diào)度時間，而且給資源設(shè)定負(fù)載閾值，還可以有效均衡資源負(fù)載。

5 仿真分析

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

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

6 結(jié)語

本文設(shè)計的一種多目標(biāo)最優(yōu)資源聚類網(wǎng)格調(diào)度方法MORC，針對元任務(wù)調(diào)度，資源首先進行多目標(biāo)最優(yōu)預(yù)先聚類，在此前提下設(shè)計了一種以最小調(diào)度時間為主要目標(biāo)，并兼顧負(fù)載均衡的網(wǎng)格任務(wù)調(diào)度算法，在調(diào)度時間、資源利用率、負(fù)載均衡方面均有較大提高。