對(duì)于計(jì)算機(jī)大家度不陌生，但是對(duì)于計(jì)算機(jī)網(wǎng)格資源的認(rèn)識(shí)你可能就了解的甚少了。網(wǎng)格的管理應(yīng)用對(duì)現(xiàn)在科技上有何影響呢?它的發(fā)展能否給科技的進(jìn)步帶來(lái)動(dòng)力及措施呢?同時(shí)網(wǎng)格資源的建設(shè)對(duì)現(xiàn)在日常生活又有什么觀點(diǎn)呢?本文選自：《計(jì)算機(jī)工程》,《計(jì)算機(jī)工程》刊登內(nèi)容包括發(fā)展趨勢(shì)/熱點(diǎn)技術(shù)、博士論文、基金項(xiàng)目論文、專題論文、軟件技術(shù)與數(shù)據(jù)庫(kù)、安全技術(shù)、多媒體技術(shù)及應(yīng)用、網(wǎng)絡(luò)與通信、人工智能及識(shí)別技術(shù)、工程應(yīng)用技術(shù)與實(shí)現(xiàn)、開發(fā)研究與設(shè)計(jì)技術(shù)等。本刊特點(diǎn)在于以最快的速度、科學(xué)求實(shí)的精神，精選刊登代表計(jì)算機(jī)行業(yè)前沿科研、技術(shù)、工程方面的高、精、尖優(yōu)秀論文

　　摘要：網(wǎng)格作為一種能帶來(lái)巨大處理、存儲(chǔ)能力和其他IT資源的新型網(wǎng)絡(luò)，可以應(yīng)付臨時(shí)之用。網(wǎng)格計(jì)算通過(guò)共享網(wǎng)絡(luò)將不同地點(diǎn)的大量計(jì)算機(jī)相聯(lián)，從而形成虛擬的超級(jí)計(jì)算機(jī),將各處計(jì)算機(jī)的多余處理器能力合在一起，可為研究和其他數(shù)據(jù)集中應(yīng)用提供巨大的處理能力。有了網(wǎng)格計(jì)算，那些沒(méi)有能力購(gòu)買價(jià)值數(shù)百萬(wàn)美元的超級(jí)計(jì)算機(jī)的機(jī)構(gòu)，也能利用其巨大的計(jì)算能力。

　　關(guān)鍵詞：網(wǎng)格資源,管理技術(shù),計(jì)算機(jī)應(yīng)用

　　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è)并行分析、全局資源分配、局部資源分配和本地資源管理。

　　在對(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)格資源管理模型。

　　由圖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ù)浔硎?/p>

　　一個(gè)作業(yè)由一個(gè)或多個(gè)任務(wù)組成。作業(yè)的拓?fù)涠x為一個(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的后繼。

　　目前，網(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)和接口。

　　圖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ù)涠x中的深度。記任務(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)，并用<屬性，值>的組合描述各種資源屬性。靜態(tài)資源庫(kù)選擇LDAP可以在性能上帶來(lái)以下優(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)資源庫(kù)可訪問(wèn)本地或全局的LDAP服務(wù)器，并能很方便地實(shí)現(xiàn)同步，即增強(qiáng)資源管理的分布性。

　　3.2 全局資源分配算法

　　根據(jù)任務(wù)組中每個(gè)任務(wù)的靜態(tài)需求，全局資源分配器在靜態(tài)資源庫(kù)中搜索滿足需求的集群。在搜索時(shí)首先隨機(jī)選擇搜索的起始位置，然后為每個(gè)任務(wù)分別返回最先發(fā)現(xiàn)的N個(gè)滿足該任務(wù)需求的集群，形成候選集群組，并以ClusterList數(shù)據(jù)結(jié)構(gòu)描述后提交給局部資源分配器;其中ClusterList是用來(lái)描述候選集群組的廣義表結(jié)構(gòu)，如圖3所示。對(duì)于任何一個(gè)任務(wù)，如果只找到K(

　　4 局部資源分配器

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

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

　　動(dòng)態(tài)資源庫(kù)中的數(shù)據(jù)以XML描述，帶來(lái)如下優(yōu)點(diǎn)：

　　(1)XML針對(duì)更新操作進(jìn)行了優(yōu)化。因此，對(duì)于需要不斷更新的動(dòng)態(tài)資源庫(kù)，可有效提高效率。

　　(2)XML和LDAP在存儲(chǔ)結(jié)構(gòu)上都是樹狀結(jié)構(gòu)，可以很方便地相互轉(zhuǎn)化。用XML描述數(shù)據(jù)，可使動(dòng)態(tài)資源庫(kù)和基于LDAP的靜態(tài)資源庫(kù)具有更好的耦合性。

　　(3)XML與平臺(tái)無(wú)關(guān)，以XML表示的數(shù)據(jù)可很方便地被其他程序使用。

　　4.2 局部資源分配策略

　　局部資源分配器得到候選集群組ClusterList后，從動(dòng)態(tài)資源庫(kù)獲取每個(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ù)，則集群綜合信息為υ=[tThT]T=[υ1,…,υp]T，其中P=m+d。如圖3所示，集群2，2的綜合信息表示為υ2.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ù)的綜合資源需求：

　　∨i∈[1,n],∨j∈[1，p]，Vi,f(i)[j]≥ri[j]

　　其中，n為任務(wù)組中的任務(wù)數(shù)量，p為向量u/和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ī)劃問(wèn)題：

　　其中C是可以改變的加權(quán)系數(shù)，且C>0。由于f(i)為離散值且取值范圍有限，因此提出以下優(yōu)化方法，通過(guò)較少的計(jì)算來(lái)搜索近似的最優(yōu)解。記候選集群組為ClusterList，則算法表示如下：

　　STEP 1.對(duì)每個(gè)任務(wù)和候選集群，將靜態(tài)和動(dòng)態(tài)資源信息組合為綜合資源信息;

　　STEP 2.刪除ClusterList中不滿足總和資源需求的集群;

　　STEP 3. ，計(jì)算每個(gè)集群i,j的局部損失Cost[i,j]:=‖vi,j-ri‖+C·tij;

　　STEP 4.并行地對(duì)Cost的每一列排序，并按從小到大的次序重排ClusterList中的集群鏈表;

　　STEP 5.如果，則報(bào)告不存在滿足條件的解，算法結(jié)束;

　　STEP 6.∨i∈[1,n],并行計(jì)算Cost*[i]：=‖vi,k-ri‖+C·ti,k，其中k=aramin(‖vi,j‖<‖vi,1‖);

　　STEP 7.∨i∈[1,n]，并行計(jì)算d(i]：=

　　STEP 8.置b:=argmin(d[j])，并刪除ClusterList中任務(wù)b的集群鏈表中前k-1個(gè)集群節(jié)點(diǎn);

　　STEP 9.如果滿足則轉(zhuǎn)STEPl0，否則轉(zhuǎn)STEP6;

　　STEP 10.∨i∈[1,n]，將第i個(gè)任務(wù)分配給ClusterList中相應(yīng)任務(wù)集群鏈表中的第一個(gè)集群，算法結(jié)束。

　　該算法為資源分配查找到了近似的最優(yōu)解，并在最大程度上利用了資源管理站點(diǎn)所在集群的計(jì)算資源，將大部分計(jì)算并行化。設(shè)資源管理站點(diǎn)所在集群的節(jié)點(diǎn)數(shù)為戶，則該算法在每個(gè)節(jié)點(diǎn)上的計(jì)算復(fù)雜度為O(n2n/P)

　　5 分析與總結(jié)

　　本課題組采用基于分層模型的結(jié)構(gòu)，將資源管理分為四個(gè)層次，然后在每個(gè)層次對(duì)模型的性能做出優(yōu)化并提出了相應(yīng)的算法。從總體上，HRMM對(duì)一個(gè)作業(yè)進(jìn)行資源管理的最大計(jì)算復(fù)雜度不超過(guò)O(n3)，是一個(gè)優(yōu)化而有效的網(wǎng)格系統(tǒng)資源管理模型。