網格環境下的大規模數據並行型計算主系統及方法

2023-09-12 22:49:55

專利名稱：網格環境下的大規模數據並行型計算主系統及方法
技術領域：
本發明涉及一種計算機的計算技術，特別是涉及一種通過在普通的、廉價的計算機機群構成的大規模計算環境下，利用現有空餘計算資源，通用的數據並行型大規模計算系統來實現的計算技術及算法。
背景技術：
隨著信息技術的飛速發展和日益普及，海量信息的處理和高性能計算的需求越來越迫切，並且這些需求逐漸被國家建設的各個領域提出。尋求高性能價格比的海量信息處理技術、高性能計算技術已經成為產業界和學術界所面臨的急需解決的主要問題。針對這一問題，網格和數據網格以其良好的自治性、自相似性、異構性、管理的多樣性、強大的並行I/O能力、非常高的性能價格比等特性成為可行的最佳解決方案之一。目前由多個計算機網絡構成的Intranet越來越多，大量的廉價的個人計算裝置隨處可見，但是它們的資源利用率非常低。相關文獻研究指出，在一個網絡環境下，給定的時間內有許多資源沒被使用，即使在一天最繁忙的時候，仍有三分之一的工作站完全未用，集群中的70％到85％的網絡存儲器(分布在網絡上各個節點的內存)處於空閒狀態。所以，挖掘利用由多個計算機機群構成的網格上的空餘的計算資源、存儲資源、通信資源，可以得到大量的、非專用的、廉價的、大規模的高性能處理和計算資源。然而，隨著機群節點數目和網絡數目的增加，系統的可靠性和資源的動態調動能力就會下降。所以機群的可靠性技術、可擴展技術的研究成為這一領域的研究熱點，其中微軟的Wolfpack、Oracle的Failover、NCR的LifeKeeper是可靠性機群計算的典型代表。然而，隨著數據網格資源規模的日益擴大、網格資源和服務的日益多樣化，這些傳統的可靠性技術已經無法適合異構的、多可信級別的網格資源的管理需求，因此基於網格的全新大規模並行理論模型和算法的研究越來越迫切。

發明內容
針對上述現有技術中存在的缺陷，本發明所要解決的技術問題是提供一種能利用目前現有的計算資源、網絡資源構造具有很好的容錯特性、良好的加速比特性、非常高的動態負載能力的，廉價的、大規模的、可靠的、穩定的網格環境下的大規模數據並行型計算主系統及方法。
為了解決上述技術問題，本發明所提供的一種網格環境下的大規模數據並行型計算主系統，包括一網格監控系統DGSS(DATA GRID SUPERVISE SYSTEM)，利用多Agent合作機制對DG實施有效動態的狀態監控的網格管理系統；還包括由機群邏輯環構成的一網格計算系統DGCS(DATA GRID COMPUTINGSYSTEM)，其中所述機群邏輯環，由設定編號的計算機機群按編號順序聯接構成，編號最後的機群的邏輯後繼機群是編號為1的機群；所述編號是根據計算機機群的所有計算節點的綜合計算能力的和按從大到小的順序對所有機群進行設定的編號；在機群邏輯環上除第1編號機群和最大編號機群之間外，越臨近的機群的綜合計算能力越相近；所述機群邏輯環上的各個計算機機群由計算節點邏輯環構成，所述計算節點邏輯環，由設定編號的計算節點按編號順序聯接構成，編號最後的計算節點的邏輯後繼節點是編號為1的計算節點；所述編號是根據每個計算節點的綜合計算能力按從大到小的順序對所有計算節點進行設定的編號，所述每個計算節點的綜合計算能力是按照權重向量W計算出來的；在計算節點邏輯環上除第1編號計算節點和最大編號計算節點之間外，越臨近的計算節點的綜合計算能力越相近；由機群邏輯環和計算節點邏輯環構成了動態DG(數據網格計算系統)；所述網格監控系統通過普通的Lan或Intranet連接所述動態網格計算系統的每個計算機機群和計算節點。
為了解決上述技術問題，本發明所提供的一種網格環境下的大規模數據並行型計算主系統的m-冗餘分配策略其步驟如下在一個邏輯環(包括機群環或計算節點環)上，設一個計算單元(包括計算節點或機群)邏輯編號為k，其計算能力為CPk；為所述計算單元分配CPk*M(*是乘法運算)任務量；再把CPk*M任務量均勻分配到邏輯編號為k+1，k+2，...，k+m的共m個計算單元上；這樣任務CPk*M被DG同時分配和執行兩次；在本發明中稱這種冗餘策略為m-冗餘分配策略；實際上，任務CPk*M只被冗餘分配一次。
為了解決上述技術問題，本發明所提供的一種網格環境下的大規模數據並行型計算算法，DGCS主要數據結構有如下部件構成設網格DG由c個計算機機群構成，每個機群內的計算節點的數目動態變化；DPC是DG上的一個數據並行型計算任務，|DPC|表示它的總任務量，W為其計算資源需求權重向量；QTDT為DPC的任務分布信息隊列；M為基本任務單元；DGSS為網格監控系統；大規模數據並行型算法的步驟如下1)初始化；a)根據M分解DPC；b)計算finished＝DPC的結束條件；c)廣播DPC的輔助數據(如係數矩陣)到DG的所有計算節點；d)Count＝0；/*並行計算次數計數器初始化*/2)While(當Finished未成立時)do
3)[DG的Master分布DPC任務]/*循環執行任務*/a)從DGSS獲取DG的資源狀態信息；b)構造DG的機群邏輯環；c)啟動所有機群構造各自的計算節點邏輯環；d)為每個計算節點計算動態二維地址；e)獲取各個機群的總體計算能力CCPi(0≤i≤c)；f)對每個機群CCi(0≤i≤c)做{計算CCPi/∑CCPj(0≤j≤c)比率；計算在機群CCi上分配的DPC的任務量Ti＝(CCPi/∑CCPj(0≤j≤c))*|DPC|/M；}；For i＝1 to cg)傳輸任務Ti到機群CCi；h)在機群環上按1-冗餘分配策略分配Ti到CCi的邏輯後繼的1個機群CCi+1上；i)End for；4)所有機群CCi(0≤i≤c)並行地做步驟5)~11)5)機群CCi根據其各個計算節點的綜合計算能力CPj(0≤j≤p，p為CCi的計算節點個數)計算每個計算節點對子任務Ti的承擔量，即如下a)For j＝1 to pb)Tij＝(CPj/∑CPk(0≤k≤p))*|Ti|/M；c)傳輸子任務Tij到計算節點Cj；d)在計算節點環上按m-冗餘分配策略分配Tij到Cj的後面的m個計算節點Cj+1，Cj+2，，…，Cj+m上；e)End for；/*計算節點上的數據分布結束*/6)機群的Master構造機群CCi的本次任務的局部任務分布信息隊列QTDTi；並發QTDTi送到DG的Master，DG的Master構造全局任務分布信息隊列QTDT；7)CCi的Master啟動其所轄的所有計算節點完成本次計算任務，重複做步驟8)9)10)；8)CCi的Master監控本機群QTDTi的任務完成的情況；接受其後繼機群對QTDTi的冗餘計算完成的情況；傳輸本機群對其前驅的冗餘計算的中間結果到其前驅機群；傳輸本機群QTDTi的計算中間結果DG的Master；9)如果((本QTDTi的計算結果，通過自身或其後繼節點全部得到)或(得到DG的Master的結束命令)/*DG的Master通過冗餘機群獲得全部中間結果*/)則結束本次子任務計算，並轉到步驟11)；10)如果CCi的Master從DGSS獲得某些計算節點失效，則{置該節點為失效狀態；按造m-冗餘分配策略，計算失效任務量，放入失效任務隊列；同時發送失效信息到DG的Master；}當某些計算節點完成自己的計算任務後，到失效任務隊列獲取相應任務繼續執行，直到失效隊列為空；
11)接受DG的Master的下一次任務分配；/*本次網格並行計算結束*/Count++；12)DG的Master根據全局QTDT匯總本次計算中間結果；修改算法結束條件；轉換中間結果為新的總體計算任務DPC；13)End while；14)輸出計算結果，通知所有計算節點結束本次計算。
所述步驟3)b)中的機群邏輯環，其構造步驟如下已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)，對DG的任意一個計算機機群CCi∈CSS，CCi的綜合計算能力是其所有計算節點的綜合計算能力的和，記為CCPj(0≤j≤c)；在DG中按照CCPi(0≤j≤c)的從大到小的順序對所有機群編號；按此編號構成一個機群邏輯環，編號最後的機群的邏輯後繼機群是編號為1的機群。
所述步驟3)c)中的計算節點邏輯環，其構造步驟如下已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)，對DG的任意一個計算機機群CCi∈CSS，其計算節點的個數為p，按照權重向量W計算出每個計算節點的綜合計算能力為CPj(0≤j≤p)；在CCi中按照CPj(0≤j≤p)的從大到小的順序對所有計算節點編號；按此編號構成一個計算節點邏輯環，編號最後的計算節點的邏輯後繼節點是編號為1的節點。
所述步驟3)d)中計算的動態二維地址，其設定為二元組(r，o)地址；DG上的每個計算節點都能從所構造的機群邏輯環和計算節點邏輯環中獲得一個二元組(r，o)地址，其中r為該計算節點所在機群的機群環編號，o為該計算節點在機群r的計算節點環中的邏輯編號；由於DG的機群環和計算節點環在並行計算過程中動態變化，所以稱(r，o)為該計算節點的動態二維地址。
所述步驟6)中的任務分布信息隊列所有基本單元任務的TDT構成一個任務分布信息隊列QTDT；DG有一個全局的QTDT，每個機群擁有一個局部的QTDTi。
所述步驟10)中的失效任務隊列對DG的每個計算機機群構造一個存放局部計算節點失效後的任務信息隊列，其格式同任務分布信息隊列一樣。
利用本發明提供的網格環境下的大規模數據並行型計算主系統，為基於網際網路的大規模數據並行型計算提供了一套可行的計算支持系統和實現方法。本發明是利用現有的計算機網絡、計算節點的空餘資源進行大規模並行計算，並且這些計算資源的結構、軟體系統可以是異構的，網絡互聯可以是任意技術的。通過調整基本任務塊的大小，根據網絡的實際情況來調整並行的粒度。通過動態計算各個計算資源的能力函數，動態構造計算機群環、計算節點環，然後根據m-冗餘策略均衡分配負載，使該系統支持的數據並行型算法具有良好的加速比、動態負載均衡性、有效的容錯能力。
所描述的基於動態冗餘機制的數據並行型算法的有效的容錯機制，分三步證明如下一、在單個機群中.不失一般性，只需證明該算法的平均容錯能力；假設單一機群內的每個計算節點的綜合計算能力相同，所以每個節點分配到的主計算任務都為T。這樣該節點的m個後繼計算節點各自冗餘存放該任務的T/m。設每個計算節點的失效概率為q。僅僅分析m+1個相鄰計算節點的失效分布情況以及失效隊列的數據量的大小。
當有1個節點失效時，失效數據為0；當有2個節點失效時，有(T/m)q2失效數據；當有3個節點失效時，有(T/m)q3失效數據；當有k個節點失效時，有(T/m)qk失效數據；……
那麼m個失效情況發生的平均失效數據量為Tave((T/m)(q2+2q3+3q4+…+(m-1)qm))/m＝(T/m2)(q2+2q3+3q4+…+(m-1)qm)＝T/(m2(1-q)2)-(T/m)(qm+1/(1-q))………(1)在公式(1)中，當q趨於0時，Tave＝T/m2；當q趨於0.5時，Tave≈1.33(T/m2)；如果一個機群的計算節點環可以被分為h個長度為m+1的部分，那麼該機群的平均失效隊列長度為h Tave，可見適當調整計算節點邏輯環的長度可以有效控制容錯隊列的長度。所以單一機群內的冗餘機制是有效的。
二、由於機群間採用1-冗餘策略，實際是鏡像策略。鏡像冗餘機制是有效的。
三、可以利用計算通信性能比來計算m-冗餘策略中的m。最佳冗餘信息量應該是使節點的計算能力恰好能夠與網絡通信能力平衡。
綜上所述，所描述的基於動態冗餘機制的數據並行型算法提供了有效的容錯機制。
關於所描述的數據並行型算法是動態負載均衡的證明在算法的步驟3)，每次並行計算啟動的初始階段，都根據當時DG的每個機群、每個計算節點的計算能力構造機群邏輯環、計算節點邏輯環。
根據兩個邏輯環的設定，根據算法步驟3)的描述，各個機群任務的負載是按能力所分的。同時，根據算法的步驟5)可知，每個機群內的負載分配也是按能力所分的。所以在算法的每個並行階段，負載均衡的。
另外，由於兩個邏輯環的構造是在每個並行階段實時構造的，所以這種負載分配是動態的。
所以，所描述的數據並行型算法是動態負載均衡的。
本發明的大規模數據並行型計算主系統是基於上述優點的，非常適合在普通計算機機群構成的網格環境下解決大規模計算問題，對利用現有的空餘計算資源實施高性能計算提出了有意義的有價值的系統實現技術、方法。本發明給出一個在由多計算機機群構成的數據網格環境下、面向數據並行型計算的、基於動態冗餘機制的大規模並行計算主系統和方法。理論分析和實踐表明該系統和方法具有良好的動態負載均衡性、容錯性和加速比特性，能有效地支持大規模數據並行型計算。


圖1是本發明的由雙邏輯環構成的動態網格DG示意圖；圖2是本發明的m-冗餘分配策略示意圖；圖3是多Agent模型運作機制中計算節點的狀態轉換示意圖。
具體實施例方式
以下結合

對本發明的實施例作進一步詳細描述，但本實施例並不用於限制本發明，凡是採用本發明的相似結構和方法及其相似變化，均應列入本發明的保護範圍。
為了構造支持大規模數據並行型計算的網格環境，利用普通的計算網絡、計算機資源構成多可信級別的網格計算系統，為了有效地描述該DGCS系統的實現方式，本說明書作如下設定設定1、計算機機群一個計算機機群(Computer Cluster)是一個二元組CC(Master，CS)，其中Master為CC主控制器；CS＝{C1，C2，...，Cp}為CC的所有計算節點的集合。
設定2、數據網格一個數據網格(Data Grid)為一個四元組DG(Master，CCS，N，R)；其中Master為DG主控制器；CSS＝{CC1，CC2，...，CCc}為計算機機群的集的集合；N＝{N1，N2，...，Nn}為連接網絡的集合，連接網絡是高速交換網；R為連接規則。每個DG中的計算節點具有獨立的處理器和外存儲器。
設定3、DG上的數據並行型計算一個DG(Master，CCS，N，R)上的一個數據並行型計算過程如下(1)計算任務規模、分解為子任務；
(2)啟動所有CCS中的計算節點；(3)計算Finish＝任務結束的條件；(4)i＝1；(5)While(當Finish未成立時)do(6)分解全局數據Data為D1，D2，...，Dp；(7)並行地發送Dk到Ck(1≤k≤p)；(8)驅動Ck(1≤k≤p)同時求解子任務i；(9)同步Ck(1≤k≤p)對子任務i的求解，交換局部數據形成新的全局數據New_Data；(10)Data＝New_Data；(11)i＝i+1；(12)End while；(13)合成計算結果；(14)通知Ck(1≤k≤p)結束計算；(15)結束本次計算。
設定4、資源需求權重向量DG中的每類數據並行型計算DPC(Data ParallelComputing)對計算節點的計算(CPU)性能、存儲(RAM)容量、I/O(DISK)速度的需求是不一樣的，對每類數據並行型計算進行分析，可以給出對上述三種資源的需求權重，用向量W＝(w1，w2，w3)表示，稱作該類DPC的資源需求權重向量。
設定5、計算通信性能比已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)。對DG的任意一個計算機機群CCi∈CSS，其計算節點的個數為p，按照權向量W計算出每個計算節點的綜合計算能力CPj(0≤j≤p)；設CCi網絡帶寬為B，那麼機群CCi對DPC的計算通信性能比設定為R＝∑CPj(0≤j≤p)/pB；其含義為機群CCi的計算節點的平均綜合處理能力和本機群網絡帶寬的比值。
由於目前一般網絡的通信帶寬一般為100M和1000M級別，而處理節點的綜合處理能力則提高的越來越快，所以R的值會大於1；至於計算節點能力的計算單位可以根據DPC的需求來設定，例如可以設每百兆赫茲處理器頻率為一個CPU單位，每兆存儲器為一個存儲單位，每毫秒的I/O速度作為硬碟的速度單位等。
在網格並行體系結構中，設定6、計算節點邏輯環已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)。對DG的任意一個計算機機群CCi∈CSS，其計算節點的個數為p，按照權向量W計算出每個計算節點的綜合計算能力為CPj(0≤j≤p)；在CCi中按照CPj(0≤j≤p)的從大到小的順序對所有計算節點編號；並按此編號構成一個計算節點邏輯環，編號最後的計算節點的邏輯後繼節點是編號為1的節點，稱該邏輯環為計算節點邏輯環。
通過設定可以知道，在計算節點邏輯環上除第1編號計算節點和最大編號節點之間外，越臨近的計算節點的綜合計算能力越相近。
設定7、機群邏輯環已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)。對DG的任意一個計算機機群CCi∈CSS，CCi的綜合計算能力是其所有計算節點的綜合計算能力的和，記為CCPj(0≤j≤c)。在DG中按照CCPi(0≤j≤c)的從大到小的順序對所有機群編號；並按此編號構成一個機群邏輯環，編號最後的機群的邏輯後繼機群是編號為1的機群，稱該邏輯環為機群邏輯環。
同樣，在機群邏輯環上除第1編號機群和最大編號機群之間外，越臨近的機群的綜合計算能力越相近。
參見圖1所示，由機群邏輯環1和計算節點邏輯環2雙環構成動態DG。
設定8、計算節點的動態二維地址DG上的每個計算節點都能從按照設定6、7所構造的兩個邏輯環中獲得一個二元組(r，o)地址，其中r為該計算節點所在機群的機群環編號，o為該計算節點在機群r的計算節點環中的邏輯編號，由於DG的機群環和計算節點環在並行計算過程中動態變化，所以稱(r，o)為該計算節點的動態二維地址。
設定9、基本任務單元已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)。根據DPC的特點，把DPC分解為若干個大小為M的任務塊，本說明書稱M為DPC在DG上的基本任務單元。
設定10、m-冗餘分配策略在一個邏輯環(機群環或計算節點環)上，設一個計算單元(計算節點或機群)邏輯編號為k，其計算能力為CPk。在為該計算單元分配CPk*M(*是乘法運算)任務量後，再把CPk*M任務量均勻分配到邏輯編號為k+1，k+2，...，k+m的共m個計算單元上，這樣任務CPk*M被DG同時分配和執行兩次，稱這種冗餘策略為m-冗餘分配策略，如圖2所示；實際上，在一個計算節點環3上，任務CPk*M只被冗餘分配一次。
設定11、任務分布信息表列對DG中的每個基本任務單元設定一個任務信息分布表TDT(Mlink，Slink)，其中Mlink為該任務單元的第一次分布的計算節點的動態二維地址鍊表，Slink為該任務單元的冗餘分布的計算節點的動態二維地址鍊表；任務分布信息隊列所有基本單元任務的TDT構成一個任務分布信息隊列QTDT。DG有一個全局的QTDT每個機群擁有一個局部的QTDTi。
失效任務隊列對DG的每個計算機機群構造一個存放局部計算節點失效後的任務信息隊列，其格式同任務分布信息隊列一樣。
網格監控系統為DGSS為了支持基於上述結構的DG上的數據並行型大規模並行算法的有效運行，必須有一個對DG實時有效動態的網格管理系統。利用多Agent合作機制研究了基於雙環結構的網格資源發現、監測、動態調整系統，可以保證DG系統的有效運行，有關該系統的描述和介紹參見本說明書最後部分；為了本說明書的描述，記該系統的名字為DGSS(DG Supervise System)。
本發明實施例所提供的一種網格環境下的大規模數據並行型計算主系統，設網格DG由c個計算機機群構成，每個機群內的計算節點的數目動態變化；DPC是DG上的一個數據並行型計算任務，|DPC|表示它的總任務量，W為其計算資源需求權重向量；QTDT為DPC的任務分布信息隊列；M為基本任務單元；DGSS為網格監控系統；大規模數據並行性算法描述如下1)初始化；a)根據M分解DPC；b)計算finished＝DPC的結束條件；c)廣播DPC的輔助數據(如係數矩陣)到DG的所有計算節點；d)Count＝0；/*並行計算次數計數器初始化*/2)While(當Finished未成立時)do3)[DG的Master分布DPC任務]/*循環執行任務*/a)從DGSS獲取DG的資源狀態信息；b)構造DG的機群邏輯環；c)啟動所有機群構造各自的計算節點邏輯環；d)為每個計算節點計算動態二維地址；e)獲取各個機群的總體計算能力CCPi(0≤i≤c)；f)對每個機群CCi(0≤i≤c)做{計算CCPi/∑CCPj(0≤j≤c)比率；計算在機群CCi上分配的DPC的任務量Ti＝(CCPi/∑CCPj(0≤j≤c))*|DPC|/M；}；For i＝1 to cg)傳輸任務Ti到機群CCi；
h)在機群環上按1-冗餘分配策略分配Ti到CCi的邏輯後繼的1個機群CCi+1上；i)End for；4)所有機群CCi(0≤i≤c)並行地做步驟5)~11)5)機群CCi根據其各個計算節點的綜合計算能力CPj(0≤j≤p，p為CCi的計算節點個數)計算每個計算節點對子任務Ti的承擔量，即如下a)For j＝1 to pb)Tij＝(CPj/∑CPk(0≤k≤p))*|Ti|/M；c)傳輸子任務Tij到計算節點Cj；d)在計算節點環上按m-冗餘分配策略分配Tij到Cj的後面的m個計算節點Cj+1，Cj+2，，…，Cj+m上；e)End for；/*計算節點上的數據分布結束*/6)機群的Master構造機群CCi的本次任務的局部任務分布信息隊列QTDTi；並發QTDTi送到DG的Master，DG的Master構造全局任務分布信息隊列QTDT；7)CCi的Master啟動其所轄的所有計算節點完成本次計算任務，重複做步驟8)9)10)；8)CCi的Master監控本機群QTDTi的任務完成的情況；接受其後繼機群對QTDTi的冗餘計算完成的情況；傳輸本機群對其前驅的冗餘計算的中間結果到其前驅機群；傳輸本機群QTDTi的計算中間結果DG的Master；9)如果((本QTDTi的計算結果，通過自身或其後繼節點全部得到)或(得到DG的Master的結束命令)/*DG的Master通過冗餘機群獲得全部中間結果*/)則結束本次子任務計算，並轉到步驟11)；10)如果CCi的Master從DGSS獲得某些計算節點失效，則{置該節點為失效狀態；按造m-冗餘分配策略，計算失效任務量，放入失效任務隊列；同時發送失效信息到DG的Mastēr；}當某些計算節點完成自己的計算任務後，到失效任務隊列獲取相應任務繼續執行，直到失效隊列為空；11)接受DG的Master的下一次任務分配；/*本次網格並行計算結束*/Count++；12)DG的Master根據全局QTDT匯總本次計算中間結果；修改算法結束條件；轉換中間結果為新的總體計算任務DPC；13)End while；14)輸出計算結果，通知所有計算節點結束本次計算。
具體實施例方式異構環境的有效開發環境是Web Service技術。本發明實施例利用微軟.Net和sun公司的SunOne技術作為開發環境、技術，開發了該系統。並進行了有效的分析、測試工作。
為了檢驗該算法的有效性，本發明實施例對線形方程組的一般迭代法[13]解法，進行了分解，然後從加速比和容錯性兩個方面進行了測試。
網格DG由8個機群構成，每個機群有6個計算節點，網絡由8個100M交換機級聯構成。
本發明實施例把計算節點分為3類，每類配置情況如表1所示，每個機群內每類計算節點各有2個。
表1.各類計算節點配信息

本發明實施例對個5000×5000係數矩陣的方程組，分別以1000次作為一次完整地計算。DPC是一般迭代法。基本任務單元M為求解向量的一個分量。取m-冗餘策略中的m＝2。測試分別在1~8個機群的情況下進行，測試結果如表2所示。從數據可以看出，該算法的加速比是近線性的。
表2.算法的加速比

為了測試該模型的容錯能力，本發明實施例分別在4個不同的時段，在計算資源的不同負載情況下對上述試驗各執行100次，來查看算法的完全失效率(不能正常完成計算的比率)。結果表明，即使在DG繁忙的高峰上午和下午，該算法的完全失效率也是很低的，說明該算法的容錯功能是有效的。測試結果如表3所示。
表3.不同時段的完全失效率

由於迭代法的並行各個階段的通信量不是太大，並且數據量穩定，該算法表現了良好的加速比。對並行階段通信量比較大並且數據量不穩定的並行JOIN[12]算法的測試工作正在進行，將另出論文描述。在基於網格的數據並行計算的大規模並行算法的實現中，動態負載均衡和有效的容錯機制十分重要。本文提出的動態冗餘策略、網格資源的動態應用策略、基於邏輯環的負載均衡策略有效地解決了這個問題。在實踐中本說明書發現，要想獲得穩定的網格計算資源，還需要有效的環境管理機制(如多Master技術、機房管理策略等)、硬體容錯策略等提供保證。
為了有效地說明本發明的網格環境下的大規模數據並行型計算主系統及方法，本說明書對利用多Agent合作機制的網絡監控系統DGSS(DATA GRID SUPERVISESYSTEM)作如下描述一、基本結構設定設定1、計算機機群，一個計算機機群(Computer Cluster)是一個二元組CC(Master，CS)，其中Master為CC主控制器；CS＝{C1，C2，…，Cp}為CC的所有計算節點的集合。
設定2、數據網格，一個數據網格(Data Grid)為一個四元組DG(Master，CCS，N，R)；其中Master為DG主控制器；CSS＝{CC1，CC2，…，CCc}為計算機機群的集的集合；N＝{N1，N2，…，Nn}為連接網絡的集合，連接網絡是高速交換網；R為連接規則。每個DG中的計算節點具有獨立的處理器和外存儲器。
設定3、DG上的數據並行型計算，一個DG(Master，CCS，N，R)上的一個數據並行型計算過程如下(1)計算任務規模、分解為子任務；(2)啟動所有CCS中的計算節點；(3)n＝子任務數；(4)i＝1；(5)分解數據Data為D1，D2，…，Dp；(6)發送Dk到Ck(1≤k≤p)；
(7)While i＜n do(8)驅動Ck(1≤k≤p)同時求解子任務i；(9)同步Ck(1≤k≤p)對子任務i的求解；(10)i＝i+1；(11)End while；(12)回收Ck(1≤k≤p)的計算結果，併合成；(13)通知Ck(1≤k≤p)結束計算；(14)結束本次計算。
設定4、多Agent合作模型，DG中的多Agent合作模型MS可以形式化的設定為一個四元組MS＝(Agents，Tm，Sm，Space)，其中Agents是所有合作實體Agent的集合；Tm為Agent間的通信機制；Sm為Agent間的服務機制；Space為所有Agent的存在空間。
設定5、Agent，一個Agent可以用一個四元組描述Agent＝(Aid，Atype，Aarea，Adesc，ABDI，Aprg)，其中Aid為Agent的唯一標誌符；Atype為Agent的類型；Aarea為Agent在網格上的活動範圍，Adesc為Agent的描述向量。ABDI為Agent的信念、願望、意圖等規則庫；Aprg為Agent的可執行代碼。
根據基於網格的數據並行計算的需求，本說明書對網格中的Agent做了如下分類設定6、資源管理智能體Arm，DG(Master，CCS，N，R)上的資源管理智能體Arm是在CCS的所有計算節點上的、用於資源的動態改變管理；其信念是所在計算節點是最具有能力的；其願望是挖掘所在節點的計算、存儲、通信能力，儘可能提高其所在計算節點在網格中的重要作用；其意圖是根據本節點的資源狀況、狀態，與網格中其它Agent合作、競爭，達到其所轄計算節點的優化工作狀態。
設定7、可靠性管理智能體Aa，DG上的可靠性管理智能體Aa是存在於在CCS的所有計算節點上的、用於資源的穩定性狀態檢測，主要檢測其所在計算節點的CPU資源、內存資源、網絡資源、各種服務的工作狀態，並根據這些狀態的數據來修正所在計算節點地可靠性參數；其信念是相信所在計算節點會出現各種故障；其願望是發現所在節點的計算、存儲、通信故障，儘可能降低其所在計算節點在網格中的重要作用，其與Arm是相矛盾的；其意圖是根據本節點的資源狀態信息，與網格中其它Agent合作、競爭，達到其所轄計算節點的優化工作狀態。
設定8、機群管理智能體Acc，DG上的機群管理智能體Acc是存在於在CCS中每個機群的Master上、用來對其所轄所有計算節點的能力進行綜合管理，根據其計算、存儲、通信、服務能力等進行綜合排隊、管理，同時負責與其他機群的Acc協調、合作工作；其信念是相信其所轄機群能力是最強的；其願望是發現所轄機群的儘可能奪得計算、存儲、通信、服務資源，儘可能提高其所在網格中的重要作用；其意圖是根據本機群的資源狀態信息，與網格中其機群的Acc合作、競爭，達到其所轄機群的優化工作狀態。
設定9、用戶代理智能體Auser，DG上的網格管理智能體Auser是存在於在DG的Master上、用來代理用戶的服務請求，根據請求的計算、存儲、通信、服務等要求，負責與機群的Agrid協調、合作工作。
設定10、網格管理智能體Agrid，DG上的網格管理智能體Agrid是存在於在DG的Master上、用來對其所轄所有機群的能力進行綜合管理，根據所有機群的計算、存儲、通信、服務能力等進行綜合排隊、管理，同時負責與機群的Acc協調、合作工作；其信念是相信其所轄網格能力是最強的；其願望是發現所轄網格的儘可能多的計算、存儲、通信、服務資源，儘可能提高網格的吞吐率和效率；其意圖是根據本網格的資源狀態信息，與服務代理Agent合作，達到其所轄網格的優化工作狀態。
設定11、網格服務智能體Aservice，DG上的網格服務智能體Aservice是存在於在DG的所有計算節點上、用來完成並行計算的特定的計算功能，如設定3的第(8)的子任務求解問題，其主要和不同的計算問題的並行分解相關，是網格對外並行服務的重要部分，其往往是一個智能體集合，本說明書計DG上的網格服務智能體集合為SAS。
每個網格服務智能體都有自己的BDI，一般情況下，一個Aservice的信念是相信其能提供最好的服務；其願望是儘可能多的提供自身的服務；其意圖是尋找所在網格上的對自己有益的最佳資源，並遷移到最佳資源節點，進行優化服務。
二、多Agent模型運作機制由於DG的構成特點，隨著計算機群數目、網絡數目、計算節點的數目的增加，網格的可靠性問題變得非常重要，因此必須有一套有效的容錯機制。檢測點容錯機制在傳統的系統容錯上扮演了重要角色，但該容錯機制會產生多米諾效應，不適合基於網格的大規模計算應用。本說明書利用動態冗餘機制、多Agent合作機制解決了該問題。容錯技術也是本說明書這個合作模型主要考慮的問題。
冗餘容錯機制就是對一個重要的網格服務子任務由分布在不同計算節點上的、多個同功能的網格服務智能體共同實施完成，其中一個為第一完成者，其它為後備完成者；當第一完成者失效後，由後備完成者接替，這樣可以避免單一失效點造成的網格性能下降的後果。
1)網格服務智能體狀態DG上的一個網格服務智能體被分為三個狀態主態、備態、沉睡。在服務過程中，當一個網格服務智能體為第一完成者，本說明書稱該服務智能體為主態智能體；當一個網格服務智能體為後備完成者，本說明書稱該服務智能體為備態智能體；如果一個服務智能體在一個計算節點中從不參與服務，本說明書稱該服務智能體為沉睡智能體。
2)網格計算節點的狀態DG上的一個計算節點Ci有四個狀態主態、容態、備態、失效。在確定的時期內，如果計算節點Ci上的所有非沉睡服務智能體都處於主態，那麼稱該計算節點為主態節點；如果計算節點Ci上的非沉睡服務智能體主態和備態並存，那麼稱該計算節點為容態節點；如果計算節點Ci上的所有服務智能體都處於備態，那麼稱該計算節點為備態節點；如果計算節點Ci上的所有服務智能體都處於沉睡狀態，那麼稱該計算節點為失效節點。
3)網格節點隊列針對網格的計算節點的上述的4個狀態，本說明書在網格DG上構造4個節點隊列，分別是主態隊列Qmaster、容態隊列Qslave、備態隊列Qbak、失效隊列Qfailure。這4個隊列的長度分別記為LQmaster、LQslave、LQbak、LQfailure。
按照設定6~11所描述的各類Agent的BDI，所有Agent通過合作、競爭目的是使各自所服務的計算節點、計算機機群儘可能發揮主要作用，即儘可能處於網格的主態隊列中；按照這種驅動機制，本說明書把四個隊列按優先級排隊如下主態隊列＞容態隊列＞備態隊列＞失效隊列根據這個原則，本說明書給出計算節點的狀態轉換機制，網格計算節點的狀態轉換模型如圖3所示。
4)多Agent合作規則A)資源管理智能體Arm規則一個網格計算節點Ci的性能的衡量參數一般可包括下面四個方面①Ci當前可提供的CPU計算能力Pcpu②Ci當前可提供的內存存儲能力Pmem③Ci當前可提供的網絡通信能力Pnet④Ci當前可提供的磁碟I/O能力PI/O資源管理智能體Arm負責動態監測計算節點Ci四個參數Pcpu、Pmem、Pnet、PI/O的變化，利用它們構成計算節點當前時刻的能力函數
Pnode＝f(Pcpu，Pmem，Pnet，PI/O)…………(1)設本計算節點的上一時刻的能力函數值為PLnode，資源管理智能體Arm利用公式(1)計算當前時刻的能力函數值PCnode。
規則1、資源管理智能體Arm規則，如果PCnode＞PLnode，則Arm向ACC申請向上一級計算節點狀態轉變。
B)可靠性管理智能體Aa規則一個網格計算節點Ci的可靠性能的衡量參數一般可包括有下面兩個方面①當前節點的正常狀態標誌器Pmark；當計算節點正常時，其值為1；當計算節點失效時，其值為0；②計算節點成功完成網格服務智能體的比率Psucc＝計算節點成功完成的服務數目/計算節點接受的服務數目。設l1、l2、l3為三個小數，並且0＜l1＜l2＜l3＜1，那麼規則2、可靠性管理智能體Aa規則，如果計算節點Ci的Pmark為false，則Arm向ACC通報Ci變為失效狀態；如果Psucc∈(0，L1)，則Ci變為失效狀態；如果Psucc∈(L1，L2)，則Ci變為後備狀態；如果Psucc∈(L2，L3)，則Ci變為容態狀態；如果Psucc∈(L3，1)，則Ci變為主態狀態；C)機群管理智能體Acc規則一個機群CCi的性能的衡量參數如下Pcci＝CCi所屬計算節點為主態的數目/LQmasterPcci反映了機群CCi在DG中的主態計算節點的分布情況，Pcci越大，說明CCi的作用越大。
對於整個DG而言，Pcc1+Pcc2+…+Pccm＝1。
CCi的Acc接收來自機群CCi所有計算節點上的Arm、Aa定期發來的Pnode、Pmark、Psucc；
同時利用心跳偵測技術檢測所有節點的有效狀態。
機群CCi的當前時刻的能力函數PCCC＝g(∑Pnode，∑Pmark，∑Psucc)…………(2)這裡∑表示綜合機群CCi所有計算節點的參數。PCCC表示機群的計算節點在DG的主態隊列Qmaster中的數目。
設機群CCi的上一時刻的能力函數值為PLCC，機群管理智能體Acc利用公式(2)計算當前時刻的能力函數值PCcc。
規則3、機群管理智能體Acc規則，如果CCi的計算節點Ci的Pmark為false，則令Ci變為失效狀態；如果PCcc＞PLcc或PCcc＜PLcc，則Acc向Agrid申請計算節點狀態轉變。
D)網格管理智能體Agrid規則Agrid接收來自DG所有機群的Acc定期發來的Pnode、Pmark、Psucc、PCcc；根據如下規則分配LQmaster規則4、網格管理智能體Agrid主態隊列的分配，for i＝1 to c對機群CCi的所有主態計算節點按其提供的資源Pnode從大到小排序，形成臨時隊列Qcci；每個機群分配一個計數器CCount[i]＝0；End for；Pcount＝LQmaster；For i＝1 to c/*c為網格DG的機群個數*/取機群CCi的PCcc；If CCount[i]＜PCccthen取機群CCi的臨時隊列Qcci中最大的計算節點加入主態隊列Qmaster，，並從Qcci刪除該計算節點；CCount[i]++；/*機群CCi的主態節點計數器加1*/Pcount--；/*分配一個主態節點指標*/End if；End for；For i＝1 to c取機群CCi的臨時隊列Qcci中剩餘的計算節點加入網格的容態隊列；End for；Agrid廣播新的主態、容態、備態、失效信息到所有機群和計算節點；在圖3中，5、6和7分別為多Agent合作規則中的資源管理智能體Arm規則、可靠性管理智能體Aa規則和機群管理智能體Acc規則。
本分配規則是根據各個機群當前時刻的能力採用round-robin機制分配，使得每個機群的主態節點數目符合其計算能力，這樣可以發揮各個計算節點的實際計算效能，同時又使負載在網格上均衡分布，有利於網格規模的可擴展性的提高。
權利要求
1.一種網格環境下的大規模數據並行型計算主系統，包括一個網格監控系統DGSS，利用多Agent合作機制對DG實施有效動態的狀態監控的網格管理系統；其特徵是，還包括由機群邏輯環構成的一個網格計算系統DGCS，其中所述機群邏輯環由設定編號的計算機機群按編號順序邏輯聯接構成，編號最後的機群的邏輯後繼機群是編號為1的機群；所述編號是根據計算機機群的所有計算節點的綜合計算能力的和按從大到小的順序對所有機群進行設定的編號；所述機群邏輯環上的各個計算機機群由計算節點邏輯環構成，所述計算節點邏輯環由設定編號的計算節點按編號順序邏輯聯接構成，編號最後的計算節點的邏輯後繼節點是編號為1的計算節點；所述編號是根據每個計算節點的綜合計算能力按從大到小的順序對所有計算節點進行設定的編號，所述每個計算節點的綜合計算能力是按照權重向量W計算出來的；由機群邏輯環和計算節點邏輯環構成了動態數據網格計算系統；所述網格監控系統通過普通的Lan或Intranet監管和連接所述動態網格計算系統的每個計算機機群和計算節點。
2.一種網格環境下的大規模數據並行型計算主系統的m-冗餘分配策略，其步驟如下在一個計算機機群環或計算節點環上，設一個計算機機群或計算節點的計算單元，邏輯編號為k，其計算能力為CPk；為所述計算單元分配CPk*M任務量；其特徵是，再把CPk*M任務量均勻分配到邏輯編號為k+1，k+2，...，k+m的共m個計算單元上；這樣任務CPk*M被DG同時分配和執行兩次。
3.一種網格環境下的大規模數據並行型計算算法，其DGCS主要數據結構有如下部件構成設網格DG由c個計算機機群構成，每個機群內的計算節點的數目動態變化；DPC是DG上的一個數據並行型計算任務，|DPC|表示它的總任務量，W為其計算資源需求權重向量；QTDT為DPC的任務分布信息隊列；M為基本任務單元；DGSS為網格監控系統；其特徵是，大規模數據並行型算法的步驟如下1)初始化a)根據M分解DPC；b)計算finished＝DPC的結束條件；c)廣播DPC的輔助數據到DG的所有計算節點；d)並行計算次數計數器Count＝0；2)While(當Finished未成立時)do3)執行任務a)從DGSS獲取DG的資源狀態信息；b)構造DG的機群邏輯環；c)啟動所有機群構造各自的計算節點邏輯環；d)為每個計算節點計算動態二維地址；e)獲取各個機群的總體計算能力CCPi(0≤i≤c)；f)對每個機群CCi(0≤i≤c)做{計算CCPi/∑CCPj(0≤j≤c)比率；計算在機群CCi上分配的DPC的任務量Ti＝(CCPi/∑CCPj(0≤j≤c))*|DPC|/M；}；g)For i＝1 to ch)傳輸任務Ti到機群CCi；i)在機群環上按1-冗餘分配策略分配Ti到CCi的邏輯後繼的1個機群CCi+1上；j)End for；4)所有機群CCi(0≤i≤c)並行地做步驟5)~11)5)機群CCi根據其各個計算節點的綜合計算能力CPj(0≤j≤p，p為CCi的計算節點個數)計算每個計算節點對子任務Ti的承擔量，即如下a)For j＝1 to pb)Tij＝(CPj/∑CPk(0≤k≤p))*|Ti|/M；c)傳輸子任務Tij到計算節點Cj；d)在計算節點環上按m-冗餘分配策略分配Tij到Cj的後面的m個計算節點Cj+1，Cj+2，...，Cj+m上；e)End for；6)機群的Master構造機群CCi的本次任務的局部任務分布信息隊列QTDTi；並發QTDTi送到DG的Master，DG的Master構造全局任務分布信息隊列QTDT；7)CCi的Master啟動其所轄的所有計算節點完成本次計算任務，重複做步驟8)9)10)；8)CCi的Master監控本機群QTDTi的任務完成的情況；接受其後繼機群對QTDTi的冗餘計算完成的情況；傳輸本機群對其前驅的冗餘計算的中間結果到其前驅機群；傳輸本機群QTDTi的計算中間結果DG的Master；9)如果((本QTDTi的計算結果，通過自身或其後繼節點全部得到)或(得到DG的Master的結束命令))則結束本次子任務計算，並轉到步驟11)；10)如果CCi的Master從DGSS獲得某些計算節點失效，則{置該節點為失效狀態；按造m-冗餘分配策略，計算失效任務量，放入失效任務隊列；同時發送失效信息到DG的Master；}當某些計算節點完成自己的計算任務後，到失效任務隊列獲取相應任務繼續執行，直到失效隊列為空；11)接受DG的Master的下一次任務分配；/*本次網格並行計算結束*/Count++；12)DG的Master根據全局QTDT匯總本次計算中間結果；修改算法結束條件；轉換中間結果為新的總體計算任務DPC；13)End while；14)輸出計算結果，通知所有計算節點結束本次計算。
4.根據權利要求3所述的大規模數據並行型計算算法，其特徵是，所述步驟3)b)中的機群邏輯環，其構造步驟如下已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)，對DG的任意一個計算機機群CCi∈CSS，CCi的綜合計算能力是其所有計算節點的綜合計算能力的和，記為CCPj(0≤j≤c)；在DG中按照CCPi(0≤j≤c)的從大到小的順序對所有機群編號；按此編號構成一個機群邏輯環，編號最後的機群的邏輯後繼機群是編號為1的機群。
5.根據權利要求3所述的大規模數據並行型計算算法，其特徵是，所述步驟3)c)中的計算節點邏輯環，其構造步驟如下已知給定的DG中的一類DPC及其資源需求權重向量W＝(w1，w2，w3)，對DG的任意一個計算機機群CCi∈CSS，其計算節點的個數為p，按照權重向量W計算出每個計算節點的綜合計算能力為CPj(0≤j≤p)；在CCi中按照CPj(0≤j≤p)的從大到小的順序對所有計算節點編號；按此編號構成一個計算節點邏輯環，編號最後的計算節點的邏輯後繼節點是編號為1的節點。
6.根據權利要求3所述的大規模數據並行型計算算法，其特徵是，所述步驟3)d)中計算的動態二維地址，其設定為二元組(r，o)地址；DG上的每個計算節點都能從所構造的機群邏輯環和計算節點邏輯環中獲得一個二元組(r，o)地址，其中r為該計算節點所在機群的機群環編號，o為該計算節點在機群r的計算節點環中的邏輯編號。
7.根據權利要求3所述的大規模數據並行型計算算法，其特徵是，所述步驟6)中的任務分布信息隊列所有基本單元任務的TDT構成一個任務分布信息隊列QTDT；DG有一個全局的QTDT，每個機群擁有一個局部的QTDTi。
8.根據權利要求3所述的大規模數據並行型計算算法，其特徵是，所述步驟10)中的失效任務隊列對DG的每個計算機機群構造一個存放局部計算節點失效後的任務信息隊列，其格式同任務分布信息隊列一樣。
全文摘要
本發明公開了一個網格環境下的大規模數據並行型計算主系統和方法。所述系統通過普通的Lan或Intranet連接的多個計算機機群構成，每個計算機機群、計算節點是異構的和多可信級別的；按計算節點的綜合計算能力從大到小的順序對所有計算節點編號，並按此編號構成一個計算節點邏輯環；按計算機機群的綜合計算能力從大到小的順序對所有機群編號，並按此編號構成一個機群邏輯環；所述機群邏輯環上的各個計算機機群由計算節點邏輯環構成；本發明提出的基於動態冗餘機制的數據並行型計算算法，利用對計算機機群構建動態邏輯環、對計算節點構建動態邏輯環和m－冗餘分配策略，有效地解決了動態冗餘、動態負載均衡、線形加速比等技術問題。
文檔編號G06F15/16GK1687917SQ200510025730
公開日2005年10月26日 申請日期2005年5月11日 優先權日2005年5月11日
發明者陳慶奎, 那麗春, 圖佔樂 申請人:上海理工大學