計算網格資源管理優(yōu)化技術和相關算法研究

1、    摘要：在對現有的網格資源管理模型進行分析和比較的基礎上，提出了一種基于分層結構的具體模型HRMM，將資源管理分為作業(yè)并行分析、全局資源分配、局部資源分配和本地資源管理四個層次，并為每個層次設計了相應的優(yōu)化策略和算法。該模型對資源管理的最大計算復雜度為O(n2)O(n3)，是一個優(yōu)化而有效的網格資源管理模型。 關鍵詞：計算網格 資源管理 資源分配 作業(yè) 資源調度 Globus Toolkit計算網格是近年興起的一種重要的并行分布式計算技術，其關鍵技術之一是對網格中的資源進行管理。網格中的資源具有廣域分布、異構和動態(tài)的特性，使得網格資源管理變得很復雜

2、。當前還沒有一種模型能夠處理所有的網格應用需求。目前，網格資源管理模型主要分為分層模型、抽象所有者模型和經濟市場模型三類。Globus項目組在網格協議制定上有重要發(fā)言權，包括IBM、Microsoft、Sun、Compaq、SGI、NEC在內的眾多重要公司都宣布支持Globus Toolkit。因此Globus所采用的分層模型代表了網格資源管理的發(fā)展趨勢。本文在Globus分層模型設計思想的基礎上提出一種優(yōu)化的網格資源管理模型HRMM(Hierarchical Resource Management Model)，并給出了相應的資源管理算法。為了提高效率，在HRMM的主要模塊中運用了Globu

3、s Toolkit 24提供的數據結構和接口。1 HRMM的總體結構HRMM的設計思想是：動態(tài)接收來自用戶的作業(yè)請求，并為該作業(yè)分配符合條件的計算資源，同時提供整個計算過程中有關資源信息的在線反饋，接受用戶的在線控制。HRMM的體系結構如圖1所示，將計算網格的資源管理任務分為四個層次：作業(yè)并行分析、全局資源分配、局部資源分配和本地資源管理。由圖1可見，用戶經過GUI(圖形用戶界面)向HRMM提交作業(yè)請求，作業(yè)并行分析器接收用戶的作業(yè)請求，再按最大并行度將作業(yè)中的任務劃分為若干任務組，提交給全局資源分配器。對多任務組中的每個任務，全局資源分配器在靜態(tài)資源庫中一次搜索多個滿足該需求的集群，組成候選

4、集群組提交給局部資源分配器。局部資源分配器在動態(tài)資源庫中讀取候選集群組中每個集群的有關信息，并將相應任務分配給最符合條件的集群。然后，該集群應用本地資源管理器執(zhí)行任務。在整體上，本地資源管理器每隔一定時間向靜態(tài)資源庫發(fā)送靜態(tài)資源更新信息。另外，局部資源分配器讀取動態(tài)資源庫前，動態(tài)資源庫會從本地資源管理器讀取更新信息。在這個分層模型中，一方面，用戶提交的作業(yè)能夠以最大的并行度執(zhí)行，從而高效體現了并行計算的思想；另一方面，選多個集群組成候選集群組，再確定其中某一分配資源的方案，由于綜合考慮了任務的靜態(tài)需求和動態(tài)需求，避免重復的查詢操作，從而提高了資源分配的效率。2 作業(yè)并行分析器如圖1所示，用戶經

5、過GUI向作業(yè)并行分析器提交作業(yè)請求。這個請求包括該作業(yè)中所含的多個任務的相關信息、任務間的依賴關系及每個任務的計算資源需求。作業(yè)并行分析器分析該作業(yè)中的任務及相互關系，根據各任務的依賴關系將作業(yè)中的任務劃分為不同的任務組，并對每個任務組進行適當描述后提交給全局資源分配器。21 作業(yè)的拓撲表示一個作業(yè)由一個或多個任務組成。作業(yè)的拓撲定義為一個滿足如下條件的有向無環(huán)圖：該圖的節(jié)點與作業(yè)中的任務一一對應；若任務B直接依賴于任務A，則存在一條由節(jié)點A到節(jié)點B的有向邊，稱A為B的直接前驅，B為A的直接后繼；如果存在一條從A到B的由多條有向邊組成的有向通路，則稱A為B的前驅，B為A的后繼。圖2表示一個作

6、業(yè)的拓撲結構。設該作業(yè)由標記為AG的7個任務及其相互關系組成。如圖2所示，任務D需要在任務A和B完成后才能開始，而任務G必須在任務正和F完成后才能開始。為了提高作業(yè)的并行執(zhí)行效率，需要關注任務在拓撲定義中的深度。記任務T的直接前驅集合為Pd(T)，則其深度d(T)為：若Pd(T)=，則d(T)=1；若Pd(T)，則d(T)=max d(R)+1RPd(T)22 作業(yè)的最大并行度劃分作業(yè)的并行劃分是指：一個作業(yè)拆分后形成的一系列對應每個任務、前后有序且相互獨立的任務組。一個作業(yè)可以有一個或多個并行劃分方案，形成該作業(yè)對應的并行劃分集，記作，I()為中的任務組數。 稱為作業(yè)的最大并行度劃分，如果：

7、E,且。I（ ）I（）將作業(yè)中的多個任務按照相應的深度進行劃分，形成一個最大并行度劃分。如圖2中的作業(yè)，其最大并行度劃分為： =(A，B)，(C，D，E)，F，G。3 全局資源分配器全局資源分配器接收到以RSL描述的任務組后，立刻進行分析和解釋，獲得每個任務的靜態(tài)資源需求。系統根據每個任務的資源需求在靜態(tài)資源庫中搜索滿足條件的多個集群，并將結果提交給局部資源分配器。31 靜態(tài)資源庫系統中的靜態(tài)資源庫采用基于輕量目錄訪問協議LDAP結構。在HRMM模型中，網格系統的所有靜態(tài)資源都在LDAP服務器的DIT(目錄信息樹)中建立了相應的目錄項，并用屬性，值的組合描述各種資源屬性。靜態(tài)資源庫選擇LDAP

8、可以在性能上帶來以下優(yōu)點：(1)LDAP專門對讀操作進行了優(yōu)化，在讀操作頻繁的情況下，可以提高讀取效率。(2)LDAP是跨平臺協議，可在任何計算機上使用。從而增加系統對異構網格環(huán)境的適應性。(3)LDAP服務器支持分布式的結構，靜態(tài)資源庫可訪問本地或全局的LDAP服務器，并能很方便地實現同步，即增強資源管理的分布性。32 全局資源分配算法根據任務組中每個任務的靜態(tài)需求，全局資源分配器在靜態(tài)資源庫中搜索滿足需求的集群。在搜索時首先隨機選擇搜索的起始位置，然后為每個任務分別返回最先發(fā)現的N個滿足該任務需求的集群，形成候選集群組，并以ClusterList數據結構描述后提交給局部資源分配器；其中Cl

9、usterList是用來描述候選集群組的廣義表結構，如圖3所示。對于任何一個任務，如果只找到K(N)個符合條件的集群，則只由這K個組成候選集群組；如果任何一個集群都不滿足任務的靜態(tài)需求，則向局部資源分配器提交空值，同時向作業(yè)并行分析器發(fā)送反饋信息，取消任務。設LDAP服務器所記錄的集群數量為M，則全局資源分配的計算復雜度為O(MN)。4 局部資源分配器局部資源分配器在動態(tài)資源庫中搜索候選集群組的動態(tài)信息，將這些動態(tài)信息和從全局資源分配器獲得的靜態(tài)信息相組合并進行綜合分析，最終將任務組中的每個任務分配給最適合的集群。41 動態(tài)資源庫動態(tài)資源庫中的數據以XML描述，帶來如下優(yōu)點：(1)XML針對更

10、新操作進行了優(yōu)化。因此，對于需要不斷更新的動態(tài)資源庫，可有效提高效率。(2)XML和LDAP在存儲結構上都是樹狀結構，可以很方便地相互轉化。用XML描述數據，可使動態(tài)資源庫和基于LDAP的靜態(tài)資源庫具有更好的耦合性。(3)XML與平臺無關，以XML表示的數據可很方便地被其他程序使用。42 局部資源分配策略局部資源分配器得到候選集群組ClusterList后，從動態(tài)資源庫獲取每個候選集群的動態(tài)信息，并將這些動態(tài)信息添加到相應集群的靜態(tài)信息之后，然后將靜態(tài)資源和動態(tài)資源信息相組合，形成集群綜合資源信息。設一個集群的動態(tài)資源信息為h=h1,，hmT，靜態(tài)資源信息為t=t1,tdT，其中m和d分別為動態(tài)和靜態(tài)資源描述的字段數，則集群綜合信息為=tThTT=1,pT，其中P=m+d。如圖3所示，集群2，2的綜合信息表示為2.2。類似地，將任務靜