??? 摘 要: 在對現(xiàn)有的網(wǎng)格資源管理" title="資源管理">資源管理模型進(jìn)行分析和比較的基礎(chǔ)上,提出了一種基于分層結(jié)構(gòu)的具體模型HRMM,將資源管理分為作業(yè)并行分析、全局資源分配" title="資源分配">資源分配、局部資源分配和本地資源管理四個層次,并為每個層次設(shè)計了相應(yīng)的優(yōu)化策略和算法。該模型對資源管理的最大" title="最大">最大計算復(fù)雜度為O(n2)~O(n3),是一個優(yōu)化而有效的網(wǎng)格資源管理模型。
??? 關(guān)鍵詞: 計算網(wǎng)格? 資源管理? 資源分配? 作業(yè)? 資源調(diào)度? Globus Toolkit
?
??? 計算網(wǎng)格是近年興起的一種重要的并行分布式計算技術(shù),其關(guān)鍵技術(shù)之一是對網(wǎng)格中的資源進(jìn)行管理。網(wǎng)格中的資源具有廣域分布、異構(gòu)和動態(tài)的特性,使得網(wǎng)格資源管理變得很復(fù)雜。當(dāng)前還沒有一種模型能夠處理所有的網(wǎng)格應(yīng)用需求。目前,網(wǎng)格資源管理模型主要分為分層模型、抽象所有者模型和經(jīng)濟(jì)/市場模型三類。Globus項目組在網(wǎng)格協(xié)議制定上有重要發(fā)言權(quán),包括IBM、Microsoft、Sun、Compaq、SGI、NEC在內(nèi)的眾多重要公司都宣布支持Globus Toolkit。因此Globus所采用的分層模型代表了網(wǎng)格資源管理的發(fā)展趨勢。
??? 本文在Globus分層模型設(shè)計思想的基礎(chǔ)上提出一種優(yōu)化的網(wǎng)格資源管理模型HRMM(Hierarchical Resource Management Model),并給出了相應(yīng)的資源管理算法。為了提高效率,在HRMM的主要模塊中運用了Globus Toolkit 2.4提供的數(shù)據(jù)結(jié)構(gòu)和接口。
1 HRMM的總體結(jié)構(gòu)
??? HRMM的設(shè)計思想是:動態(tài)接收來自用戶的作業(yè)請求,并為該作業(yè)分配符合條件的計算資源,同時提供整個計算過程中有關(guān)資源信息的在線反饋,接受用戶的在線控制。HRMM的體系結(jié)構(gòu)如圖1所示,將計算網(wǎng)格的資源管理任務(wù)分為四個層次:作業(yè)并行分析、全局資源分配、局部資源分配和本地資源管理。
?
???? 由圖1可見,用戶經(jīng)過GUI(圖形用戶界面)向HRMM提交作業(yè)請求,作業(yè)并行分析器接收用戶的作業(yè)請求,再按最大并行度將作業(yè)中的任務(wù)劃分為若干任務(wù)組,提交給全局資源分配器。對多任務(wù)組中的每個任務(wù),全局資源分配器在靜態(tài)資源庫中一次搜索多個滿足該需求的集群,組成候選集群組提交給局部資源分配器。局部資源分配器在動態(tài)資源庫中讀取候選集群組中每個集群的有關(guān)信息,并將相應(yīng)任務(wù)分配給最符合條件的集群。然后,該集群應(yīng)用本地資源管理器執(zhí)行任務(wù)。在整體上,本地資源管理器每隔一定時間向靜態(tài)資源庫發(fā)送靜態(tài)資源更新信息。另外,局部資源分配器讀取動態(tài)資源庫前,動態(tài)資源庫會從本地資源管理器讀取更新信息。
??? 在這個分層模型中,一方面,用戶提交的作業(yè)能夠以最大的并行度執(zhí)行,從而高效體現(xiàn)了并行計算的思想;另一方面,選多個集群組成候選集群組,再確定其中某一分配資源的方案,由于綜合考慮了任務(wù)的靜態(tài)需求和動態(tài)需求,避免重復(fù)的查詢操作,從而提高了資源分配的效率。
2? 作業(yè)并行分析器
??? 如圖1所示,用戶經(jīng)過GUI向作業(yè)并行分析器提交作業(yè)請求。這個請求包括該作業(yè)中所含的多" title="的多">的多個任務(wù)的相關(guān)信息、任務(wù)間的依賴關(guān)系及每個任務(wù)的計算資源需求。作業(yè)并行分析器分析該作業(yè)中的任務(wù)及相互關(guān)系,根據(jù)各任務(wù)的依賴關(guān)系將作業(yè)中的任務(wù)劃分為不同的任務(wù)組,并對每個任務(wù)組進(jìn)行適當(dāng)描述后提交給全局資源分配器。
2.1 作業(yè)的拓?fù)浔硎?/FONT>
?? ?一個作業(yè)由一個或多個任務(wù)組成。作業(yè)的拓?fù)涠x為一個滿足如下條件的有向無環(huán)圖:該圖的節(jié)點與作業(yè)中的任務(wù)一一對應(yīng);若任務(wù)B直接依賴于任務(wù)A,則存在一條由節(jié)點A到節(jié)點B的有向邊,稱A為B的直接前驅(qū),B為A的直接后繼;如果存在一條從A到B的由多條有向邊組成的有向通路,則稱A為B的前驅(qū),B為A的后繼。
??? 圖2表示一個作業(yè)的拓?fù)浣Y(jié)構(gòu)。設(shè)該作業(yè)由標(biāo)記為A~G的7個任務(wù)及其相互關(guān)系組成。如圖2所示,任務(wù)D需要在任務(wù)A和B完成后才能開始,而任務(wù)G必須在任務(wù)E和F完成后才能開始。
?
??? 為了提高作業(yè)的并行執(zhí)行效率,需要關(guān)注任務(wù)在拓?fù)涠x中的深度。記任務(wù)T的直接前驅(qū)集合為Pd(T),則其深度d(T)為:
???
2.2? 作業(yè)的最大并行度劃分
??? 作業(yè)的并行劃分是指:一個作業(yè)拆分后形成的一系列對應(yīng)每個任務(wù)、前后有序且相互獨立的任務(wù)組。一個作業(yè)可以有一個或多個并行劃分方案,形成該作業(yè)對應(yīng)的并行劃分集,稱為作業(yè)的最大并行度劃分,將作業(yè)中的多個任務(wù)按照相應(yīng)的深度進(jìn)行劃分,形成一個最大并行度劃分。如圖2中的作業(yè),其最大并行度劃分為:
3 全局資源分配器 ? ??? 其中,n為任務(wù)組中的任務(wù)數(shù)量,p為向量v和r的維數(shù),f(i)為任務(wù)i的候選集群(即ClusterList中Taski對應(yīng)的集群鏈表" title="鏈表">鏈表)中最終被選擇集群的序號。因此,首先在ClusterList中刪除所有不滿足上述條件的集群,并記第i個任務(wù)還剩余Ki個符合綜合資源需求的候選集群,其中1≤i≤n,1≤Ki≤N。最后,局部資源分配器要為每個任務(wù)Taski從Ki個候選集群中選擇最合適的一個。綜合考慮計算網(wǎng)格的整體資源分配效率,在具體選擇集群時采用如下決策機(jī)制: ??? 其中C是可以改變的加權(quán)系數(shù),且C>0。由于f(i)為離散值且取值范圍有限,因此提出以下優(yōu)化方法,通過較少的計算來搜索近似的最優(yōu)解。記候選集群組為ClusterList,則算法表示如下: ??? STEP 4. 并行地對Cost的每一列排序,并按從小到大的次序重排ClusterList中的集群鏈表; ??? 該算法為資源分配查找到了近似的最優(yōu)解,并在最大程度上利用了資源管理站點所在集群的計算資源,將大部分計算并行化。設(shè)資源管理站點所在集群的節(jié)點數(shù)為P,則該算法在每個節(jié)點上的計算復(fù)雜度為O(n2N/P)
??? 全局資源分配器接收到以RSL描述的任務(wù)組后,立刻進(jìn)行分析和解釋,獲得每個任務(wù)的靜態(tài)資源需求。系統(tǒng)根據(jù)每個任務(wù)的資源需求在靜態(tài)資源庫中搜索滿足條件的多個集群,并將結(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)的目錄項,并用<屬性,值>的組合描述各種資源屬性。靜態(tài)資源庫選擇LDAP可以在性能上帶來以下優(yōu)點:
??? (1) LDAP專門對讀操作進(jìn)行了優(yōu)化,在讀操作頻繁的情況下,可以提高讀取效率。
??? (2) LDAP是跨平臺協(xié)議,可在任何計算機(jī)上使用。從而增加系統(tǒng)對異構(gòu)網(wǎng)格環(huán)境的適應(yīng)性。
??? (3) LDAP服務(wù)器支持分布式的結(jié)構(gòu),靜態(tài)資源庫可訪問本地或全局的LDAP服務(wù)器,并能很方便地實現(xiàn)同步,即增強資源管理的分布性。
3.2 全局資源分配算法
?? ?根據(jù)任務(wù)組中每個任務(wù)的靜態(tài)需求,全局資源分配器在靜態(tài)資源庫中搜索滿足需求的集群。在搜索時首先隨機(jī)選擇搜索的起始位置,然后為每個任務(wù)分別返回最先發(fā)現(xiàn)的N個滿足該任務(wù)需求的集群,形成候選集群組,并以ClusterList數(shù)據(jù)結(jié)構(gòu)描述后提交給局部資源分配器;其中ClusterList是用來描述候選集群組的廣義表結(jié)構(gòu),如圖3所示。對于任何一個任務(wù),如果只找到K(
4 局部資源分配器
??? 局部資源分配器在動態(tài)資源庫中搜索候選集群組的動態(tài)信息,將這些動態(tài)信息和從全局資源分配器獲得的靜態(tài)信息相組合并進(jìn)行綜合分析,最終將任務(wù)組中的每個任務(wù)分配給最適合的集群。
4.1 動態(tài)資源庫
?? ?動態(tài)資源庫中的數(shù)據(jù)以XML描述,帶來如下優(yōu)點:
??? (1) XML針對更新操作進(jìn)行了優(yōu)化。因此,對于需要不斷更新的動態(tài)資源庫,可有效提高效率。
??? (2) XML和LDAP在存儲結(jié)構(gòu)上都是樹狀結(jié)構(gòu),可以很方便地相互轉(zhuǎn)化。用XML描述數(shù)據(jù),可使動態(tài)資源庫和基于LDAP的靜態(tài)資源庫具有更好的耦合性。
??? (3) XML與平臺無關(guān),以XML表示的數(shù)據(jù)可很方便地被其他程序使用。
4.2 局部資源分配策略
??? 局部資源分配器得到候選集群組ClusterList后,從動態(tài)資源庫獲取每個候選集群的動態(tài)信息,并將這些動態(tài)信息添加到相應(yīng)集群的靜態(tài)信息之后,然后將靜態(tài)資源和動態(tài)資源信息相組合,形成集群綜合資源信息。設(shè)一個集群的動態(tài)資源信息為h=[h1,…,hm]T,靜態(tài)資源信息為t=[t1,…, td]T,其中m和d分別為動態(tài)和靜態(tài)資源描述的字段數(shù),則集群綜合信息為v=[tT hT]T =[v1,…, vp]T,其中p=m+d。如圖3所示,集群2,2的綜合信息表示為v2,2。類似地,將任務(wù)靜態(tài)資源需求和動態(tài)資源組合,設(shè)一個任務(wù)的動態(tài)資源需求為g=[g1,…,gm]T,靜態(tài)資源需求為s=[s1,…,sd]T,則綜合資源需求為r=[sT gT]T=[r1,…,rp]T。任務(wù)i的綜合資源需求表示為ri。在確定分配策略時,將只考慮任務(wù)的綜合資源需求和集群的綜合資源信息。
??? 首先,為了任務(wù)能夠順利完成,最終被選擇的集群必須同時滿足任務(wù)的靜態(tài)資源需求和動態(tài)資源需求,即滿足任務(wù)的綜合資源需求:
???
??? (1) 獲選集群的綜合資源信息應(yīng)盡量接近相應(yīng)任務(wù)的綜合資源需求,避免資源的浪費,即:
??? STEP 1. 對每個任務(wù)和候選集群,將靜態(tài)和動態(tài)資源信息組合為綜合資源信息;
????STEP 2. 刪除ClusterList中不滿足總和資源需求的集群;
??? STEP 5. 則報告不存在滿足條件的解,算法結(jié)束;
5 分析與總結(jié)
??? 本課題組采用基于分層模型的結(jié)構(gòu),將資源管理分為四個層次,然后在每個層次對模型的性能做出優(yōu)化并提出了相應(yīng)的算法。從總體上,HRMM對一個作業(yè)進(jìn)行資源管理的最大計算復(fù)雜度不超過O(n3),是一個優(yōu)化而有效的網(wǎng)格系統(tǒng)資源管理模型。
參考文獻(xiàn)
1 K. Czajkowski, I. Foster, N. Karonis, C. Kesselman. A resource managementarchitecture for metacomputing systems[C]. Proceedings of the 4th Workshop on Job Scheduling?Strategies for Parallel Processing, 1998.
2 Kurowski.K, Nabrzyski.J, Pukacki.J. User preference driven?multiobjective resource management in grid environments [C].Proceedings First IEEE/ACM International Symposium,15~18?May 2001.
3 Peng Liu, Yao Shi, San-li Li. Computing Pool--a Simpli-fied and Practical Computational Grid Model[C].The Second?International Workshop on Grid and Cooperative Computing(GCC 2003), 2003;(12):7~10
4 I. Foster, C. Kesselman, S. Tuecke. The Anatomy of the?Grid: Enabling Scalable Virtual Organizations[J].International?J. Supercomputer Applications, 2001;15(3)