一種多目標(biāo)最優(yōu)資源聚類的網(wǎng)格調(diào)度算法

邱 昕，趙俊杰，林 琳

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

0 引言

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

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

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

1 任務(wù)模型

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

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

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

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

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

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

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

2 資源超圖模型

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

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

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

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

②P為資源的處理能力。

③C為資源通信的能力。

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

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

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

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

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

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

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

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

3 資源聚類

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

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

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

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

類內(nèi)距離：

類間距離：

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

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

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

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

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

3.2 遺傳算法聚類

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

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

4 調(diào)度策略

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

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

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

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

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

5 仿真分析

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

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

6 結(jié)語(yǔ)

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