?

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

2.2? 作業(yè)的最大并行度劃分
??? 作業(yè)的并行劃分是指：一個(gè)作業(yè)拆分后形成的一系列對(duì)應(yīng)每個(gè)任務(wù)、前后有序且相互獨(dú)立的任務(wù)組。一個(gè)作業(yè)可以有一個(gè)或多個(gè)并行劃分方案，形成該作業(yè)對(duì)應(yīng)的并行劃分集，稱為作業(yè)的最大并行度劃分，將作業(yè)中的多個(gè)任務(wù)按照相應(yīng)的深度進(jìn)行劃分，形成一個(gè)最大并行度劃分。如圖2中的作業(yè)，其最大并行度劃分為：

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（目錄信息樹(shù)）中建立了相應(yīng)的目錄項(xiàng)，并用<屬性，值>的組合描述各種資源屬性。靜態(tài)資源庫(kù)選擇LDAP可以在性能上帶來(lái)以下優(yōu)點(diǎn)：
??? (1) LDAP專門(mén)對(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)上都是樹(shù)狀結(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=[h₁,…,h_m]^T，靜態(tài)資源信息為t=[t₁,…, t_d]^T，其中m和d分別為動(dòng)態(tài)和靜態(tài)資源描述的字段數(shù)，則集群綜合信息為v=[t^T h^T]^T =[v₁,…, v_p]^T，其中p=m+d。如圖3所示，集群2,2的綜合信息表示為v_2,2。類(lèi)似地，將任務(wù)靜態(tài)資源需求和動(dòng)態(tài)資源組合，設(shè)一個(gè)任務(wù)的動(dòng)態(tài)資源需求為g=[g₁,…,g_m]^T，靜態(tài)資源需求為s=[s₁,…,s_d]^T，則綜合資源需求為r=[s^T g^T]^T=[r₁,…,r_p]^T。任務(wù)i的綜合資源需求表示為r_i。在確定分配策略時(shí)，將只考慮任務(wù)的綜合資源需求和集群的綜合資源信息。
??? 首先，為了任務(wù)能夠順利完成，最終被選擇的集群必須同時(shí)滿足任務(wù)的靜態(tài)資源需求和動(dòng)態(tài)資源需求，即滿足任務(wù)的綜合資源需求：
???

??? 其中，n為任務(wù)組中的任務(wù)數(shù)量，p為向量v和r的維數(shù)，f(i)為任務(wù)i的候選集群（即ClusterList中Task_i對(duì)應(yīng)的集群鏈表" title="鏈表">鏈表）中最終被選擇集群的序號(hào)。因此，首先在ClusterList中刪除所有不滿足上述條件的集群，并記第i個(gè)任務(wù)還剩余K_i個(gè)符合綜合資源需求的候選集群，其中1≤i≤n，1≤K_i≤N。最后，局部資源分配器要為每個(gè)任務(wù)Task_i從K_i個(gè)候選集群中選擇最合適的一個(gè)。綜合考慮計(jì)算網(wǎng)格的整體資源分配效率，在具體選擇集群時(shí)采用如下決策機(jī)制：
??? (1) 獲選集群的綜合資源信息應(yīng)盡量接近相應(yīng)任務(wù)的綜合資源需求，避免資源的浪費(fèi)，即：

??? 其中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 4. 并行地對(duì)Cost的每一列排序，并按從小到大的次序重排ClusterList中的集群鏈表;
??? STEP 5. 則報(bào)告不存在滿足條件的解，算法結(jié)束;