韓 妙,劉 杰,原 軍

(太原科技大學應用科學學院,太原 030024)

隨著計算機的普及與發(fā)展,計算機系統(tǒng)越來越復雜,形成如今的多處理器系統(tǒng),雖然多處理器系統(tǒng)在計算等方面有著卓越的優(yōu)勢,但計算機系統(tǒng)發(fā)生故障的概率也大大增加。為了保證計算機系統(tǒng)的正常運行,診斷出并替換掉故障處理器就至關重要。故障診斷需要依靠模型的建立,1967年,Preparata等[1]創(chuàng)建了系統(tǒng)級故障診斷理論,提出了一種系統(tǒng)級故障診斷模型——PMC模型。PMC模型是通過相鄰兩個處理器相互測來試實現(xiàn)故障診斷的。傳統(tǒng)的診斷度假定系統(tǒng)的每個結點的所有鄰點可能同時發(fā)生故障,但從實際角度出發(fā),發(fā)生這種事件的概率很小。因此傳統(tǒng)診斷度嚴重低估了系統(tǒng)的自我診斷能力。為改善傳統(tǒng)診斷度這一缺點,很多學者提出了新的診斷度。2005年,Lai等[2]提出了條件診斷度的概念,它要求系統(tǒng)中每個結點至少有1個好鄰點,并證明了超立方體Qn在PMC模型下的條件診斷度為4(n-2)+1,n≥5.2012年,Peng等[3]提出了g-好鄰條件診斷度的概念,它要求系統(tǒng)中每個非故障結點至少有g個好鄰點,并證明了超立方體Qn在PMC模型下的g-好鄰條件診斷度為2g(n-g)+2g-1,0≤g≤n-3.g-好鄰條件診斷度的研究得到了學者的廣泛關注,取得了一系列的研究成果,參見文獻[3-5].在條件診斷度和g-好鄰條件診斷度概念的啟發(fā)下,我們提出了2-條件診斷度的概念,要求系統(tǒng)中每個結點至少有2個好鄰點。本文研究了超立方體Qn在PMC模型下的2-條件診斷度。

1 預備知識

Preparata等[1]提出的PMC模型是通過相鄰兩個處理器相互測試,即對應到圖G中兩個處理器為頂點對(u,v),(u,v)表示從u到v進行測試,則u為測試者,v為被測試者。用0和1代表是否出現(xiàn)故障,0代表未出現(xiàn)故障,1代表出現(xiàn)故障。若u為故障點,則測試結果不可靠。系統(tǒng)在PMC模型下的測試過程就是對每對相鄰結點進行相互測試,因此系統(tǒng)的測試結果是一個集合,稱為G的癥候,用σ表示,可以用一個有向圖T=(V,L)表示,其中(u,v)∈L代表u和v相鄰。所以一個癥候σ就是一個函數(shù)σ:L→{0,1}.對于給定的癥候σ,頂點集F?V(G),若癥候σ是由頂點集F滿足下列情況產生的,則稱σ與F一致。

(1) 若u,v∈V(G)-F,則σ(u,v)=0;

(2) 若u∈F,v∈V(G)-F,則σ(u,v)=1;

(3) 若u∈V(G)-F,v∈F,則σ(u,v)=1;

(4) 若u,v∈F,則σ(u,v)=1.

令σ(F)是與F一致的癥候的集合。對于G中兩個不同的頂點子集F1和F2,如果σ(F1)∩σ(F2)=?,則稱F1和F2是可區(qū)分的;否則,稱F1和F2是不可區(qū)分的。

圖1 超立方體Q1、Q2、Q3Fig.1 Hypercubes Q1、Q2、Q3

由定義1.1可知,Qn是一個n正則圖,Qn中任意兩個相鄰頂點沒有公共鄰點。

定義1.2 在一個系統(tǒng)G=(V,E)中,對于任意兩個不同的2-條件故障集F1和F2,其中|F1|≤t和|F2|≤t,若F1和F2是可區(qū)分的,則G是t-可診斷的。使得G是t-可診斷的最大值t,稱為圖G的2-條件診斷度,記為t2(G).

引理1.3[7]若k≤n-2,Qk是Qn的一個子圖,且CQn(Qk)=NQn(Qk)∪V(Qk),則δ(Qn-CQn(Qk))≥n-2.

引理1.4[4]假設n≥3,且1≤g≤n-1,則κg(Qn)=(n-g)2g.

引理1.5 設H是n維超立方體的子圖,H?Q4且CQn(H)=NQn(H)∪V(H),其中n≥5,那么|NQn(H)|=16(n-4).

證明:令Q4=X40n-4,X∈(0,1).由定義1.1知,

|NQn(Q4)|=|V(X410n-5)∪V(X4010n-6)∪…∪V(X40n-51)|=|V(X410n-5)|+|V(X4010n-6)|+…+|X40n-51|=24(n-4)=16(n-4)

引理1.7[8]設A是Qn中每個點的度至少為g的子圖,則當1≤g≤n時,有|V(A)|≥2g.

2 主要結果

DahBura等[9]給出了PMC模型下F1和F2是可區(qū)分的充要條件。

引理2.1[10]設F1和F2是G中任意兩個不同的頂點子集,則F1和F2是可區(qū)分的當且僅當存在一個頂點u∈V(F1∪F2),v∈F1ΔF2,使得(u,v)∈E,如圖2所示。

引理2.2是由定義1.2和引理2.1得到PMC模型下2-條件t-可診斷的充要條件。

引理2.2[3]一個系統(tǒng)G=(V,E)在PMC模型下是2-條件t-可診斷的充要條件對于G的任意兩個2-條件故障集F1和F2(|F1|≤t,|F2|≤t),存在頂點u∈VF1∪F2,v∈F1ΔF2,使得(u,v)∈E,如圖2所示。

圖2 點集對(F1,F2)在PMC模型下可區(qū)分Fig.2 A distinguishable pair(F1,F2)under PMC model

首先討論超立方體Qn在PMC模型下t2(Qn)的上界。

引理2.3 設n≥7,則超立方體Qn在PMC模型下的2-條件診斷度t2(Qn)≤16n-57 .

證明:取超立方體Qn中的一個子圖H={A1,A2,B1,B2}?Q4,其中H1={A1,A2},H2={B1,B2},Ai,Bi?Q2,i∈{1,2}.圖H的構造如下圖3所示。我們假設F1=H1∪NQn(H),F2=H2∪NQn(H),F=F1∪F2.

由引理1.5知,

|N(H)|=24(n-4)=16(n-4)

從而

|F1|=16(n-4)+8=16n-56,

|F2|=16(n-4)+8=16n-56

由2條件故障集的定義知,對任意的u∈V(Qn),都有|NQn-F(u)|≥2.不失一般性,假設H?Q4=X40n-4,下面分三種情形討論:

情形一:u∈H1∪H2.

不妨設u∈H1,由于H?Q4,如圖3,故|NQn-F1(u)|=|NF2-F1(u)|=2.同理,u∈H2時,|NQn-F2(u)|=|NF1-F2(u)|=2.

情形二:u∈N(H).

易看出NQn(H)=V(X410n-5)∪V(X4010n-6)∪…∪V(X40n-51).不妨設u∈V(X410n-5),令u=u1u2u3u410n-5,則|NH(u)|=1;|NQn[X410n-5](u)|=4,即|NN(H)(u)|=4.因此,當n≥7時,|NQn-F(u)|=n-5≥2.

情形三:u∈V-(F1∪F2).

由引理1.3,當n≥4時,δ(V-F1∪F2)≥n-2≥2.也就是說,|NQn-F(u)|≥n-2≥2.

結合三種情形可得,F1和F2是2-條件故障集。

又因為N(H)?F1∩F2,所以對任意u∈F1ΔF2,v∈V(Qn)-(F1∪F2),有(u,v)?E(Qn).由引理2.1知,F1和F2不可分。再由引理2.2知,超立方體Qn在PMC模型下不是2-條件(16n-56)-可診斷的,即t2(Qn)≤16n-57.引理得證。

圖3 圖H及頂點集F1和F2Fig.3 Graph H and vertex sets F1 and F2

下面討論超立方體Qn在PMC模型下t2(Qn)的下界。

引理2.4 設n≥7,假設超立方體Qn中的任意兩個2-條件故障集F1和F2都有F1∩F2是Qn的一個4-好鄰割,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)≥16n-57.

證明:欲證明t2(Qn)≥16n-57,則只需要證明Qn是2-條件(16n-57)-可診斷的,根據(jù)引理2.1和引理2.2,等價于證明V(Qn)中任意兩個不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57,存在u∈V(Qn)(F1∪F2),v∈F1ΔF2,使得(u,v)∈E(Qn).采用反證法,假設存在兩個不同的2-條件故障集F1,F2(|F1|≤16n-57,|F2|≤16n-57).對于任意的u∈V(Qn)(F1∪F2),v∈F1ΔF2,都有(u,v)?E(Qn).不失一般性,假設F2F1≠?,分以下兩種情形進行討論。

情形一:V(Qn)=F1∪F2.

令f(n)=2n-32n+114,則導數(shù)f′(n)=n2n-1-32,當n≥5時,f(n)′>0,從而f(n)是一個增函數(shù)。故當n≥7時,f(n)>0.即當n≥7時,2n≥32n-114.

另一方面:

2n=|V(Qn)|=|F1|+|F2|-|F1∩F2|≤

|F1|+|F2|=2(16n-57)=32n-114,

矛盾。

情形二:V(Qn)≠F1∪F2.

根據(jù)假設V(Qn)(F1∪F2)與F1ΔF2之間沒有邊,F2ΔF1≠?且F1和F2是2-條件故障集,可得δ(F1ΔF2)≥4,由引理1.7可知,|F1ΔF2|≥24=16,可知F1-F2和F2-F1中有一個點的個數(shù)至少為8,不妨設|F2-F1|≥8.由題設可知F1∩F2是Qn的一個4-好鄰割,再由引理1.4知,

|F1∩F2|≥24(n-4)=16n-64.

從而有：

|F2|=|F2-F1|+|F1∩F2|≥

8+16n-64=16n-56.

這與已知條件中的|F2|≤16n-57矛盾。

綜上所述,兩種情況都產生矛盾,故即當n≥7時,Qn是2-條件(16n-57)-可診斷的,即t2(Qn)≥16n-57.

結合引理2.3和引理2.4可得以下定理:

定理2.5 設n≥7,假設超立方體Qn中的任意兩個2-條件故障集F1和F2都有F1∩F2是Qn的一個4-好鄰割,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.

下面對超立方體Qn在PMC模型下的2-條件診斷度做進一步的討論。

引理2.6 設n≥61,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)≥16n-57.

證明:欲證明t2(Qn)≥16n-57,則只需要證明Qn是2-條件(16n-57)-可診斷的,根據(jù)引理2.1和引理2.2,等價于證明V(Qn)中任意兩個不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57,存在u∈V(Qn)(F1∪F2),v∈F1ΔF2,使得(u,v)∈E(Qn).采用反證法,假設存在兩個不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57.對于任意的u∈V(Qn)(F1∪F2),v∈F1ΔF2,都有(u,v)?E(Qn).

由引理1.7知,|F1ΔF2|≥24.令V(Qn)-(F1∪F2)=S,則

|S|=|V(Qn)-(F1∪F2)|≥2n-2(16n-57).

由引理2.4情形一知,當n≥7時,|V(Qn)-(F1∪F2)|≥24.由題設可知F1和F2不可分,所以NQn(F1ΔF2)?F1∩F2.換言之,Qn[V(Qn)-(F1∩F2)]的每個分支的頂點個數(shù)不少于24.令F1ΔF2=B,則|B|≥24,|V(Qn-CQn(B))|≥24.由引理1.6得,

另一方面:

2(16n-57)-24≥|F1|+|F2|-

|F1ΔF2|=|F1∩F2|≥

矛盾。

綜上所述,當n≥61時,Qn是2-條件(16n-57)-可診斷的,即t2(Qn)≥16n-57.

結合引理2.3和引理2.6可得以下定理:

定理2.7 設n≥61,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.

3 結論

提出了2-條件診斷度的概念,它是條件診斷度概念的一個推廣。本文首先證明了:若超立方體Qn中的任意兩個2-條件故障集F1和F2都有F1∩F2是Qn的一個4-好鄰割,其中n≥7,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.進一步,得到當n≥61時,超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.結果表明,當要求每個結點的非故障鄰點至少為2時,超立方體能診斷出故障結點數(shù)較條件診斷度有顯著提升。