計(jì)算網(wǎng)格資源管理優(yōu)化技術(shù)和相關(guān)算法的研究

一個(gè)作業(yè)由一個(gè)或多個(gè)任務(wù)組成。作業(yè)的拓?fù)涠x為一個(gè)滿足如下條件的有向無環(huán)圖:該圖的節(jié)點(diǎn)與作業(yè)中的任務(wù)一一對(duì)應(yīng);若任務(wù)B直接依賴于任務(wù)A,則存在一條由節(jié)點(diǎn)A到節(jié)點(diǎn)B的有向邊,稱A為B的直接前驅(qū),B為A的直接后繼;如果存在一條從A到B的由多條有向邊組成的有向通路,則稱A為B的前驅(qū),B為A的后繼。圖2表示一個(gè)作業(yè)的拓?fù)浣Y(jié)構(gòu)。設(shè)該作業(yè)由標(biāo)記為A～G的7個(gè)任務(wù)及其相互關(guān)系組成。如圖2所示,任務(wù)D需要在任務(wù)A和B完成后才能開始,而任務(wù)G必須在任務(wù)E和F完成后才能開始。

圖2 作業(yè)的拓?fù)浣Y(jié)構(gòu)

為了提高作業(yè)的并行執(zhí)行效率,需要關(guān)注任務(wù)在拓?fù)涠x中的深度。記任務(wù)T的直接前驅(qū)集合為Pd(T),則其深度d(T)為: 
    
2.2 作業(yè)的最大并行度劃分

作業(yè)的并行劃分是指:一個(gè)作業(yè)拆分后形成的一系列對(duì)應(yīng)每個(gè)任務(wù)、前后有序且相互獨(dú)立的任務(wù)組。一個(gè)作業(yè)可以有一個(gè)或多個(gè)并行劃分方案,形成該作業(yè)對(duì)應(yīng)的并行劃分集,記作Θ,I(Θ)為Θ中的任務(wù)組數(shù)。φ稱為作業(yè)的最大并行度劃分,如果:φ∈Θ,且∨ξ∈Θ。I(φ)≤I(ξ)將作業(yè)中的多個(gè)任務(wù)按照相應(yīng)的深度進(jìn)行劃分,形成一個(gè)最大并行度劃分。如圖2中的作業(yè),其最大并行度劃分為:φ={(A,B),(C,D,E),F,G}。

3 全局資源分配器

全局資源分配器接收到以RSL描述的任務(wù)組后,立刻進(jìn)行分析和解釋,獲得每個(gè)任務(wù)的靜態(tài)資源需求。系統(tǒng)根據(jù)每個(gè)任務(wù)的資源需求在靜態(tài)資源庫中搜索滿足條件的多個(gè)集群,并將結(jié)果提交給局部資源分配器。

3.1靜態(tài)資源庫

系統(tǒng)中的靜態(tài)資源庫采用基于輕量目錄訪問協(xié)議LDAP結(jié)構(gòu)。在HRMM模型中,網(wǎng)格系統(tǒng)的所有靜態(tài)資源都在LDAP服務(wù)器的DIT(目錄信息樹)中建立了相應(yīng)的目錄項(xiàng),并用<屬性,值>的組合描述各種資源屬性。靜態(tài)資源庫選擇LDAP可以在性能上帶來以下優(yōu)點(diǎn):
(1) LDAP專門對(duì)讀操作進(jìn)行了優(yōu)化,在讀操作頻繁的情況下,可以提高讀取效率。
(2) LDAP是跨平臺(tái)協(xié)議,可在任何計(jì)算機(jī)上使用。從而增加系統(tǒng)對(duì)異構(gòu)網(wǎng)格環(huán)境的適應(yīng)性。
(3) LDAP服務(wù)器支持分布式的結(jié)構(gòu),靜態(tài)資源庫可訪問本地或全局的LDAP服務(wù)器,并能很方便地實(shí)現(xiàn)同步,即增強(qiáng)資源管理的分布性。

3.2 全局資源分配算法

根據(jù)任務(wù)組中每個(gè)任務(wù)的靜態(tài)需求,全局資源分配器在靜態(tài)資源庫中搜索滿足需求的集群。在搜索時(shí)首先隨機(jī)選擇搜索的起始位置,然后為每個(gè)任務(wù)分別返回最先發(fā)現(xiàn)的N個(gè)滿足該任務(wù)需求的集群,形成候選集群組,并以ClusterList數(shù)據(jù)結(jié)構(gòu)描述后提交給局部資源分配器;其中ClusterList是用來描述候選集群組的廣義表結(jié)構(gòu),如圖3所示。對(duì)于任何一個(gè)任務(wù),如果只找到K(＜N)個(gè)符合條件的集群,則只由這K個(gè)組成候選集群組;如果任何一個(gè)集群都不滿足任務(wù)的靜態(tài)需求,則向局部資源分配器提交空值,同時(shí)向作業(yè)并行分析器發(fā)送反饋信息,取消任務(wù)。設(shè)LDAP服務(wù)器所記錄的集群數(shù)量為M,則全局資源分配的計(jì)算復(fù)雜度為O(MN)。

圖3 候選集群組的廣義表數(shù)據(jù)結(jié)構(gòu)——ClusterList

4 局部資源分配器

局部資源分配器在動(dòng)態(tài)資源庫中搜索候選集群組的動(dòng)態(tài)信息,將這些動(dòng)態(tài)信息和從全局資源分配器獲得的靜態(tài)信息相組合并進(jìn)行綜合分析,最終將任務(wù)組中的每個(gè)任務(wù)分配給最適合的集群。

4.1動(dòng)態(tài)資源庫

動(dòng)態(tài)資源庫中的數(shù)據(jù)以XML描述,帶來如下優(yōu)點(diǎn):
(1) XML針對(duì)更新操作進(jìn)行了優(yōu)化。因此,對(duì)于需要不斷更新的動(dòng)態(tài)資源庫,可有效提高效率。
(2) XML和LDAP在存儲(chǔ)結(jié)構(gòu)上都是樹狀結(jié)構(gòu),可以很方便地相互轉(zhuǎn)化。用XML描述數(shù)據(jù),可使動(dòng)態(tài)資源庫和基于LDAP的靜態(tài)資源庫具有更好的耦合性。
(3) XML與平臺(tái)無關(guān),以XML表示的數(shù)據(jù)可很方便地被其他程序使用。

4.2 局部資源分配策略

局部資源分配器得到候選集群組ClusterList后,從動(dòng)態(tài)資源庫獲取每個(gè)候選集群的動(dòng)態(tài)信息,并將這些動(dòng)態(tài)信息添加到相應(yīng)集群的靜態(tài)信息之后,然后將靜態(tài)資源和動(dòng)態(tài)資源信息相組合,形成集群綜合資源信息。設(shè)一個(gè)集群的動(dòng)態(tài)資源信息為 h=[h1,…,hm]T,靜態(tài)資源信息為t=[t1,…, td]T,其中m和d分別為動(dòng)態(tài)和靜態(tài)資源描述的字段數(shù),則集群綜合信息為v=[tT hT]T =[v1,…,vp]T,其中p=m+d。如圖3所示,集群2,2的綜合信息表示為v2,2。類似地,將任務(wù)靜態(tài)資源需求和動(dòng)態(tài)資源組合,設(shè)一個(gè)任務(wù)的動(dòng)態(tài)資源需求為g=[g1,…,gm]T,靜態(tài)資源需求為s=[s1,…,sd]T,則綜合資源需求為r=[sT gT]T=[r1,…,rp]T。任務(wù)i的綜合資源需求表示為ri。在確定分配策略時(shí),將只考慮任務(wù)的綜合資源需求和集群的綜合資源信息。

首先,為了任務(wù)能夠順利完成,最終被選擇的集群必須同時(shí)滿足任務(wù)的靜態(tài)資源需求和動(dòng)態(tài)資源需求,即滿足任務(wù)的綜合資源需求:
    
其中,n為任務(wù)組中的任務(wù)數(shù)量,p為向量v和r的維數(shù),f(i)為任務(wù)i的候選集群(即ClusterList中Taski對(duì)應(yīng)的集群鏈表)中最終被選擇集群的序號(hào)。因此,首先在ClusterList中刪除所有不滿足上述條件的集群,并記第i個(gè)任務(wù)還剩余Ki個(gè)符合綜合資源需求的候選集群,其中1≤i≤n,1≤Ki≤N。最后,局部資源分配器要為每個(gè)任務(wù)Taski從Ki個(gè)候選集群中選擇最合適的一個(gè)。綜合考慮計(jì)算網(wǎng)格的整體資源分配效率,在具體選擇集群時(shí)采用如下決策機(jī)制:
(1) 獲選集群的綜合資源信息應(yīng)盡量接近相應(yīng)任務(wù)的綜合資源需求,避免資源的浪費(fèi),即:
　　
(2) 獲選集群和任務(wù)提交節(jié)點(diǎn)間的總網(wǎng)絡(luò)延遲應(yīng)盡量小,即:
　　
其中tj為全局標(biāo)識(shí)為j的集群的延遲;
(3) HRMM為每個(gè)用戶規(guī)定了計(jì)算資源占用量的上限,即:
　　
其中W為該用戶對(duì)計(jì)算資源占用量的上限,且W>0。
綜合考慮上述三方面,局部資源分配可以描述為如下二次規(guī)劃問題:
　　
其中C是可以改變的加權(quán)系數(shù),且C>0。由于f(i)為離散值且取值范圍有限,因此提出以下優(yōu)化方法,通過較少的計(jì)算來搜索近似的最優(yōu)解。記候選集群組為ClusterList,則算法表示如下:
STEP 1. 對(duì)每個(gè)任務(wù)和候選集群,將靜態(tài)和動(dòng)態(tài)資源信息組合為綜合資源信息;
STEP 2. 刪除ClusterList中不滿足總和資源需求的集群;
STEP 3. ∨i∈[1,n],∨j∈[1,Ki],計(jì)算每個(gè)集群i,j的局部損失Cost[i,j]:=‖vi,j-ri‖2+C