基于二元決策圖的集群計算系統性能分析

許美玲，喬 瑩，莫毓昌，鐘發榮

(浙江師范大學 數理與信息工程學院，浙江 金華 321004)

(*通信作者電子郵箱1933785432@qq.com)

基于二元決策圖的集群計算系統性能分析

許美玲*，喬 瑩，莫毓昌，鐘發榮

(浙江師范大學 數理與信息工程學院，浙江 金華 321004)

(*通信作者電子郵箱1933785432@qq.com)

針對節點計算能力相同但故障分布不同的集群系統的性能分析問題，基于k-to-l-out-of-n結構對集群系統的性能進行建模，并提出了一種基于二元決策圖(BDD)的分析方法。針對k-to-l-out-of-n結構的BDD模型生成問題，分析了BDD的結構特征并設計自頂向下生成算法,克服了傳統的自底向上生成算法必須生成大量中間冗余節點的缺陷；然后利用生成的BDD模型高效地計算出系統處于一個特定性能級別的概率；最后通過實例說明了BDD方法能夠有效分析節點具有不同故障分布的集群系統性能。

集群計算系統；k-to-l-out-of-n模型；二元決策圖

0 引言

現代計算機集群系統包含大量計算節點，這些節點可以是處于分布式環境下或不同管理域中的獨立計算機，例如云計算系統或網格計算系統[1-2]，也可以是由Infiniband或三維torus 互聯系統連接的單獨處理器，例如超級計算系統[3-5]。

假設pi表示節點Ni的計算能力，由n個節點組成的計算系統，其計算能力MP表示為MP=p1+p2+…+pn。節點出現故障會導致計算系統性能降低，即節點Ni出現故障，系統的計算能力將變為MP-pi。若節點具有相同的計算能力p，則系統所能呈現的狀態數量共有n+1種情況，計算能力分別為0,p,2p, …,np，其中：0表示所有節點都發生故障，np表示所有節點都正常運行。需要說明的是，本文考慮的集群系統滿足：集群的整體性能可以近似為各節點計算能力之和，例如具有前端分發節點的n節點Web集群。當然還存在其他很多分布式計算應用，n個節點之間需要進行進一步的交互以完成計算。對于這些交互應用,“n節點集群計算能力是各節點計算能力之和”這一條件將不滿足，該類型集群系統的性能分析研究不屬于本文的研究范圍。

當節點具有相同計算能力時，將計算能力歸一化處理，基于k-to-l-out-of-n結構對系統性能進行建模分析，在k-to-l-out-of-n結構的n個節點中，需要不少于k個但不多于l個可以正常運行的節點[6-7]。分析系統性能時，所有性能狀態可以分成若干種不同情況：L1,L2, …,Lm。例如由n個節點組成的計算系統，如果每個節點的計算能力都為p，采用平均劃分的方法，可以把系統性能級別從高到低一共劃分若干個級別。例如對于n個節點系統其性能可以簡單劃分為5個級別，為了進行區分可以分別命名為：極低(0≤P≤np/5-1)，低(np/5≤P≤2np/5-1)，中等(2np/5≤P≤3np/5-1)，高(3np/5≤P≤4np/5-1)，極高(4np/5≤P≤np)。其中極高性能級別包含n個節點全部正常工作的情況；而極低性能級別包含n個節點全部失效的情況。系統的性能分析可表示為系統處于一個特定性能的概率計算，即計算系統性能P落在某個區間內的概率。上述例子中極低、低、中等、高、極高五種情況分別對應以下結構：0-to-(n/5-1)-out-of-n,n/5-to-(2n/5-1)-out-of-n, 2n/5-to-(3n/5-1)-out-of-n,3n/5-to-(4n/5-1)-out-of-n,4n/5-to-n-out-of-n。

當節點數量較大時，采用狀態窮舉的方法效率較低,此時可以采用含非邏輯的非單調關聯故障樹分析方法[8]。基于質蘊含的非單調關聯故障樹分析與基于最小割集的單調關聯故障樹分析類似，同樣存在指數復雜性[9]問題。最近，一些基于二元決策圖(Binary Decision Diagram, BDD)[10]的組合方法開始應用于故障樹分析[11-14]。與其他方法相比，基于二元決策圖的方法顯得更加有效，因為BDD可以有效描述布爾函數，并且BDD上的操作可以高效地實現各種布爾運算。但現有的一些基于BDD的方法使用自底向上BDD生成算法，容易產生大量冗余的中間節點，而且這些方法也很難利用k-to-l-out-of-n模型的特殊結構，因此并不能提高模型的生成效率。

本文使用基于BDD的分析方法，對具有k-to-l-out-of-n結構的大型集群系統進行性能分析。在任務執行期間，集群及其節點都是不可修復的。針對節點計算能力相同但故障分布不同的集群，利用k-to-l-out-of-n結構下BDD模型所具有的特殊結構特征，設計了自頂向下BDD生成算法，避免了傳統自底向上BDD生成算法中大量中間節點的生成。

1 問題描述

形式上，二進制隨機變量Xi表示節點Ni的狀態，Xi=1表示節點Ni處于非故障狀態，Xi=0表示節點Ni處于故障狀態;由n個節點組成的計算系統，用X=(X1,X2,…,Xn)表示隨機的系統狀態向量。因為每個節點Ni有兩種狀態(故障狀態或非故障狀態)，所以由n個節點組成的計算系統有2n種可能的狀態。

x=(x1,x2,…,xn)表示系統狀態，xi表示節點Ni的狀態。系統在任務時間t內處于狀態x的概率計算公式如下：

(1)

Fi(t)表示節點Ni在任務時間t內處于Xi=0(故障狀態)時的概率。

系統在任務時間t內處于狀態x的計算能力P的計算公式如下：

(2)

系統在任務時間t內以特定性能L運行的概率，用計算能力P落在區間[LB,UB]內的概率表示，LB表示下限，UB表示上限，計算公式如下：

(3)

本文討論的問題是如何在特定任務時間t內計算ΦL，作以下假設：

1)計算節點之間相互獨立運行，即在整個系統中，一個節點事件(比如節點出現故障)的發生不會影響另一個節點事件的發生;

2)每個節點處于每個狀態的概率可以通過給定參數直接計算獲得,即本文只考慮系統級的性能分析，部件級的性能分析不在本文討論范圍內;

3)系統在使用時不可修復，即節點一旦從非故障狀態轉換到故障狀態，在剩余任務時間內該節點都處于故障狀態。

2 實例說明

實例系統由6個計算節點組成：N1,N2,…,N6，任務持續時間為100 h。為了說明集群的各個節點具有不同壽命分布，假設節點N1、N2、N3服從參數為λ的指數故障分布，累積分布函數Fi(t)如下：

Fi(t)=1-exp(-λit)

(4)

假設節點N4、N5、N6服從參數為λ和β的Weibull故障分布，累積分布函數Fi(t)如下：

Fi(t)=1-exp(-(λit)βi)

(5)

表1顯示了任務時間為100h，參數λi和βi分別為給定值時，使用式(4)或(5)計算得出的Fi(t)。

表1 節點參數和計算所得的Fi(t)

節點Ni的計算能力為pi，實例系統的最大計算能力MP表示為MP=p1+p2+p3+p4+p5+p6。不失一般性，系統性能P的三種性能分別定義為：低LL(LBL≤P≤UBL)，中LM(LBM≤P≤UBM)，高LH(LBH≤P≤UBH)，LBi(i∈{L,M,H)表示下限，UBi(i∈{L,M,H)表示上限。

當節點相同且計算能力也相同時，將pi歸一化處理。表2顯示了對應三種性能的LB和UB值，以及對應的k-to-l-out-of-n模型。

表2 不同性能下的參數設置(pi相同)

本文所研究的集群系統性能分析問題可以描述為：在任務時間內，分析集群系統在表1和表2的參數設置下，系統處于性能狀態LL、LM和LH的概率。需要注意的是，本文關注的是在特定時間內的概率計算，而不是處于穩定狀態或長期運行狀態的概率計算。

3 基于BDD的性能分析方法

本文提出一種基于BDD的性能分析方法對節點計算能力相同的集群系統進行性能分析。該方法由兩個步驟組成：1)使用k-to-l-out-of-n結構生成BDD模型；2)分析BDD模型并得到系統性能評估指標。

3.1 生成BDD模型

每個二狀態節點Ni的狀態空間存在兩種互斥的狀態：0表示故障狀態，1表示非故障狀態。如圖1所示，BDD模型中每個節點Ni都有兩條輸出邊：then-edge用1表示(非故障狀態)，else-edge用0表示(故障狀態)。

圖1 與Ni關聯的BDD節點

Fig.1BDDnodeassociatedwithNi

由表2可知，2-to-4-out-of-6模型表示LM，該模型生成的BDD結構如圖2所示。

圖2 2-to-4-out-of-6模型的BDD結構

BDD結構中有兩種葉子節點(正方形表示葉子節點)：葉子節點“1”表示系統性能為LM，而葉子節點“0”表示系統性能不為LM，比如計算能力高于UBM或者低于LBM的情況。例如，當節點N1,N2, …,N5都處于0狀態(故障狀態)，無論節點N6處于什么狀態，系統的計算能力都低于LBM，即系統性能不為LM。這種情況下的路徑與葉子節點“0”相連(如圖2中頂部的水平路徑所示)。另一種情況，當節點N1,N2, …,N5都處于1狀態(非故障狀態)，無論節點N6處于什么狀態，系統的計算能力都高于UBM，即系統性能不為LM。這種情況下的路徑也與葉子節點“0”相連(如圖2中最左側的垂直路徑所示)。

總之，對任何基于k-to-l-out-of-n結構的計算系統進行BDD建模，如果節點計算能力相同，那么BDD模型可以由以下引理推導得到：

引理 基于k-to-l-out-of-n結構的計算系統，性能為Li時對應的BDD模型如圖3所示，即一個(l+1)*(n-k+1)的矩陣去除右下角 (l-k+1)*(l-k+1)的矩陣后剩余的部分。

圖3 基于k-to-l-out-of-n結構的BDD模型

證明 在性能為Li的BDD模型中，即系統計算能力P的取值范圍是[LBi,UBi]，所有路徑可以分為四種情況，每種情況的解釋如下：

1)如果超過n-k個節點處于0狀態，無論其他節點處于什么狀態，系統的計算能力都低于LBi，即系統性能不為Li。對應這種情況的路徑和葉子節點“0”相連。

2)如果超過n-l個節點處于0狀態，并且至少有k個節點處于1狀態，無論其他節點處于什么狀態，系統的計算能力P都在 [LBi,UBi]中，即系統性能為Li。對應這種情況的路徑和葉子節點“1”相連。

3)如果超過k個節點處于1狀態，并且至少有n-l個節點處于0狀態，無論其他節點處于什么狀態，系統的計算能力P都在 [LBi,UBi]中，即系統性能為Li。對應這種情況的路徑和葉子節點“1”相連。

4)如果超過l個節點處于1狀態，不管其他節點處于什么狀態，系統的計算能力都高于UBi，即系統性能不為Li。對應這種情況的路徑和葉子節點“0”相連。

為了方便描述基于晶格結構的k-to-l-out-of-n模型的BDD生成過程，將晶格結構置于二維坐標系中。如圖4所示，用坐標(x,y)表示非葉子節點的位置。如果一個BDD節點的坐標為(x,y)，那么可以用“x+y+1”表示該節點的下標，例如表示為節點Nx+y+1。舉例說明，坐標為(0, 0)的節點用N1表示，坐標為(2, 2)的節點用N5表示。

圖4 用坐標(x, y)表示的BDD結構

基于k-to-l-out-of-n結構使用自頂向下算法進行BDD建模的代碼描述如下：

BDD(k,l,n)=index=0;

//首節點位置為0 For eachyon vertical axis, 0≤y≤lIf(y

//節點對應的y坐標值

//處理所有可能的x坐標值Foreachxon horizontal axis, 0≤x≤n-kIf(x=n-k);E=‘0’

//設置節點else-edge連接 ElseE=index+1

//設置節點else-edge連接T=index+n-k+1

//設置節點then-edge連接

create-BDD-node(x+y+1,E,T);

//創建節點

index++;

//更新節點位置

If(y=k-1) For eachxon horizontal axis, 0≤x≤n-kIf(x

If(k-1

create-BDD-node(x+y+1,E,T);index++;

If(y=l) For eachxon horizontal axis, 0≤x≤n-l-1 If(x=n-l-1);E=‘1’ ElseE=index+1

T=‘0’

create-BDD-node(x+y+1,E,T);index++;

Returnindex

“create-BDD-node(x+y+1,E,T)”操作表示把一個新BDD節點添加到數組中。用index記錄這個新節點在數組中的位置，新節點的編號為“x+y+1”。新節點的then-edge與一個BDD節點相連，數組中的T記錄該BDD節點的位置index，else-edge與另一個BDD節點相連；數組中的E記錄該BDD節點的位置index。3.3節中將對上述算法和傳統算法進行性能比較，進一步說明上述算法的正確性。以下簡要說明上述BDD生成算法的正確性：

如果一個BDD節點的坐標為(x,y)，節點的then-edge和else-edge坐標計算如下：

1)y∈[0,k-1)，x∈[0,n-k]，每個節點的then-edge與編號為“x+y+2”并且坐標為(x,y+1)的非葉子節點相連。如果x=n-k，那么這個節點的else-edge與葉子節點“0”相連；否則這個節點的else-edge與編號為“x+y+2”并且坐標為(x+1,y)的非葉子節點相連。

2)y=k-1，x∈[0,n-k]。如果x∈[0,n-l)，那么這個節點的else-edge與編號為“x+y+2”并且坐標為(x+1,y)的非葉子節點相連，節點的then-edge與編號為“x+y+2”并且坐標為(x,y+1)的非葉子節點相連；如果x∈[n-l,n-k)，那么這個節點的else-edge與編號為“x+y+2”并且坐標為(x+1,y)的非葉子節點相連，節點的then-edge與葉子節點“1”相連；如果x=n-k，那么節點的else-edge與葉子節點“0”相連，節點的then-edge與葉子節點“1”相連。

3)y∈(k-1,l)，x∈[0,n-l-1]。每個節點的then-edge與編號為“x+y+2”并且坐標為(x,y+1)的非葉子節點相連。如果x=n-l-1，那么節點的else-edge與葉子節點“1”相連；否則，節點的else-edge與編號為“x+y+2”并且坐標為(x+1,y)的非葉子節點相連。

4)y=l，x∈[0,n-l-1]。每個節點的then-edge與葉子節點“0”相連。如果x=n-l-1，那么這個節點的else-edge與葉子節點“1”相連；否則，這個節點的else-edge與編號為“x+y+2”并且坐標為(x+1,y)的非葉子節點相連。

3.2 評估BDD模型

在基于k-to-l-out-of-n結構的BDD模型中，計算每個BDD非葉子節點兩個邊的概率，就是計算該節點是處于非故障狀態(then-edge)還是故障狀態(else-edge)的概率，分別用1-Fj和Fj表示。

從根節點到葉子節點的每條路徑都代表了一組節點的一個狀態組合。如果到達葉子節點“1”，那么可以用這條路徑或這個狀態組合來表示系統性能Li。因此，系統處于性能Li就可以用從根節點到葉子節點“1”的所有路徑的概率之和表示。

對性能為Li時生成的BDD模型，其性能評估可以通過以下遞歸算法表示。

Pr(BDD)=(1-Fj)·Pr(BDD.T)+Fj·Pr(BDD.E)

(6)

其中：Fj表示BDD中根節點Ni處于故障狀態的概率；Pr(BDD)表示BDD的概率；BDD.T是與根節點的then-edge相連的子BDD，BDD.E是與根節點的else-edge相連的子BDD。

評估BDD模型的遞歸算法，代碼如下：

Evaluate(BDD)= If(BDD=‘1’);

// 若BDD節點是葉子節點“1” Return 1

If(BDD=‘0’);

// 若BDD節點是葉子節點“0” Return 0

If(BDD.Prhas been computed);

// 若已經計算過 ReturnBDD.Pr

// 按照式(6)計算

BDD.Pr=(1-Fj)*Evaluate(BDD.T)+Fj*Evaluate(BDD.E)

ReturnBDD.Pr

遞歸算法的結束條件是，如果BDD節點是葉子節點“0”，那么Pr(BDD)=0；如果BDD節點是葉子節點“1”，那么Pr(BDD)=1。

對于第2章給出的實例系統，其節點具有相同計算能力，表3給出了實例系統性能分析的結果，BDD模型的大小用非葉子節點的數量表示。

表3 實例系統性能分析結果

3.3 性能比較

為了證明自頂向下BDD生成算法的有效性和正確性，將其與傳統BDD生成算法作比較。傳統BDD生成算法一般采用自底向上算法[11-15]，首先創建與系統性能狀態對應的節點狀態布爾表達式，然后根據所給的邏輯操作自底向上組合生成BDD。為了防止相同表達式的重復構建，使用哈希表computation-table將一個布爾表達式映射到一個BDD節點。只有當computation-table中沒有相應的布爾表達式記錄時，才執行表達式BDD構建。但是，盡管使用computation-table，在自底向上的組合過程中，仍會產生大量BDD中間節點。

為了比較性能，使用2-to-5-out-of-n模型作為基準系統，n=10, 11, 12, 13, 14, 15，節點的故障模型為負指數分布模型。所有計算都在一臺PC上完成，其CPU為IntelCorei7- 2600 3.40GHz，內存為2.00GB，運行Windows7操作系統。性能比較結果如表4所示。注意，BDD的構造時間以毫秒(ms)為單位，BDD的大小用非葉子節點的數量表示。實驗數據表明，自頂向下BDD生成算法比傳統自底向上BDD生成算法更高效，而且隨著系統規模的增加，更能體現這樣的優勢。自頂向下BDD生成算法使用特殊的晶格結構，不會產生任何冗余的中間節點，由表4中相同的“中間BDD節點數”和“最終BDD節點數”得以證明。

為了進一步說明自頂向下BDD生成算法的性能優勢，使用一個更大的k-to-l-out-of-n模型作為基準系統，n=50, 60, 70, 80, 90, 100,每個節點的狀態分布隨機生成；考慮三組不同的(k,l)組合。

表5中BDD分析時間包括構建BDD的時間和評估BDD的時間。數據表明，自頂向下BDD生成算法可以快速地分析基于k-to-l-out-of-n結構的大型計算系統，并且BDD大小和分析時間的增長較為緩慢。特別是BDD的規模復雜度接近n2/3的情況，由表5數據可知，隨n值的增大，BDD大小增長緩慢。

表4 兩種BDD生成算法性能比較結果(2-to-5-out-of-n)

表5 BDD大小與分析時間對比

4 結語

本文提出了一種新的基于BDD的集群計算系統性能分析方法，該方法能夠有效處理節點計算能力相同的大型集群計算系統性能分析問題。采用自頂向下BDD生成算法可以避免產生大量中間操作，充分利用特殊的k-to-l-out-of-n結構，相比傳統的自底向上生成算法更為高效。

處理節點不同且計算能力也不同的集群系統性能分析問題時，適合使用狀態空間法，如Markov模型。但是，對中型或大型集群計算系統進行性能分析時，這些方法會出現“組合爆炸”問題，而且受限于可積故障時間分布[16-17]。最近，針對部件不同且相互獨立的多狀態k-out-of-n系統，我們在文獻[18]中提出了一種基于決策圖的方法。決策圖方法與Markov方法不同，Markov方法使用一個顯式狀態轉換圖模型，而決策圖使用一個組合模型，它用不相交路徑表示不相交節點的狀態組合，這些狀態組合使整個系統處于一個特定性能狀態。實例結果表明，決策圖方法可以有效地處理大量實際問題，但這個方法只適用于k-out-of-n模型，并不適用本文中的k-to-l-out-of-n模型。要將基于決策圖的方法應用于k-to-l-out-of-n模型中，需要實現新的模型生成算法、新的簡化規則以及新的排序策略。

雖然在k-to-l-out-of-n系統的建模和分析方面已經有了一些研究成果，但是本文提出的新方法在大型集群計算系統性能分析方面仍具有一定意義，特別是在現代數據中心和云計算系統規模快速增長的情況下。以后我們還將繼續擴展基于BDD的性能分析方法，將其應用于具有多狀態節點的大型集群計算系統。

References)

[1] FOSTER I, KESSELMAN C, TUECKE S.The anatomy of the grid: enabling scalable virtual organizations [J].The International Journal of High Performance Computing Applications: Information for Contributors, 2001, 15(3): 200-222.

[2] VOUK M A.Cloud computing — issues, research and implementations [J].Journal of Computing and Information Technology, 2008, 16(4): 235-246.

[3] MO Y.Variable ordering to improve BDD analysis of phased-mission systems with multimode failures [J].IEEE Transactions on Reliability, 2009, 58(1): 53-57.

[4] HARISH P, NARAYANAN P J.Accelerating large graph algorithms on the GPU using CUDA [C]// HiPC 2007: Proceedings of the 14th International Conference on High Performance Computing, LNCS 4873.Berlin: Springer-Verlag, 2007: 197-208.

[5] SHIVA S G.Advanced Computer Architectures [M].Boca Raton, FL: CRC Press, 2005: 312-322.

[6] MO Y, XING L, ZHONG F, et al.Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis [J].Reliability Engineering and System Safety, 2015, 131: 83-93.

[7] LEVITIN G, XING L.Reliability and performance of multi-state systems with propagated failures having selective effect [J].Reliability Engineering and System Safety, 2010, 95(6): 655-661.

[8] ANDREWS J D.To not or not to not [C]// ISSC-2000：Proceedings of the 18th International System Safety Conference.[S.l.]: System Safety Society, 2000: 267-275.

[9] RAUZY A, DUTUIT Y.Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within aralia [J].Reliability Engineering and System Safety, 1997, 58(2): 127-144.

[10] MO Y, XING L, ZHONG F, et al.Reliability evaluation of network systems with dependent propagated failures using decision diagrams [J].IEEE Transcations on Dependable and Secure Computing, 2015, 13(6): 672-683.

[11] MEYER J F.Model-based evaluation of system resilience [C]// DSN-W 2013: Proceedings of the 2013 43rd Annual IEEE/IFIP Conference on Dependable Systems and Networks Workshop.Washington, DC: IEEE Computer Society, 2013: 1-7.

[12] RAUZY A B, GAUTHIER J, LEDUC X.Assessment of large automatically generated fault trees by means of binary decision diagrams [J].Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2007, 221(2): 95-105.

[13] POCKY M, MALASS E, WALTER M.Combining different binary decision diagram techniques for solving models with multiple failure states [J].Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2011, 225(1): 18-27.

[14] MO Y, ZHONG F, LIU H, et al.Efficient ordering heuristics in binary decision diagram-based fault tree analysis [J].Quality and Reliability Engineering International, 2013, 29(3): 307-315.

[15] MEYER J F.Defining and evaluating resilience: a performability perspective [C/OL]// PMCCS-9: Proceedings of the 9th International Workshop on the Performability Modeling of Computer and Communication Systems.[S.l.]: Mendeley, 2009 [2016- 03- 06].http://ftp.eecs.umich.edu/people/jfm/PMCCS-9_Slides.pdf.

[16] REIBMAN A, TRIVEDI K.Numerical transient analysis of Markov models [J].Computers and Operations Research, 1998, 15(1): 19-36.

[17] TRIVEDI K S.Probability and Statistics with Reliability, Queuing and Computer Science Applications [M].2nd ed.Upper Saddle River, NJ: Prentice Hall, 2001: 172-179

[18] MO Y, XING L, AMARI S V, et al.Efficient analysis of multi-statek-out-of-nsystems [J].Reliability Engineering and System Safety, 2015, 133: 95-105.

This work is partially supported by the National Natural Science Foundation of China (61272130, 61572442), the Public Projects of Zhejiang Province (2015C33085).

XU Meiling, born in 1992, M.S.candidate.Her research interests include decision diagram analysis.

QIAO Ying, born in 1992, M.S.candidate.Her research interests include decision diagram analysis.

MO Yuchang, born in 1980, Ph.D., associate professor.His research interests include highly reliable computing.

ZHONG Farong, born in 1963, Ph.D., professor.His research interests include parallel computing.

Performance analysis of cluster computing systems using binary decision diagram

XU Meiling*, QIAO Ying, MO Yuchang, ZHONG Farong

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

To analyze the performance of cluster computing systems with identical computing power but different failure distribution, ak-to-l-out-of-nstructure was used to model system performance, and a new analytical method based on Binary Decision Diagram (BDD) was proposed for the performance analysis.A new and efficient BDD algorithm that makes full use of the specialk-to-l-out-of-nstructure was also proposed using a top-down manner, which solved the problem that the traditional bottom-up generation algorithm must generate a large number of intermediate redundant nodes.Then the proposed BDD was used to efficiently calculate the probability of the system being at a specific performance level.At last, some examples were provided to illustrate the proposed BDD-based performance analysis methodology as well as its efficiency in analyzing large-scale cluster computing systems.

cluster computing system;k-to-l-out-of-nmodel; Binary Decision Diagram (BDD)

2016- 08- 02;

2016- 08- 31。

國家自然科學基金面上項目(61272130,61572442)；浙江省公益性項目(2015C33085)。

許美玲(1992—),女,浙江杭州人,碩士研究生,主要研究方向:決策圖分析; 喬瑩(1992—),女,陜西榆林人,碩士研究生,主要研究方向:決策圖分析; 莫毓昌(1980—),男,浙江湖州人,副教授,博士,CCF會員,主要研究方向:高可靠計算; 鐘發榮(1963—),男,浙江龍游人,教授,博士,主要研究方向:并行計算。

1001- 9081(2017)02- 0463- 05

10.11772/j.issn.1001- 9081.2017.02.0463

TP302

A