摘 要： 在混合式P2P結構的基礎上提出了P2P-Grid模型，把同類同屬性資源聚集到資源組，并建立資源組目錄樹。給出了一種可以避免Grid-Peer" title="Grid-Peer">Grid-Peer內部任務扎堆現(xiàn)象的資源調度" title="資源調度">資源調度算法和Grid-Peer調度算法。
關鍵詞： P2P-Grid模型 Grid-Peer算法 資源組 資源調度 并行資源調度模型
目前，對結合P2P與Grid二種分布式計算技術的新型網絡結構P2P-Grid方面的研究很少，且對P2P-Grid環(huán)境下資源調度機制的研究也不多見。P2P-Grid是作者針對現(xiàn)階段不同地區(qū)網絡之間的通信速度遠遠低于集群或局域網內部的通信速度以及網絡環(huán)境下資源分布不均勻的情況，在混合式P2P結構的基礎上提出來的。
在局部范圍內把地理位置彼此相近的資源構造成規(guī)模適當?shù)?a class="cblue" href="http://ihrv.cn/search/?q=網格系統(tǒng)" title="網格系統(tǒng)">網格系統(tǒng)，這些網格系統(tǒng)可看作是P2P-Grid的Grid-Peer(相當于混合式P2P結構中的Super-Peer)，并使用P2P技術組織這些Grid-Peer資源。充分利用二者各自的資源調度優(yōu)勢，在Grid-Peer集中式" title="集中式">集中式高效資源調度與Grid-Peer具備健壯性、可靠性和可用性的分布式資源調度之間達成一種平衡機制，并在各Grid-Peer之間以及Grid-Peer內部分類的資源組之間形成對資源的多點并行調度機制，可有效地避免單一網格系統(tǒng)瓶頸的產生。
Gondor的匹配器使用集中式方式組織資源，負責資源提供者和資源請求者之間需求的匹配。Adriana Iamnitchi等人使用P2P模式分布式組織資源，并使用請求向前搜索的策略發(fā)現(xiàn)資源。中科院的織女星網格項目研究了基于路由轉發(fā)模型的資源發(fā)現(xiàn)方法和面向資源發(fā)現(xiàn)的VEGA體系結構。
1 P2P-Grid模型
網格的特點及其最終面向最普通的計算機用戶的目標，決定了網格系統(tǒng)不宜采用傳統(tǒng)的集中式資源管理模式。普通計算機位于互聯(lián)網的邊緣，且P2P技術處理這類資源已經比較成熟。為把這類數(shù)量龐大的資源整合到網格系統(tǒng)中，結合P2P和Grid的互補性，可采用P2P-Grid模型[5][6]組織網絡環(huán)境下的資源。該P2P-Grid模型依據(jù)銀行系統(tǒng)的運作模式，采用“分而治之”的思想，把“單一網格系統(tǒng)”分割成若干處于對等地位的“小規(guī)模網格”系統(tǒng)，本文稱為Grid-Peer。每個Grid-Peer可使用不同網格技術管理所在域的資源，就如同P2P系統(tǒng)中計算機的操作系統(tǒng)可以互不相同。
2 Grid-Peer中基于聚集的資源組織[6]
2.1 基本概念
定義1 資源屬性值域[4]：R表示某資源任一屬性值所有可能取值為實數(shù)的集合，R上的值域定義為VA＝{x|r1≤x＜r2，x∈R，r1∈R，r2∈R}，則令VA＝[r1，r2]，VA為R的子集，表示VA由所有介于r1(可以等于r1)和r2之間的實數(shù)組成。
定義2 資源組：記錄資源屬性值在某個資源屬性值域范圍內的資源集合的域。
定義3 計算能力" title="計算能力">計算能力：計算資源在單位時間內運算的次數(shù)。
定義4 CPU==[1G，2G]：CPU的主頻取值在1GB～2GB范圍內。
定義5 Mem＝＝[64M，128M]：內存容量取值在64MB～128MB之間。
定義6 預留資源：及時分配給在某個特定的時間段內到來的任務，或某個資源出現(xiàn)故障時，準備運行遷移過來的任務的資源。
定義7 備份資源：正在運行任務的資源出現(xiàn)故障時，替換該資源繼續(xù)運行任務的資源。
定義8 任務扎堆：任務總是優(yōu)先占用被調度次數(shù)最多的資源的現(xiàn)象。
性質1 同一資源組中資源具有的計算能力屬于規(guī)定該資源組CPU屬性值域的集合。
性質2 同一資源組中資源具有的存儲容量屬于規(guī)定該資源組的內存屬性值域的集合。
性質3 同一資源組中的資源可以互為備份資源。
2.2 基于聚集的資源組目錄樹
資源的組織方式決定資源的發(fā)現(xiàn)、資源匹配和資源調度等其他的資源管理技術。而資源管理器為用戶選擇資源、匹配資源請求與具體資源的方法有很多種，不同的方法會影響資源的利用率和系統(tǒng)開銷。本文采用分布式與層次式結合的資源組織方式組織P2P-Grid環(huán)境下的資源。把計算資源按照接入到互聯(lián)網的方式和屬性分為HPC(高性能計算機)、PC(桌面計算機)和LAN(局域網)三類。每類再根據(jù)資源屬性進行細分并確立多個資源組。資源組中聚集的資源計算能力和存儲能力相當。
LAN資源的組織形式如圖1(其他二類資源的組織類似)。
3 資源調度
3.1 并行資源調度模型
P2P-Grid的目標是把網絡邊緣上的計算機利用起來，形成具有無窮處理能力的若干個虛擬超級計算機，即Grid-Peer。在Grid-Peer中，相對于要調度的任務而言，資源同樣需要調度。為完成用戶提交的任務和滿足用戶提出的要求，把Grid-Peer中所有可用資源(計算資源、存儲資源和網絡資源)進行匹配，使用合理的資源分配方式和資源調度策略。調度策略是一些調度規(guī)則和算法 ，使應用能夠按照規(guī)則找到最優(yōu)資源。其實質是將n個相互獨立的任務分配到m個異構可用資源，使得總任務的完成時間最小且資源得到充分利用。
資源調度的方式有集中式調度和分布式調度二種。
(1)集中式調度：在網格中只有一個調度中心，負責調度網格中的所有資源。其優(yōu)點是調度系統(tǒng)知道網格中的所有資源，對于一個應用可以產生高效的資源調度方案。缺點是：當網絡比較大時，調度系統(tǒng)便很難掌握所有的資源，因此調度系統(tǒng)會成為瓶頸。例如，調度系統(tǒng)因為錯誤出現(xiàn)故障，就會影響整個網格系統(tǒng)。集中式調度比較適合小型網格。
(2)分布式調度：有多個調度中心，各中心是平等的。優(yōu)點是健壯性、可靠性和可用性比較高。缺點是調度中心之間的通信量比較大，由于不能掌握網格中所有資源，很難找到全局最優(yōu)的資源分配方式。
由于P2P-Grid把單一網格系統(tǒng)拆分成多個小型網格系統(tǒng)(Grid-Peer)，因此減小了網格系統(tǒng)規(guī)模，并且Grid-Peer內部可以使用集中式的資源管理方式。Grid-Peer使用P2P技術進行信息交互、實現(xiàn)資源共享，構成的P2P-Grid系統(tǒng)是一個分布式系統(tǒng)。因此，P2P-Grid系統(tǒng)是分布式和集中式系統(tǒng)的結合。作者結合集中式調度和分布式調度的優(yōu)點，設計了P2P-Grid環(huán)境下的基于聚集的并行資源調度模型。對整個P2P-Grid而言，每個Grid-Peer可同時調度資源，形成一種多點調度。同樣，在Grid-Peer內部，資源調度系統(tǒng)可基于聚集的資源組并行地調度各資源組中的任務。把單一網格系統(tǒng)拆分重組成為P2P-Grid系統(tǒng)后，每個Grid-Peer系統(tǒng)所管理的資源數(shù)目比原來少了，從而解決了因為單一的網格系統(tǒng)規(guī)模太大，難以掌握所有資源狀態(tài)以及屬性信息這一問題。原先單一網格系統(tǒng)負載由許許多多Grid-Peer分擔，不僅可解決系統(tǒng)任務請求時出現(xiàn)的瓶頸問題，也可快速發(fā)現(xiàn)任務所需資源，提高該任務的QoS。另外，可減小由于單一網格系統(tǒng)出錯而導致整個系統(tǒng)崩潰的概率。
拆分重組后的P2P-Grid系統(tǒng)中的每個Grid-Peer也是一個網格系統(tǒng)，其規(guī)模也會直接影響到Grid-Peer之間信息交流時的通信量。如果規(guī)模過小，P2P-Grid系統(tǒng)過于分布，必然會造成Grid-Peer之間任務頻繁地遷移，在網絡中產生大量的數(shù)據(jù)包。數(shù)據(jù)包過多，還可造成網絡擁塞，使P2P-Grid性能急劇下降。因此，設計P2P-Grid模型時應把Grid-Peer規(guī)模設計成大小適中，既可以利用集中式調度機制高效產生資源調度方案，也可充分利用分布式調度具備的健壯性、可靠性和可用性等優(yōu)點。
P2P-Grid系統(tǒng)的資源調度具有以下特點：
(1)P2P-Grid系統(tǒng)不同于傳統(tǒng)的單機處理任務。在單臺計算機中可以利用的資源有限，一般都是任務等待少量計算資源，需要調度的是任務。而在Grid-Peer系統(tǒng)中，資源數(shù)量非常多，有時可能出現(xiàn)資源等待處理任務的情況。
(2)P2P-Grid系統(tǒng)中資源是動態(tài)變化的，隨著時間的變化，總有舊的資源推出和新的資源加入。
(3)P2P-Grid系統(tǒng)是由各種不同的管理域組成的異構環(huán)境，系統(tǒng)中的資源調度程序不可能控制系統(tǒng)中的所有資源。
(4)為充分利用所有資源，需要避免任務競爭性能相對良好的資源。
因此，設計一個P2P-Grid環(huán)境下的資源調度模型會遇到以下難點：
(1)由于資源之間的關聯(lián)性，進入Grid-Peer中的任務會與其他已經在Grid-Peer中的任務競爭資源，造成任務之間的相互影響。因此，要找到滿足所有任務要求的最優(yōu)調度方案有時不大可能。
(2)由于P2P-Grid中的資源種類繁多，各種任務對資源的要求也各種各樣，所以很難用統(tǒng)一的尺度描述和度量其特征。
(3)P2P-Grid中對各種資源的約束很多是非線性的，要達到的調度目標也很多，例如要求時間最少、代價最小、資源利用率最高等，并且有些目標相互矛盾。對于這種多目標多約束的問題，找到滿足所有約束和目標的全局最優(yōu)解是很困難的。
資源組的概念是針對P2P-Grid系統(tǒng)資源調度的特點以及設計資源調度模型的難點提出的。屬于同一資源組中資源的物理屬性相近，故這些資源對同類任務具有相似的興趣。針對Grid-Peer系統(tǒng)的資源組織模型、任務調度模型以及相應的資源發(fā)現(xiàn)機制，設計了如圖2所示的基于資源組模式的并行資源調度模型。
資源組是記錄性能相近的資源聚集成資源集合的一個域，資源調度完全根據(jù)層次式資源組目錄樹并行進行。一般情況下，該任務請求哪類資源只需查找這類資源子樹，搜索一個或多個資源組中的資源進行調度，并在給任務分配資源時，多預留一些實時可用的資源，作為分配資源的備份資源。
Grid-Peer系統(tǒng)資源管理模型中的HPC管理器、PC管理器和LAN管理器除了要管理其中的資源樹的邏輯信息外，還要針對每個資源組中的可用資源、正在運行任務的資源以及備份資源進行監(jiān)控，實時獲取資源最新的狀態(tài)信息，以便資源調度時不至于把任務分配到不能正常運行的計算資源上。
Grid-Peer環(huán)境下的資源管理系統(tǒng)采用基于資源物理特性構造的資源組目錄樹模型。Grid-Peer系統(tǒng)的資源按照其物理特性歸類，根據(jù)資源的處理能力分為：超級計算機、位于局域網中的計算機和單獨連接到互聯(lián)網的計算機三種計算類資源。資源的屬性信息分別組織在相應的三類資源管理器中。每類資源根據(jù)其計算能力可以再分為幾個等級，例如：現(xiàn)在的桌面計算機的CPU主頻主要位于1GHz以下，1GHz以上、2GHz以下、2GHz以上、3GHz以下，如此類推。若任務請求資源對其主存能力有要求，可根據(jù)資源內存容量繼續(xù)細分，詳見資源組目錄樹(圖1)。Grid-Peer系統(tǒng)的資源調度根據(jù)資源類別分別進行，可減少資源的查找時間，提高資源與任務的匹配度，把更高處理能力的資源留給一些特殊的任務，使Grid-Peer系統(tǒng)的整體性能得到提高。
3.2 資源調度參數(shù)
下面介紹Grid-Peer系統(tǒng)內部的資源調度參數(shù)和P2P-Grid系統(tǒng)對Grid-Peer調度所要用到的參數(shù)。
本地Grid-Peer系統(tǒng)的參數(shù)：Rg表示資源組；T表示資源已經被調度的次數(shù)；Ht表示資源組中被調度次數(shù)最多的資源的調度次數(shù)；Bd表示資源所在的網絡帶寬，指HPC的集群計算機和LAN資源的內部網絡帶寬；Hbd表示資源組中資源的最高帶寬，本文僅指HPC的集群計算機和LAN資源的內部網絡帶寬；Rt表示在t時刻網絡通信速度；HRt表示訪問資源組中資源能夠達到的最高網絡通信速度；Cpu表示資源的計算能力，也就是該計算資源的主頻；Hcpu表示資源組中資源計算能力的最高上限，如資源樹中 表示“Cpu=＝[1G，2G]”這一資源組的Hcpu為2GHz。PRI表示調度優(yōu)先級。
在單個Grid-Peer系統(tǒng)中每個資源組由一個專用服務器負責管理，對其中可用資源按照被訪問時間、計算能力和使用頻率等綜合參數(shù)進行優(yōu)先級排序。計算能力相同的，訪問時間越短，排序越靠前；計算能力和訪問時間相同的情況下，使用頻率高的反而排序靠后。充分挖掘出更多具有同等屬性的資源以均衡網絡流量，充分體現(xiàn)P2P-Grid的動態(tài)特征，因為訪問時間隨信息流量不同而發(fā)生變化。
單個Grid-Peer系統(tǒng)中，不同資源組也可以使用該參數(shù)來制定該資源組內部的資源調度策略，從而使得單個Grid-Peer中資源組管理資源信息的服務器能夠同時多點調度Grid-Peer系統(tǒng)中的資源，提高系統(tǒng)的工作效率。
P2P-Grid系統(tǒng)中Grid-Peer調度參數(shù)：L表示Grid-Peer的系統(tǒng)負載；Time表示搜索到Grid-Peer所用的時間；Ltime表示搜索到Grid-Peer所用的最長時間；PRIGrid-Peer為調度Grid-Peer的優(yōu)先級。
3.3 資源調度過程和算法
(1)根據(jù)提交任務的屬性決定選擇三種資源中的那一類，然后在相應信息資源管理器中查找初步滿意的資源集，同時，資源調度管理者還需檢查可用資源隊列中的資源。若可用資源隊列中具有最高優(yōu)先級的資源之優(yōu)先級超過了0.5，則可以選擇此資源作為此次被調度的資源；否則等待計算從資源管理器中所發(fā)現(xiàn)資源的優(yōu)先級。這兩項操作是同時進行的,可以減少資源的相對發(fā)現(xiàn)時間。
(2)根據(jù)資源所在的位置、網絡流量、帶寬、資源使用率、資源計算能力等參數(shù)，決定資源調度的次序。假定資源調度最高級別的權值為1，資源的計算能力由cpu的主頻決定，多cpu采用累加的形式計算。則資源調度優(yōu)先級為：
PRI＝Cpu/Hcpu×80%+Bd/Hbd×10%+Rt/HRt×5%-T/Ht×5%
最后一項對調度次數(shù)進行加權處理，可避免任務總是搶占被調度次數(shù)較多的資源，造成這些資源附近網絡流量過大；還可以充分挖掘出更多新注冊的資源，有效均衡網絡流量，避免網絡阻塞。
(3)計算出所查找資源組中初步滿意的各資源級別，比較本次最高級別與可用資源隊列中最高優(yōu)先級資源級別，選擇級別高的資源作為此次被調度的資源來處理提交的任務，并把計算出來的結果返回給用戶，記錄加1后的調度次數(shù)和被調度的時間，按照資源調度方法回收該資源，保存在可用資源隊列中，等待下一次的調度。其中調度時間相當重要，因為Grid-Peer環(huán)境下的資源具有動態(tài)特性，此次確定的優(yōu)先級在以后某個時間段將會發(fā)生很大的變化。如果發(fā)現(xiàn)兩個資源的優(yōu)先級相等，則選擇最近被調度的資源去處理提交的任務。
全局P2P-Grid環(huán)境下的資源調度實際上是對所發(fā)現(xiàn)的Grid-Peer進行調度。如何選擇Grid-Peer進行任務遷移，還要根據(jù)該Grid-Peer系統(tǒng)負載及本地Grid-Peer到遠程Grid-Peer之間通信速度的影響確定。在本地Grid-Peer系統(tǒng)中采用聚集資源組的方式調度本地資源，而在P2P-Grid系統(tǒng)中采用泛洪算法發(fā)現(xiàn)滿足條件的Grid-Peer，然后在這些Grid-Peer中選擇一個合適的Grid-Peer。
向本地Grid-Peer系統(tǒng)提交任務時，可能會遇到本地Grid-Peer系統(tǒng)負載過重，不能滿足用戶QoS需求的情況。此時，本地Grid-Peer就需要向其他的遠程Grid-Peer轉移任務。這種情況需要查找具有最佳處理能力的Grid-Peer，并把任務遷移到這個最佳的Grid-Peer。Grid-Peer調度最主要的就是在所發(fā)現(xiàn)的Grid-Peer集合中選擇某個合適的超級Peer。Grid-Peer處理完任務后直接向用戶返回結果。
QoS指標是指Grid-Peer對轉移到來的任務的服務質量，由處理結果精確性和任務處理時間兩個參數(shù)來決定。當本地Grid-Peer在某個時間段內接收到返回的查找信息后，根據(jù)返回時間的長短和被返回系統(tǒng)內在的處理能力來決定把任務轉移到某個Grid-Peer。選擇具有最高調度優(yōu)先級的Grid-Peer來遷移本系統(tǒng)中的任務，Grid-Peer的優(yōu)先級為：
PRIGrid-Peer＝(1-Time/Ltime)×10％+90％×(1-L)
網格技術和P2P技術已經成為高性能計算領域的研究熱點，結合P2P和Grid的P2P-Grid也將逐漸成為高性能計算研究中的一個熱點。本文在確定P2P-Grid的資源組織模型，即基于聚集的層次式資源組目錄樹之后，設計了基于資源組的并行資源調度模型。本模型為整個P2P-Grid系統(tǒng)中網格資源調度模型的一個雛形，今后還有很多方面需進一步的研究。
參考文獻
1 Raman R，Livny M，Solomon M.Matchmaking：distributed resource management for high throughput computing.In：Proc. of the 7th IEEE Int′l Symp.on High Performance Distributed Computing.Chicago，IL，USA，1998
2 Gong YL，Dong F P，Li W et al.VEGA Infrastructure for Resource Discovery in Grids.J.Compute.Sci.&Technol，2003；18(4)
3 徐志偉，馮百明，李偉.網格計算技術.北京：電子工業(yè)出版社，2004
4 周曉，陳鳴.基于散列值的廣域網服務發(fā)現(xiàn).軟件學報，2004；15(10)
5 葉從歡，江武漢，孫世新.P2P與Grid的結合：P2P-Grid模型研究.微型機與應用，2005；24(5)
6 葉從歡.P2P-Grid環(huán)境下的一種新的資源組織方法.微型機與應用，2005；24(12)