- 相關推薦
計算網格資源管理優化技術和相關算法研究
摘要：在對現有的網格資源管理模型進行分析和比較的基礎上，提出了一種基于分層結構的具體模型HRMM，將資源管理分為作業并行分析、全局資源分配、局部資源分配和本地資源管理四個層次，并為每個層次設計了相應的優化策略和算法。該模型對資源管理的最大計算復雜度為O(n2)~O(n3)，是一個優化而有效的網格資源管理模型。計算網格是近年興起的一種重要的并行分布式計算技術，其關鍵技術之一是對網格中的資源進行管理。網格中的資源具有廣域分布、異構和動態的特性，使得網格資源管理變得很復雜。當前還沒有一種模型能夠處理所有的網格應用需求。目前，網格資源管理模型主要分為分層模型、抽象所有者模型和經濟／市場模型三類。Globus項目組在網格協議制定上有重要發言權，包括IBM、Microsoft、Sun、Compaq、SGI、NEC在內的眾多重要公司都宣布支持Globus Toolkit。因此Globus所采用的分層模型代表了網格資源管理的發展趨勢。
本文在Globus分層模型設計思想的基礎上提出一種優化的網格資源管理模型HRMM(Hierarchical Resource Management Model)，并給出了相應的資源管理算法。為了提高效率，在HRMM的主要模塊中運用了Globus Toolkit 2．4提供的數據結構和接口。
1 HRMM的總體結構
HRMM的設計思想是：動態接收來自用戶的作業請求，并為該作業分配符合條件的計算資源，同時提供整個計算過程中有關資源信息的在線反饋，接受用戶的在線控制。HRMM的體系結構如圖1所示，將計算網格的資源管理任務分為四個層次：作業并行分析、全局資源分配、局部資源分配和本地資源管理。
由圖1可見，用戶經過GUI(圖形用戶界面)向HRMM提交作業請求，作業并行分析器接收用戶的作業請求，再按最大并行度將作業中的任務劃分為若干任務組，提交給全局資源分配器。對多任務組中的每個任務，全局資源分配器在靜態資源庫中一次搜索多個滿足該需求的集群，組成候選集群組提交給局部資源分配器。局部資源分配器在動態資源庫中讀取候選集群組中每個集群的有關信息，并將相應任務分配給最符合條件的集群。然后，該集群應用本地資源管理器執行任務。在整體上，本地資源管理器每隔一定時間向靜態資源庫發送靜態資源更新信息。另外，局部資源分配器讀取動態資源庫前，動態資源庫會從本地資源管理器讀取更新信息。
在這個分層模型中，一方面，用戶提交的作業能夠以最大的并行度執行，從而高效體現了并行計算的思想；另一方面，選多個集群組成候選集群組，再確定其中某一分配資源的方案，由于綜合考慮了任務的靜態需求和動態需求，避免重復的查詢操作，從而提高了資源分配的效率。
2 作業并行分析器
如圖1所示，用戶經過GUI向作業并行分析器提交作業請求。這個請求包括該作業中所含的多個任務的相關信息、任務間的依賴關系及每個任務的計算資源需求。作業并行分析器分析該作業中的任務及相互關系，根據各任務的依賴關系將作業中的任務劃分為不同的任務組，并對每個任務組進行適當描述后提交給全局資源分配器。
2．1 作業的拓撲表示
一個作業由一個或多個任務組成。作業的拓撲定義為一個滿足如下條件的有向無環圖：該圖的節點與作業中的任務一一對應；若任務B直接依賴于任務A，則存在一條由節點A到節點B的有向邊，稱A為B的直接前驅，B為A的直接后繼；如果存在一條從A到B的由多條有向邊組成的有向通路，則稱A為B的前驅，B為A的后繼。
圖2表示一個作業的拓撲結構。設該作業由標記為A~G的7個任務及其相互關系組成。如圖2所示，任務D需要在任務A和B完成后才能開始，而任務G必須在任務正和F完成后才能開始。
為了提高作業的并行執行效率，需要關注任務在拓撲定義中的深度。記任務T的直接前驅集合為Pd(T)，則其深度d(T)為：
若Pd(T)=φ，則d(T)=1；
若Pd(T)≠φ，則d(T)=max {d(R)} 1．
R∈Pd(T)
2．2 作業的最大并行度劃分
作業的并行劃分是指：一個作業拆分后形成的一系列對應每個任務、前后有序且相互獨立的任務組。一個作業可以有一個或多個并行劃分方案，形成該作業對應的并行劃分集，記作Θ，I(Θ)為Θ中的任務組數。 稱為作業的最大并行度劃分，如果：E∈Θ,且 ξ∈Θ。I（ ）≤I（ξ）將作業中的多個任務按照相應的深度進行劃分，形成一個最大并行度劃分。如圖2中的作業，其最大并行度劃分為： ={(A，B)，(C，D，E)，F，G}。
3 全局資源分配器
全局資源分配器接收到以RSL描述的任務組后，立刻進行分析和解釋，獲得每個任務的靜態資源需求。系統根據每個任務的資源需求在靜態資源庫中搜索滿足條件的多個集群，并將結果提交給局部資源分配器。
3．1 靜態資源庫
系統中的靜態資源庫采用基于輕量目錄訪問協議LDAP結構。在HRMM模型中，網格系統的所有靜態資源都在LDAP服務器的DIT(目錄信息樹)中建立了相應的目錄項，并用
【計算網格資源管理優化技術和相關算法研究】相關文章：
研究高校人力資源管理和優化03-25
無線資源管理中的調度算法研究03-07
均勻圓陣下的DOA估計算法研究03-07
研究民辦高校人力資源管理優化03-18
基于DSP的信道譯碼算法優化03-19
淺談基于知識的網格技術應用研究03-02
計數查找算法的研究11-22