許美玲，喬 瑩，莫毓昌，鐘發(fā)榮

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

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

基于二元決策圖的集群計算系統(tǒng)性能分析

許美玲*，喬 瑩，莫毓昌，鐘發(fā)榮

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

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

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

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

0 引言

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

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

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

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

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

1 問題描述

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

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

(1)

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

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

(2)

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

(3)

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

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

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

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

2 實例說明

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

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

(4)

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

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

(5)

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

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

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

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

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

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

3 基于BDD的性能分析方法

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

3.1 生成BDD模型

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

圖1 與Ni關聯(lián)的BDD節(jié)點

Fig.1BDDnodeassociatedwithNi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

//節(jié)點對應的y坐標值

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

//設置節(jié)點else-edge連接 ElseE=index+1

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

//設置節(jié)點then-edge連接

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

//創(chuàng)建節(jié)點

index++;

//更新節(jié)點位置

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節(jié)點添加到數(shù)組中。用index記錄這個新節(jié)點在數(shù)組中的位置，新節(jié)點的編號為“x+y+1”。新節(jié)點的then-edge與一個BDD節(jié)點相連，數(shù)組中的T記錄該BDD節(jié)點的位置index，else-edge與另一個BDD節(jié)點相連；數(shù)組中的E記錄該BDD節(jié)點的位置index。3.3節(jié)中將對上述算法和傳統(tǒng)算法進行性能比較，進一步說明上述算法的正確性。以下簡要說明上述BDD生成算法的正確性：

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

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

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

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

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

3.2 評估BDD模型

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

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

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

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

(6)

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

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

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

// 若BDD節(jié)點是葉子節(jié)點“1” Return 1

If(BDD=‘0’);

// 若BDD節(jié)點是葉子節(jié)點“0” Return 0

If(BDD.Prhas been computed);

// 若已經(jīng)計算過 ReturnBDD.Pr

// 按照式(6)計算

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

ReturnBDD.Pr

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

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

表3 實例系統(tǒng)性能分析結果

3.3 性能比較

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

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

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

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

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

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

4 結語

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

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

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

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會員,主要研究方向:高可靠計算; 鐘發(fā)榮(1963—),男,浙江龍游人,教授,博士,主要研究方向:并行計算。

1001- 9081(2017)02- 0463- 05

10.11772/j.issn.1001- 9081.2017.02.0463

TP302

A