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

摘要：在對(duì)現(xiàn)有的網(wǎng)格資源管理模型進(jìn)行分析和比較的基礎(chǔ)上，提出了一種基于分層結(jié)構(gòu)的具體模型HRMM，將資源管理分為作業(yè)并行分析、全局資源分配、局部資源分配和本地資源管理四個(gè)層次，并為每個(gè)層次設(shè)計(jì)了相應(yīng)的優(yōu)化策略和算法。該模型對(duì)資源管理的最大計(jì)算復(fù)雜度為O(n2)~O(n3)，是一個(gè)優(yōu)化而有效的網(wǎng)格資源管理模型。

計(jì)算網(wǎng)格是近年興起的一種重要的并行分布式計(jì)算技術(shù)，其關(guān)鍵技術(shù)之一是對(duì)網(wǎng)格中的資源進(jìn)行管理。網(wǎng)格中的資源具有廣域分布、異構(gòu)和動(dòng)態(tài)的特性，使得網(wǎng)格資源管理變得很復(fù)雜。當(dāng)前還沒(méi)有一種模型能夠處理所有的網(wǎng)格應(yīng)用需求。目前，網(wǎng)格資源管理模型主要分為分層模型、抽象所有者模型和經(jīng)濟(jì)／市場(chǎng)模型三類。Globus項(xiàng)目組在網(wǎng)格協(xié)議制定上有重要發(fā)言權(quán)，包括IBM、Microsoft、Sun、Compaq、SGI、NEC在內(nèi)的眾多重要公司都宣布支持Globus Toolkit。因此Globus所采用的分層模型代表了網(wǎng)格資源管理的發(fā)展趨勢(shì)。

本文在Globus分層模型設(shè)計(jì)思想的基礎(chǔ)上提出一種優(yōu)化的網(wǎng)格資源管理模型HRMM(Hierarchical Resource Management Model)，并給出了相應(yīng)的資源管理算法。為了提高效率，在HRMM的主要模塊中運(yùn)用了Globus Toolkit 2．4提供的數(shù)據(jù)結(jié)構(gòu)和接口。

1 HRMM的總體結(jié)構(gòu)

HRMM的設(shè)計(jì)思想是：動(dòng)態(tài)接收來(lái)自用戶的作業(yè)請(qǐng)求，并為該作業(yè)分配符合條件的計(jì)算資源，同時(shí)提供整個(gè)計(jì)算過(guò)程中有關(guān)資源信息的在線反饋，接受用戶的在線控制。HRMM的體系結(jié)構(gòu)如圖1所示，將計(jì)算網(wǎng)格的資源管理任務(wù)分為四個(gè)層次：作業(yè)并行分析、全局資源分配、局部資源分配和本地資源管理。

由圖1可見，用戶經(jīng)過(guò)GUI(圖形用戶界面)向HRMM提交作業(yè)請(qǐng)求，作業(yè)并行分析器接收用戶的作業(yè)請(qǐng)求，再按最大并行度將作業(yè)中的任務(wù)劃分為若干任務(wù)組，提交給全局資源分配器。對(duì)多任務(wù)組中的每個(gè)任務(wù)，全局資源分配器在靜態(tài)資源庫(kù)中一次搜索多個(gè)滿足該需求的集群，組成候選集群組提交給局部資源分配器。局部資源分配器在動(dòng)態(tài)資源庫(kù)中讀取候選集群組中每個(gè)集群的有關(guān)信息，并將相應(yīng)任務(wù)分配給最符合條件的集群。然后，該集群應(yīng)用本地資源管理器執(zhí)行任務(wù)。在整體上，本地資源管理器每隔一定時(shí)間向靜態(tài)資源庫(kù)發(fā)送靜態(tài)資源更新信息。另外，局部資源分配器讀取動(dòng)態(tài)資源庫(kù)前，動(dòng)態(tài)資源庫(kù)會(huì)從本地資源管理器讀取更新信息。

在這個(gè)分層模型中，一方面，用戶提交的作業(yè)能夠以最大的并行度執(zhí)行，從而高效體現(xiàn)了并行計(jì)算的思想；另一方面，選多個(gè)集群組成候選集群組，再確定其中某一分配資源的方案，由于綜合考慮了任務(wù)的靜態(tài)需求和動(dòng)態(tài)需求，避免重復(fù)的查詢操作，從而提高了資源分配的效率。

2 作業(yè)并行分析器

如圖1所示，用戶經(jīng)過(guò)GUI向作業(yè)并行分析器提交作業(yè)請(qǐng)求。這個(gè)請(qǐng)求包括該作業(yè)中所含的多個(gè)任務(wù)的相關(guān)信息、任務(wù)間的依賴關(guān)系及每個(gè)任務(wù)的計(jì)算資源需求。作業(yè)并行分析器分析該作業(yè)中的任務(wù)及相互關(guān)系，根據(jù)各任務(wù)的依賴關(guān)系將作業(yè)中的任務(wù)劃分為不同的任務(wù)組，并對(duì)每個(gè)任務(wù)組進(jìn)行適當(dāng)描述后提交給全局資源分配器。

2．1 作業(yè)的拓?fù)浔硎?IMG onmousewheel="return bbimg(this)" onclick=ImgClick(this) height=242 hspace=1 src="/Freepaper/UploadFiles_paper/200608/200682320225610.gif" width=271 align=right vspace=1 border=0 resized="0">

一個(gè)作業(yè)由一個(gè)或多個(gè)任務(wù)組成。作業(yè)的拓?fù)涠�義為一個(gè)滿足如下條件的有向無(wú)環(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ù)正和F完成后才能開始。

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

若Pd(T)=φ，則d(T)=1；

若Pd(T)≠φ，則d(T)=max {d(R)} 1．

R∈Pd(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è)的最大并行度劃分，如果：E∈Θ,且　ξ∈Θ。I（ ）≤I（ξ）將作業(yè)中的多個(gè)任務(wù)按照相應(yīng)的深度進(jìn)行劃分，形成一個(gè)最大并行度劃分。如圖2中的作業(yè)，其最大并行度劃分為： ={(A，B)，(C，D，E)，F(xiàn)，G}。

3 全局資源分配器

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

3．1 靜態(tài)資源庫(kù)

系統(tǒng)中的靜態(tài)資源庫(kù)采用基于輕量目錄訪問(wèn)協(xié)議LDAP結(jié)構(gòu)。在HRMM模型中，網(wǎng)格系統(tǒng)的所有靜態(tài)資源都在LDAP服務(wù)器的DIT(目錄信息樹)中建立了相應(yīng)的目錄項(xiàng)，并用

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

研究高校人力資源管理和優(yōu)化03-25

無(wú)線資源管理中的調(diào)度算法研究03-07

均勻圓陣下的DOA估計(jì)算法研究03-07

基于802.11a的信道估計(jì)算法設(shè)計(jì)與研究03-07

研究民辦高校人力資源管理優(yōu)化03-18

基于DSP的信道譯碼算法優(yōu)化03-19

淺談基于知識(shí)的網(wǎng)格技術(shù)應(yīng)用研究03-02

作業(yè)成本計(jì)算法與傳統(tǒng)成本計(jì)算法的比較與運(yùn)用03-22

計(jì)數(shù)查找算法的研究11-22