馮凱 李婧

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

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

中圖分類號(hào)：TP393.02

文獻(xiàn)標(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?引言

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

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

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

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

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

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

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

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

在點(diǎn)故障模型下，邊故障可以忽略不計(jì)，各個(gè)頂點(diǎn)發(fā)生故障是相互獨(dú)立的（即某個(gè)頂點(diǎn)發(fā)生故障不受已發(fā)生故障的頂點(diǎn)的影響），且頂點(diǎn)的故障率是不變的。在無(wú)特殊說(shuō)明的情況下，下文中出現(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個(gè)不同的Qkn-1子網(wǎng)絡(luò)，而Qkn中所有不同的Qkn-1子網(wǎng)絡(luò)恰好可以通過(guò)沿不同維劃分Qkn得出。

2?固定劃分模式下Ti的計(jì)算

2.1?理論計(jì)算

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

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

基于以上假設(shè)前提，S0，S1，S2，…，Sk的狀態(tài)轉(zhuǎn)換圖如圖1所示。當(dāng)t=0時(shí)，P0（0）=1且對(duì)于任意的1≤l≤k有Pl（0）=0;當(dāng)t=∞時(shí)，Pk（∞）=1且對(duì)于任意的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。

進(jìn)一步地，有如下結(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;對(duì)于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。

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

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

斷言1?對(duì)于1≤i≤k，有：

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

注意到，對(duì)于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?對(duì)任意的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;對(duì)于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時(shí)，由斷言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時(shí)，由斷言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è)斷言對(duì)于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時(shí)，由斷言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可知，對(duì)于任意的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;對(duì)于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個(gè)不同的Qkn-1子網(wǎng)絡(luò)。若在t時(shí)刻Qkn中所有故障點(diǎn)均位于i個(gè)Qkn-1子網(wǎng)絡(luò)中，則此時(shí)在Qkn中顯然有（k-i）個(gè)Qkn-1子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)。從而可知，對(duì)于任意的0≤i≤k-1有Ti=∫+∞0Ri（t）dt。進(jìn)一步地，有如下結(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。

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

由定理1中的斷言1可知，對(duì)于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中頂點(diǎn)的故障率為λ=10-6。

2.2?仿真分析

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

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

3?靈活劃分模式下Ti的計(jì)算

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

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

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

證明?注意到，對(duì)于任意的d∈{1，2，…，n}，p∈{0，1，…，k-1}，Hd，p為Qkn中由點(diǎn)集{u=u1u2…ud…un∈V（Qkn）：ud=p}導(dǎo)出的子圖，即Hd，p為一個(gè)Qkn-1子網(wǎng)絡(luò)。由定義可知，H1，a1中有kn-1個(gè)頂點(diǎn)。注意到V（H1，a1）∩V（H2，a2）=kn-2?？芍贖2，a2中但不在H1，a1中的頂點(diǎn)有kn-1-kn-2個(gè)。注意到H1，a1，H2，a2，H3，a3中任意兩個(gè)Qkn-1子網(wǎng)絡(luò)均有kn-2個(gè)共同頂點(diǎn)，且 V（H1，a1）∩V（H2，a2）∩V（H3，a3）=kn-3。由容斥原理可知，在H3，a3中但不在H1，a1∪H2，a2中的頂點(diǎn)有kn-1-21kn-2+kn-3個(gè)。類似地，對(duì)于4≤l≤n，根據(jù)容斥原理，在Hl，al中但不在H1，a1∪H2，a2∪…∪Hl-1，al-1中的頂點(diǎn)有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個(gè)，從而可知，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個(gè)頂點(diǎn)。引理1證畢。

由引理1可知，在Qkn中任意一個(gè)點(diǎn)發(fā)生故障之后，若要選取Qkn中第二個(gè)故障點(diǎn)使得將Qkn沿任一維劃分后均會(huì)得到2個(gè)故障的Qkn-1子網(wǎng)絡(luò)，則滿足這一條件的第二個(gè)故障點(diǎn)的選取方式有β=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種。假定在初始時(shí)刻時(shí)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）個(gè)Qkn-1子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間更大。

然而隨著Qkn中發(fā)生故障的頂點(diǎn)個(gè)數(shù)的增加，故障點(diǎn)的分布情況會(huì)變得越來(lái)越復(fù)雜，這導(dǎo)致很難利用上述方法去分析T′2，T′3，…，Tk-1′。假定這些參數(shù)仍按照定理2給出的公式進(jìn)行求解，則有如下結(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證畢。

注意到，對(duì)于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中頂點(diǎn)的故障率為λ=10-6。

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

4?結(jié)語(yǔ)

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

參考文獻(xiàn) （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方體的條件強(qiáng)匹配排除[J]. 計(jì)算機(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.