k元n方體的可靠性評估

馮凱 李婧

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

關(guān)鍵詞：并行計算機系統(tǒng);互連網(wǎng)絡(luò);k元n方體;可靠性;平均失效時間

中圖分類號：TP393.02

文獻標(biāo)志碼：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?引言

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

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

1?基本概念和性質(zhì)

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

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

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

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

性質(zhì)3[5]Qkn中共有nk個不同的Qkn-1子網(wǎng)絡(luò)。

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

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

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

2.1?理論計算

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

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

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

P0t=-λknP0

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

其中1≤i≤k。

進一步地，有如下結(jié)論成立。

定理1?令ri=λ（k-i）kn-1（0≤i≤k），則P0（t）=e-r0t，Pi（t）=∑il=0ai，le-rlt（1≤i≤k），其中ai，l為常數(shù)且滿足：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。結(jié)合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為常數(shù)且滿足：

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。

當(dāng)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為常數(shù)且L[P1]=a1，01s+r0+a1，11s+r1。

當(dāng)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為常數(shù)且L[P2]=a2，01s+r0+a2，11s+r1+a2，21s+r2。

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

當(dāng)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為常數(shù)且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為常數(shù)且滿足：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子網(wǎng)絡(luò)。若在t時刻Qkn中所有故障點均位于i個Qkn-1子網(wǎng)絡(luò)中，則此時在Qkn中顯然有（k-i）個Qkn-1子網(wǎng)絡(luò)保持無故障狀態(tài)。從而可知，對于任意的0≤i≤k-1有Ti=∫+∞0Ri（t）dt。進一步地，有如下結(jié)論成立。

定理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。在固定劃分模式下，不同規(guī)模的Qkn的Ti的值如表2所示，其中Qkn中頂點的故障率為λ=10-6。

2.2?仿真分析

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

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

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

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

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

引理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}導(dǎo)出的子圖，即Hd，p為一個Qkn-1子網(wǎng)絡(luò)。由定義可知，H1，a1中有kn-1個頂點。注意到V（H1，a1）∩V（H2，a2）=kn-2?？芍贖2，a2中但不在H1，a1中的頂點有kn-1-kn-2個。注意到H1，a1，H2，a2，H3，a3中任意兩個Qkn-1子網(wǎng)絡(luò)均有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，根據(jù)容斥原理，在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中任意一個點發(fā)生故障之后，若要選取Qkn中第二個故障點使得將Qkn沿任一維劃分后均會得到2個故障的Qkn-1子網(wǎng)絡(luò)，則滿足這一條件的第二個故障點的選取方式有β=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處于狀態(tài)S0，則P0（t）、P1（t）之間的相互關(guān)系可表示為：P0t=-λknP0，P1t=λknP0-λβP1。

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

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子網(wǎng)絡(luò)保持無故障狀態(tài)的平均失效時間更大。

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

定理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可知，結(jié)論顯然成立。定理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。在靈活劃分模式下，不同規(guī)模的Qkn的Ti′的值如表3所示，其中Qkn中頂點的故障率為λ=10-6。

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

4?結(jié)語

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

參考文獻 （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]. 計算機應(yīng)用， 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.