k元n方體的可靠性評估

馮凱 李婧

摘 要：并行計算機系統功能的實現很大程度上依賴于系統互連網絡的性能。為了精確度量以k元n方體為底層拓撲結構的并行計算機系統的容錯能力，研究了點故障模型下k元n方體中k元（n-1）方體子網絡的可靠性。當k≥3且為奇數時，分別在固定劃分模式和靈活劃分模式下對k元n方體中不同數目的k元（n-1）方體子網絡保持無故障狀態的平均失效時間進行了分析，并得出了這一子網絡可靠性評估參數的計算公式。結果表明，當基于k為奇數的k元n方體構建的并行計算機系統指派子網絡執行用戶任務時，在點故障模型下靈活劃分模式相比固定劃分模式有著更好的容錯能力。

關鍵詞：并行計算機系統;互連網絡;k元n方體;可靠性;平均失效時間

中圖分類號：TP393.02

文獻標志碼：A

Reliability assessment ofkaryncube networks

FENG Kai*， LI Jing

School of Computer and Information Technology， Shanxi University， Taiyuan Shanxi 030006， China

Abstract：

The functions of a parallel computer system heavily rely on the performance of interconnection network of the system. In order to measure the fault tolerance abilities of the parallel computer systems withkaryncubes as underlying topologies， the reliability of the subnetworks ofkary （n-1）cubes in akaryncube under the node fault model was studied. For odd k≥3， the mean time to failure to maintain the fault free condition of different number ofkary （n-1）cubes in akaryncube was analyzed under the fixed partition pattern and the flexible partition pattern， respectively. And the calculation formulas for the reliability evaluation parameter of subnetwork were obtained. Under the node fault model， the results indicate that the parallel computer system which is built based onkaryncubes with odd k has better fault tolerance ability under the flexible partition pattern when subnetworks in the system are assigned for the user task execution.

Key words：

parallel computer system; interconnection network;karyncube; reliability; mean time to failure

0?引言

并行計算機系統將多個處理器按照某種互連網絡連接起來，使得這些處理器通過信息傳輸相互配合，從而提高運算能力。系統互連網絡的性能對系統功能的實現起著重要的作用。在實現多任務并行處理時，系統會通過特定的機制指派各個子網絡（與原有網絡具有相同的拓撲性質，但規模較小的網絡）完成用戶任務的不同部分。然而在實際構建的大規模并行計算機系統中發生故障是不可避免的。當系統互連網絡中有故障發生時，原有網絡必將遭到一定程度的破壞，網絡中較小規模子網絡的可靠性研究對于并行算法的設計與實現至關重要。在此背景下，互連網絡的子網絡可靠性得到了廣泛的關注[1-6]。Abraham等[1]對n維超立方體的子網絡可靠性進行了研究，給出了不同規模子超立方體保持無故障狀態的平均失效時間的估計。受此啟發，Fitzgerald等[3]在不同故障模型下分別對n維星圖網絡中（n-1）維星圖子網絡的可靠性進行了研究，并且估算出了不同數目的（n-1）維星圖子網絡保持無故障狀態的平均失效時間。最近，Zhou等[6]利用這一分析方法對（n，k）星圖網絡中（n-1，k-1）星圖子網絡的可靠性也進行了研究。

本文將這一子網絡可靠性評估方法應用于k元n方體的可靠性研究。k元n方體是并行計算機系統最常用的互連網絡拓撲結構之一，諸多基于k元n方體構建的并行計算機系統已經問世，如Cray T3E[7]、IBM Blue Gene[8]等。近年來，k元n方體的拓撲結構性質得到了廣泛的研究[5，9-15]。Wang等[5]在點故障模型下研究了使得k元n方體（k≥3為奇數）中不存在k元（n-m）方體子網絡（0≤m≤n-1）的最小的點故障數，這一子網絡容錯參數刻畫了k元n方體對某一規模子網絡存在性的保持能力。為了更精確地度量k元n方體中k元（n-1）方體子網絡的可靠性，本文將在點故障模型下對不同數目的k元（n-1）方體子網絡保持無故障狀態的平均失效時間進行分析，實現對不同數目的k元（n-1）方體子網絡存在性的保持能力的刻畫。

1?基本概念和性質

首先引入一些基本概念和標記（見表1）。下文中未定義而直接使用的圖論術語和記號參見文獻[16]。

Qkn（k≥2，n≥1）是一個具有kn個頂點的連通圖，它的任一頂點可表示為u=u1u2…un，其中對于任意的整數i（1≤i≤n）均有0≤ui≤k-1。兩個頂點u=u1u2…un和v=v1v2…vn相鄰，當且僅當存在j∈{1，2，…，n}使得uj=vj±1（modk）且對于任意的l∈{1，2，…，n}＼{j}均有ul=vl。這樣的一條邊（u，v）稱為Qkn中的一條j維邊。稱Qkn中一個同構于Qkn-1的子圖為一個Qkn-1子網絡。當k≥3為奇數時，Qkn具有以下性質：

性質1[12]Qkn是點傳遞的且每個頂點的度為2n。

性質2[12]給定任一整數d∈{1，2，…，n}，通過刪除Qkn中所有的d維邊，可以將Qkn沿第d維劃分為k個不相交的Qkn-1子網絡Hd，0，Hd，1，…，Hd，k-1，其中Hd，p為Qkn中由點集{u=u1u2…ud…un∈V（Qkn）：ud=p}導出的子圖，這里0≤p≤k-1。

性質3[5]Qkn中共有nk個不同的Qkn-1子網絡。

在點故障模型下，邊故障可以忽略不計，各個頂點發生故障是相互獨立的（即某個頂點發生故障不受已發生故障的頂點的影響），且頂點的故障率是不變的。在無特殊說明的情況下，下文中出現的k元n方體Qkn均滿足k≥3為奇整數。

令C表示Qkn中所有不同的Qkn-1子網絡構成的集合。由性質2和性質3可知，C={Hd，l：1≤d≤n，0≤l≤k-1}。這表明，將Qkn沿任意一維劃分可以得到k個不同的Qkn-1子網絡，而Qkn中所有不同的Qkn-1子網絡恰好可以通過沿不同維劃分Qkn得出。

2?固定劃分模式下Ti的計算

2.1?理論計算

由性質2可知，選定d∈{1，2，…，n}，可以將Qkn沿第d維劃分為k個不同的Qkn-1子網絡Hd，0，Hd，1，…，Hd，k-1。下面通過計算Ti來評估Qkn中Qkn-1子網絡的可靠性。

在初始時刻，假定Qkn處于狀態S0;當Qkn中不存在無故障的Qkn-1子網絡時，認定Qkn失效。注意到，當Qkn處于狀態Si（1≤i≤k-1）時，Qkn中任意一個故障的Qkn-1子網絡中仍可能包含健康的頂點，而這些健康的頂點發生故障不會導致故障的Qkn-1子網絡數增多。為了便于分析，假設一旦某個Qkn-1子網絡有故障發生，則將該Qkn-1子網絡的所有頂點從Qkn中全部移除。

基于以上假設前提，S0，S1，S2，…，Sk的狀態轉換圖如圖1所示。當t=0時，P0（0）=1且對于任意的1≤l≤k有Pl（0）=0;當t=∞時，Pk（∞）=1且對于任意的0≤l≤k-1有Pl（∞）=0。P0（t），P1（t），P2（t），…，Pk（t）之間的相互關系可表示為：

P0t=-λknP0

Pit=λ[k-（i-1）]kn-1Pi-1-λ（k-i）kn-1Pi

其中1≤i≤k。

進一步地，有如下結論成立。

定理1?令ri=λ（k-i）kn-1（0≤i≤k），則P0（t）=e-r0t，Pi（t）=∑il=0ai，le-rlt（1≤i≤k），其中ai，l為常數且滿足：a1，0=r0r1-r0，a1，1=-a1，0;對于i=2，3，…，k，有ai，m=ri-1ri-rmai-1，m（m=0，1，…，i-1），ai，i=-∑i-1m=0ai，m。

證明?由P0t=-λknP0可知，∫+∞0dP0P0=∫+∞0-λkndt。結合P0（0）=1求解可得，P0（t）=e-λknt=e-r0t。

對P0（t）=e-r0t作拉普拉斯變換可知：

L[P0]=∫+∞0e-r0te-stdt=∫+∞0e-（r0+s）tdt=1r0+s

斷言1?對于1≤i≤k，有：

L[Pi]=ri-1s+riL[Pi-1]

注意到，對于1≤i≤k，有：

Pit=λ[k-（i-1）]kn-1Pi-1-λ（k-i）kn-1Pi=

ri-1Pi-1-riPi

作拉普拉斯變換可得：

LPit=∫+∞0Pite-stdt=∫+∞0e-stdPi=

∫+∞0ri-1Pi-1e-stdt-∫+∞0riPie-stdt=

ri-1L[Pi-1]-riL[Pi]

由Pl（0）=0（1≤l≤k）可知：

∫+∞0e-stdPi=Pie-st+∞0-∫+∞0Pide-st=

-Pi（0）+s∫+∞0Pie-stdt=sL[Pi]

因此ri-1L[Pi-1]-riL[Pi]=sL[Pi]，即有L[Pi]=ri-1s+riL[Pi-1]。斷言1證畢。

斷言2?對任意的1≤i≤k，有L[Pi]=ai，01s+r0+ai，11s+r1+…+ai，i1s+ri，其中ai，0，ai，1，…，ai，i為常數且滿足：

a1，0=r0r1-r0，a1，1=-a1，0;對于i=2，3，…，k有ai，m=ri-1ri-rmai-1，m（m=0，1，…，i-1），ai，i=-∑i-1m=0ai，m。

當i=1時，由斷言1可知：

L[P1]=r0s+r1L[P0]=r0（s+r1）（s+r0）=

r0r1-r0（1s+r0-1s+r1）

令a1，0=r0r1-r0，a1，1=-a1，0，則a1，0、a1，1為常數且L[P1]=a1，01s+r0+a1，11s+r1。

當i=2時，由斷言1可知，

L[P2]=r1s+r2L[P1]=

r1s+r2a1，01s+r0+a1，11s+r1=

a1，0r1r2-r01s+r0-1s+r2+a1，1r1r2-r11s+r1-1s+r2

令a2，0=r1r2-r0a1，0，a2，1=r1r2-r1a1，1，a2，2=-（a2，0+a2，1），則a2，0，a2，1，a2，2為常數且L[P2]=a2，01s+r0+a2，11s+r1+a2，21s+r2。

假設斷言對于i=q（q≥2）成立，即有L[Pq]=aq，01s+r0+aq，11s+r1+…+aq，q1s+rq，其中aq，0，aq，1，…，aq，q為常數且aq，m=rq-1rq-rmaq-1，m（m=0，1，…，q-1），aq，q=-∑q-1m=0aq，m。

當i=q+1≤k時，由斷言1可知，

L[Pq+1]=rqs+rq+1L[Pq]=

rqs+rq+1（aq，0s+r0+aq，1s+r1+…+aq，qs+rq）=

rqaq，0rq+1-r0（1s+r0-1s+rq+1）+

rqaq，1rq+1-r1（1s+r1-1s+rq+1）+…+

rqaq，qrq+1-rq（1s+rq-1s+rq+1）

令aq+1，m=rqrq+1-rmaq，m（m=0，1，…，q），aq+1，q+1=-∑qm=0aq+1，m，則aq+1，0，aq+1，1，…，aq+1，q+1為常數且L[Pq+1]=aq+1，01s+r0+aq+1，11s+r1+…+aq+1，q1s+rq+aq+1，q+11s+rq+1。斷言2證畢。

由斷言2可知，對于任意的1≤i≤k，有L[Pi]=ai，01s+r0+ai，11s+r1+…+ai，i1s+ri。作拉普拉斯逆變換可得，Pi（t）=∑il=0ai，le-rlt，其中ai，l為常數且滿足：a1，0=r0r1-r0，a1，1=-a1，0;對于i=2，3，…，k有ai，m=ri-1ri-rmai-1，m（m=0，1，…，i-1），ai，i=-∑i-1m=0ai，m。定理1證畢。

由Pi（t）和Ri（t）的定義可知，R0（t）=P0（t），Ri（t）=Ri-1（t）+Pi（t）（1≤i≤k）。

注意到，在固定劃分模式下可以將Qkn劃分為k個不同的Qkn-1子網絡。若在t時刻Qkn中所有故障點均位于i個Qkn-1子網絡中，則此時在Qkn中顯然有（k-i）個Qkn-1子網絡保持無故障狀態。從而可知，對于任意的0≤i≤k-1有Ti=∫+∞0Ri（t）dt。進一步地，有如下結論成立。

定理2?T0=1λkn，Ti=Ti-1+1λ（k-i）kn-1（1≤i≤k-1）。

證明?令ri=λ（k-i）kn-1（0≤i≤k-1）。由定理1可知，T0=∫+∞0R0（t）dt=∫+∞0P0（t）dt=∫+∞0e-r0tdt=1r0=1λkn。

對于1≤i≤k-1，Ti=∫+∞0Ri（t）dt=∫+∞0（Ri-1（t）+Pi（t））dt=Ti-1+∫+∞0Pi（t）dt。

由定理1中的斷言1可知，對于1≤i≤k-1有L[Pi]=ri-1s+riL[Pi-1]。從而有L[Pi]=ri-1s+riri-2s+ri-1L[Pi-2]=ri-1s+riri-2s+ri-1…r0s+r11s+r0，即∫+∞0Pie-stdt=ri-1s+riri-2s+ri-1…r0s+r11s+r0。

令s=0，則∫+∞0Pidt=1ri。故Ti=Ti-1+1ri=Ti-1+1λ（k-i）kn-1（1≤i≤k-1）。定理2證畢。

例1?選取k=7，3≤n≤6。在固定劃分模式下，不同規模的Qkn的Ti的值如表2所示，其中Qkn中頂點的故障率為λ=10-6。

2.2?仿真分析

為了驗證固定劃分模式下理論結果的精確性，對Qkn中Qkn-1子網絡可靠性進行仿真實驗。選取不同規模的Qkn（k=7，3≤n≤6）為實驗對象。假定Qkn中頂點的可靠性是獨立同分布的，且均服從故障率為λ=10-6的指數分布。在給定時刻t，Qkn中發生故障的頂點數為kn（1-e-λt），通過隨機生成10-000次故障頂點集對這一時刻在固定劃分模式下發生故障的Qkn-1子網絡的平均個數進行仿真計算，并與例1計算出的理論結果進行對比，具體結果如圖2所示。

從圖2可以看出，對于不同規模的Qkn，理論結果與仿真結果均基本吻合。這表明，在固定劃分模式下，得出的不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間的估計值是較為精確的。

3?靈活劃分模式下Ti的計算

當基于Qkn構建的實際系統中有故障發生時，人們期望故障的系統仍能發揮其最大作用。在考慮指派系統中不同子網絡完成用戶任務的不同部分時，不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間越大越好。在上一小節中，在固定劃分模式下對這一Qkn-1子網絡可靠性評估參數進行了分析。注意到，Qkn沿任意一維均可以劃分為k個不同的Qkn-1子網絡。若已知故障點的具體分布，可以通過靈活選取d∈{1，2，…，n}使Qkn沿第d維劃分后得到的無故障Qkn-1子網絡盡可能多，本小節將證明在這種靈活劃分模式下Ti的值相比固定劃分模式下這一參數的值有所增加。為了區分固定劃分模式下和靈活劃分模式下Ti的計算公式，記靈活劃分模式下Ti的值為Ti′。

由性質1可知，Qkn是點傳遞的。不失一般性，設a1a2…an為Qkn中首個發生故障的頂點。無論將Qkn沿哪一維劃分為k個不相交的Qkn-1子網絡，故障點a1a2…an必然可以破壞其中一個Qkn-1子網絡。注意到，Qkn中所有不同的Qkn-1子網絡構成的集合為C={Hd，l：1≤d≤n，0≤l≤k-1}。若第二個故障點b1b2…bn出現在H1，a1∪H2，a2∪…∪Hn，an中時，不妨設b1b2…bn∈V（Hi，ai），則顯然可知Qkn沿第i維劃分后得到的Hi，0，Hi，1，…，Hi，k-1中仍有k-1個無故障Qkn-1子網絡。

引理1?H1，a1∪H2，a2∪…∪Hn，an中共有nl=1∑l-1m=0（-1）ml-1mkn-1-m個頂點。

證明?注意到，對于任意的d∈{1，2，…，n}，p∈{0，1，…，k-1}，Hd，p為Qkn中由點集{u=u1u2…ud…un∈V（Qkn）：ud=p}導出的子圖，即Hd，p為一個Qkn-1子網絡。由定義可知，H1，a1中有kn-1個頂點。注意到V（H1，a1）∩V（H2，a2）=kn-2。可知在H2，a2中但不在H1，a1中的頂點有kn-1-kn-2個。注意到H1，a1，H2，a2，H3，a3中任意兩個Qkn-1子網絡均有kn-2個共同頂點，且 V（H1，a1）∩V（H2，a2）∩V（H3，a3）=kn-3。由容斥原理可知，在H3，a3中但不在H1，a1∪H2，a2中的頂點有kn-1-21kn-2+kn-3個。類似地，對于4≤l≤n，根據容斥原理，在Hl，al中但不在H1，a1∪H2，a2∪…∪Hl-1，al-1中的頂點有kn-1-l-11kn-2+l-12kn-3-l-13kn-4+…+（-1）l-1l-1l-1kn-l=∑l-1m=0（-1）ml-1mkn-1-m個，從而可知，H1，a1∪H2，a2∪…∪Hn，an中共有kn-1+（kn-1-kn-2）+（kn-1-21kn-2+kn-3）+∑nl=4∑l-1m=0（-1）ml-1mkn-1-m=∑nl=1∑l-1m=0（-1）ml-1mkn-1-m個頂點。引理1證畢。

由引理1可知，在Qkn中任意一個點發生故障之后，若要選取Qkn中第二個故障點使得將Qkn沿任一維劃分后均會得到2個故障的Qkn-1子網絡，則滿足這一條件的第二個故障點的選取方式有β=kn-∑nl=1∑l-1m=0（-1）ml-1mkn-1-m=（k-1）kn-1-∑nl=2∑l-1m=0（-1）ml-1mkn-1-m種。假定在初始時刻時Qkn處于狀態S0，則P0（t）、P1（t）之間的相互關系可表示為：P0t=-λknP0，P1t=λknP0-λβP1。

與上一小節的求解方法類似，可得：

T0′=T0=1λkn

T1′=T0′+1λβ（1）

注意到，T1=T0+1λ（k-1）kn-1，β=（k-1）kn-1-∑nl=2∑l-1m=0（-1）ml-1mkn-1-m。可知，T1′>T1。這表明，相比固定劃分模式，在靈活劃分模式下Qkn中（k-1）個Qkn-1子網絡保持無故障狀態的平均失效時間更大。

然而隨著Qkn中發生故障的頂點個數的增加，故障點的分布情況會變得越來越復雜，這導致很難利用上述方法去分析T′2，T′3，…，Tk-1′。假定這些參數仍按照定理2給出的公式進行求解，則有如下結論成立。

定理3?T0′=1λkn，T1′=T0′+1λ[（k-1）kn-1-∑nl=2∑l-1m=0（-1）ml-1mkn-1-m]，Ti′=Ti-1′ + 1λ（k-i）kn-1（2≤i≤k-1）。

證明?由式（1）和定理2可知，結論顯然成立。定理3證畢。

注意到，對于2≤i≤k-1，有Ti′=Ti-1′ + 1λ（k-i）kn-1，Ti=Ti-1+1λ（k-i）kn-1。由于T1′>T1，顯然有Ti′>Ti（2≤i≤k-1）。

例2?選取k=7，3≤n≤6。在靈活劃分模式下，不同規模的Qkn的Ti′的值如表3所示，其中Qkn中頂點的故障率為λ=10-6。

對于相同規模的Qkn，通過比較表2中Ti的值與表3中Ti′的值（1≤i≤6）可知，在靈活劃分模式下Qkn中（k-i）個Qkn-1子網絡保持無故障狀態的平均失效時間相比在固定劃分模式下有顯著增加。

4?結語

并行計算機系統通常以某個具有優良性質的互連網絡作為其底層拓撲結構。考慮到在實際應用中系統的處理器和通信線路難免會發生故障，系統的可靠性研究得到了學者們的廣泛關注。本文以點故障模型下的Qkn（k≥3為奇數）為研究對象，分別在固定劃分模式和靈活劃分模式下對Qkn中不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間進行了分析，并得出了這一子網絡可靠性評估參數的計算公式。研究結果表明，與固定劃分模式相比，在靈活劃分模式下Qkn中不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間更大。這意味著，當基于Qkn構建的并行計算機系統在指派子網絡完成用戶任務的不同部分時，靈活劃分模式相比固定劃分模式有著更好的容錯能力。邊故障模型下Qkn中不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間值得進一步研究。

參考文獻 （References）

[1]ABRAHAM S， PADMANABHAN K. Reliability of the hypercube[C]// Proceedings of the 1998 International Conference on Parallel Processing. Piscataway： IEEE，1988： 90-94.

[2]CHANG Y， BHUYAN L N. A combinatorial analysis of subcube reliability in hypercube[J]. IEEE Transactions on Computers， 1995， 44（7）： 952-956.

[3]FITZGERALD K， LATIFI S， SRIMANI P K. Reliability modeling and assessment of the stargraph networks[J]. IEEE Transactions on Reliability， 2002， 51（1）： 49-57.

[4]LI X， ZHOU S， XU X， et al. The reliability analysis based on subsystems of （n， k）star graph[J]. IEEE Transactions on Reliability， 2016， 65（4）： 1700-1709.

[5]WANG S， ZHANG G， FENG K. Fault tolerance in kary ncube networks[J]. Theoretical Computer Science， 2012， 460： 34-41.

[6]ZHOU S， LI X， LI J， et al. Reliability assessment of multiprocessor system based on （n， k）star network[J]. IEEE Transactions on Reliability， 2017， 66（4）： 1025-1035.

[7]ANDERSON E， BROOKS J， GRASSL C， et al. Performance of the CRAY T3E multiprocessor[C]// Proceedings of the 1997 ACM/IEEE Conference on Supercomputing. New York： ACM， 1997： 1-17.

[8]ADIGA N R， BLUMRICH M A， CHEN D， et al. Blue Gene/L torus interconnection network[J]. IBM Journal of Research and Development， 2005， 49（2/3）： 265-276.

[9]CHEN X. Paired 2disjoint path covers of faulty kary ncubes[J]. Theoretical Computer Science， 2016， 609： 494-499.

[10]馮凱. k元n方體的條件強匹配排除[J]. 計算機應用， 2017， 37（9）： 2454-2456， 2490. （FENG K. Conditional strong matching preclusion for kary ncubes[J]. Journal of Computer Applications， 2017， 37（9）： 2454-2456， 2490.）

[11]HSIEH S Y， KAO C Y. The conditional diagnosability ofkaryncubes under the comparison diagnosis model[J]. IEEE Transactions on Computers， 2013， 62（4）： 839-843.

[12]MAO W， NICOL D M. On kary ncubes： theory and applications[J]. Discrete Applied Mathematics， 2003， 129（1）： 171-193.

[13]WANG S， FENG K， ZHANG G. Strong matching preclusion for kary ncubes[J]. Discrete Applied Mathematics， 2013， 161（18）： 3054-3062.

[14]WANG F， ZHANG H. Matchings extend to Hamiltonian cycles in kary ncubes[J]. Information Sciences， 2015， 305： 1-13.

[15]YANG Y， LI J， WANG S. Embedding various cycles with prescribed paths into kary ncubes[J]. Discrete Applied Mathematics， 2017， 220： 161-169.

[16]BONDY A， MURTY M R. Graph Theory[M]. London： Springer， 2008：1-356.

This work is partially supported by the National Natural Science Foundation of China （61502286）， the Applied Basic Research Project of Shanxi Province （201701D221099）.

FENG Kai， born in 1987， Ph. D.， associate professor. His research interests include faulttolerance of interconnection network， graph theory and its applications.

LI Jing， born in 1996， M. S. candidate. Her research interests include faulttolerance of interconnection network.