交換超立方體在PMC模型下的g好鄰條件診斷度

劉秀麗，原 軍，馬 雪

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

隨著并行計(jì)算機(jī)系統(tǒng)規(guī)模的逐步擴(kuò)大，系統(tǒng)中元件出現(xiàn)故障的可能性大大增加。為了保持并行計(jì)算機(jī)系統(tǒng)的可靠性，系統(tǒng)中的故障元素應(yīng)該被及時(shí)診斷出來(lái)并被替換。Preparata等[1]在1967年將圖論方法應(yīng)用于計(jì)算機(jī)系統(tǒng)的故障診斷，創(chuàng)建了系統(tǒng)級(jí)故障診斷理論。PMC模型是他們首次提出的系統(tǒng)故障診斷模型。診斷度是系統(tǒng)級(jí)故障診斷研究的一個(gè)重要的參數(shù)，它是多處理器系統(tǒng)能夠診斷的最大故障處理器的個(gè)數(shù)。傳統(tǒng)的診斷度總是假定系統(tǒng)的任何部分都可能同時(shí)失靈，但是對(duì)于大規(guī)模并行計(jì)算機(jī)系統(tǒng)而言，每一個(gè)處理器所有相鄰的處理器同時(shí)發(fā)生故障的概率是非常小的，因此它遠(yuǎn)遠(yuǎn)低估了并行計(jì)算機(jī)系統(tǒng)的自我診斷能力。為了克服這個(gè)缺陷，2005年Lai等[2]通過(guò)限制每個(gè)頂點(diǎn)的所有鄰點(diǎn)不能同時(shí)發(fā)生故障，提出了一個(gè)新的診斷測(cè)度，稱為條件診斷度。在此概念的啟發(fā)下，2012年P(guān)eng等[3]通過(guò)限制每個(gè)非故障頂點(diǎn)都有g(shù)個(gè)非故障鄰點(diǎn)，提出了g好鄰條件診斷度。同時(shí)，在文獻(xiàn)[3]中，Peng等給出了超立方體在PMC模型下的g好鄰條件診斷度。本文研究了交換超立方體在PMC模型下的g好鄰條件診斷度，并由此推出對(duì)偶立方體在PMC模型下的g好鄰條件診斷度。

1 預(yù)備工作

設(shè)G=(V,E)是一個(gè)無(wú)向圖，其中V=V(G)，E=E(G)分別表示圖G的頂點(diǎn)集和邊集。當(dāng)用圖來(lái)表示并行計(jì)算機(jī)系統(tǒng)時(shí)，頂點(diǎn)代表處理器，邊代表處理器之間的連接。假設(shè)V′是V的一個(gè)非空子集，以V′為頂點(diǎn)集，以兩端點(diǎn)均在V′中的邊的全體為邊集所組成的子圖，稱為G的由V′導(dǎo)出的子圖，記為G[V′]；G[V′]稱為G的導(dǎo)出子圖。G的頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊的數(shù)目，用δ(G)和△(G)來(lái)表示G的頂點(diǎn)的最小度和最大度。對(duì)于圖G的任一頂點(diǎn)集S，定義G中S的鄰集為與S的頂點(diǎn)相鄰的所有頂點(diǎn)的集，記為NG(S).定義CG(S)=NG(S)∪V(S).設(shè)F為G的任意頂點(diǎn)子集，若V-F在中任意一點(diǎn)v在導(dǎo)出子圖G[V-F]中至少有g(shù)個(gè)鄰點(diǎn)，則稱F為G的g好鄰條件故障集。如果G-F不連通且G-F的每個(gè)連通分支滿足最小度為g，則稱F是一個(gè)g好鄰條件故障割。G的所有g(shù)好鄰條件故障割的最小頂點(diǎn)數(shù)稱為G的g好鄰條件連通度，記為κ(g)(G).其它文中未予定義直接使用的符號(hào)和術(shù)語(yǔ)參見文獻(xiàn)[4].

在PMC模型下，相鄰的兩個(gè)處理器可以相互進(jìn)行測(cè)試，對(duì)于圖G中的任意一條邊(u,v)∈E(G)，頂點(diǎn)對(duì)(u,v)代表從u到v的測(cè)試，稱u為測(cè)試者，v為被測(cè)試者。我們用1(0)代表測(cè)試結(jié)果是否發(fā)生故障，用σ(u,v)表示測(cè)試結(jié)果。當(dāng)u是故障的，結(jié)果是不可靠的，σ(u,v)可能是0或1.但當(dāng)u是非故障的，若v是故障的，則σ(u,v)為0，若v是非故障的，則σ(u,v)為1.所有測(cè)試結(jié)果的集合稱為系統(tǒng)G的校驗(yàn)子，記作σ.它可以用一個(gè)有向圖T=(V(G),L)表示，其中(u,v)∈L表示u和v在圖G中相鄰。對(duì)于一個(gè)給定的校驗(yàn)子σ，如果σ產(chǎn)生的條件是：存在頂點(diǎn)子集F?V，對(duì)于任意一條邊(u,v)∈L，并且σ(u,v)=1當(dāng)且僅當(dāng)v∈F，則稱故障集F與校驗(yàn)子σ是一致的。對(duì)兩個(gè)不同的頂點(diǎn)子集F1和F2，若σ(F1)∩σ(F2)=φ，則稱F1和F2是可區(qū)分的，(F1,F2)為可區(qū)分的點(diǎn)對(duì)；否則，稱F1和F2是不可區(qū)分的，(F1,F2)為不可區(qū)分的點(diǎn)對(duì)。

對(duì)于給定的校驗(yàn)子σ，若系統(tǒng)G中發(fā)生故障的處理器的數(shù)目不超過(guò)t時(shí)，所有的處理器都能被準(zhǔn)確地判斷出是否發(fā)生故障，則稱G是t-可診斷的。使得G是t-可診斷的t的最大值稱為G的診斷度，記為t(G).

定理1設(shè)F1和F2是G中任意兩個(gè)不同的頂點(diǎn)子集，且|F1|≤t，|F2|≤t.則G是t-可診斷的當(dāng)且僅當(dāng)F1和F2是可區(qū)分的。

2012年，Peng等在文獻(xiàn)[3]中提出了g好鄰條件診斷度的概念。

定義2若G中任意兩個(gè)頂點(diǎn)數(shù)至多為t的g好鄰條件故障集F1，F(xiàn)2都是可區(qū)分的，則稱G是g好鄰條件t-可診斷的。使得G是g好鄰條件t-可診斷的最大值t稱為G的g好鄰條件診斷度，記作tg(G).

本文研究的是交換超立方體。作為超立方體的一種變形網(wǎng)絡(luò)，它是由超立方體Qs+t+1去掉一些邊得到的。它不僅保留了超立方體許多有用的性質(zhì)，而且降低了互連網(wǎng)絡(luò)的復(fù)雜性。下面給出交換超立方體的概念和性質(zhì)。

給定一個(gè)正整數(shù)，稱序列xnxn-1…x1為有序n元組。對(duì)任一個(gè)有序n+1元組unun-1…u1u0，稱ur為它的r維，其中0≤r≤n.記In={1,2,…,n}.

定義3設(shè)整數(shù)t≥1,s≥1，交換超立方體EH(s,t)為無(wú)向圖，頂點(diǎn)集V(EH(s,t))={us+t…ut+1ut…u1u0|u0,ui∈{0,1},i∈Is+t}，兩頂點(diǎn)u=us+t…ut+1ut…u1u0和v=vs+t…vt+1vt…v1v0相鄰當(dāng)且僅當(dāng)滿足以下三個(gè)條件：

(1)u和v在r維恰有一個(gè)坐標(biāo)不同，其中0≤r≤s+t；

(2)若r∈I，則u0=v0=1；

(3)若r∈Is+t-It，則u0=v0=0.

稱這樣的邊(u,v)為r維邊。交換超立方體EH(1,1)和EH(1,2)如圖1所示。

圖1 交換超立方體EH(1,1)和EH(1,2)Fig.1 Two exchanged hypercubes EH(1,1) and EH(1,2)

由定義3可知EH(s,t)有2s+t+1個(gè)頂點(diǎn)和(s+t+2)2s+t-1條邊，且它是由超立方體Qs+t+1去掉一些邊得到的，即當(dāng)0維為0時(shí)，對(duì)r∈It，去掉所有的r維邊；當(dāng)0維為1時(shí)，對(duì)r∈Is+t-It，去掉所有的r維邊。因此，EH(s,t)是最小度δ(EH(s,t))=min{s,t}+1和最大度△(EH(s,t))=max{s,t}+1的二部圖。當(dāng)s=t=1時(shí)，EH(s,t)是長(zhǎng)為8的圈。當(dāng)s=t≥2時(shí)，EH(s,t)退化為新近研究較多的對(duì)偶立方體DCn[6-7].

引理4[8]EH(s,t)同構(gòu)于EH(t,s).

引理6[5]設(shè)1≤s≤t，0≤g≤s，則κg(EH(s,t))=2g(s+1-g).

引理7設(shè)H是EH(s,t)的連通子圖，且δ(H)≥g，0≤g≤s，則|V(H)|≥2g.

2 主要結(jié)果

對(duì)稱差F1△F2=(F1-F2)∪(F2-F1).DahBura等[5]給出了判定在PMC模型下，F(xiàn)1和F2是否可區(qū)分的充要條件。

定理8[9]設(shè)F1和F2是G中任意兩個(gè)不同的頂點(diǎn)子集，則F1和F2是可區(qū)分的當(dāng)且僅當(dāng)存在一個(gè)頂點(diǎn)u∈V-(F1∪F2)，x∈F1△F2，使得(u,v)∈E.如圖2所示。

圖2 在PMC模型下的可區(qū)分點(diǎn)集對(duì)(F1,F2)Fig.2 A distinguishable pair(F1,F2)of PMC model

首先討論tg(EH(s,t))的上界。

定理9設(shè)0≤g≤s，則tg(EH(s,t))≤2g(s+2-g)-1.

證明：令X={xg0s+t+1-g|x∈(0,1)}.由定義3知，導(dǎo)出子圖EH(s,t)[X]是一個(gè)g維超立方體Qg，且NEH(s,t)(X)={xg0p10s-p-g-10t+1|0≤p≤s-g-1,g≤s-1}∪{xg0s+t-g1}，其中x∈{0,1}.對(duì)任一頂點(diǎn)v∈X，有dEH(s,t)(v)=s+1，且v在X中有g(shù)個(gè)鄰點(diǎn)，因此v在NEH(s,t)(X)中有s+1-g個(gè)鄰點(diǎn)。同時(shí)，由X的取法與定義3可知，NEH(s,t)(X)中每一個(gè)頂點(diǎn)在X中有且僅有一個(gè)鄰點(diǎn)，因此|NEH(s,t)(X)|=2g(s+1-g).令F1=NEH(s,t)(X)，F(xiàn)2=CEH(s,t)(X)，故|F1|=2g(s+1-g)，|F2|=2g(s+2-g).因?yàn)閄=F1△F2，NEH(s,t)(X)=F1，如圖3所示，所以由定理8可知，F(xiàn)1和F2是不可區(qū)分的。

圖3 頂點(diǎn)集F1和F2Fig.3 Vertex set of F1 and F2

令Y=V(EH(s,t))-(F1∪F2).要證F1和F2是g好鄰條件故障集，只需證明EH(s,t)[X]和EH(s,t)[Y]滿足最小度至少為g.因?yàn)閷?dǎo)出子圖EH(s,t)[X]是一個(gè)g維超立方體Qg，所以EH(s,t)[X]滿足最小度至少為g.現(xiàn)在考慮EH(s,t)[Y]中的頂點(diǎn)。令v∈Y，若v與NEH(s,t)(X)中的頂點(diǎn)相鄰，則v有如下三種形式：

形式1：v=xg0p10s-p-g-10t1，其中0≤p≤s-g-1；g≤s-1;

形式2：v=xg0s-g0r10t-r-11，其中0≤r≤t-1；

形式3：v=xg0p10q10s-p-q-g-20t+1，其中0≤p≤s-g-2，0≤q≤s-g-2.

如果v滿足前兩種形式，那么v在NEH(s,t)(X)中有一個(gè)鄰點(diǎn)，因此v在Y中至少有s個(gè)鄰點(diǎn)，且s≥g；如果v滿足最后一種形式，那么s-g≥2，且v在NEH(s,t)(X)中含有兩個(gè)鄰點(diǎn)，因此v在Y中至少有s-1個(gè)鄰點(diǎn)，且s-1≥g.由v的任意性可知EH(s,t)[V]滿足最小度至少為g.因此，F(xiàn)1和F2是EH(s,t)的g好鄰條件故障集。

由于F1和F2是不可區(qū)分的，且|F1|=2g(s+1-g)，|F2|=2g(s+2-g)，故由定理1和定義2可知當(dāng)0≤g≤s時(shí)，EH(s,t)的g好鄰條件診斷度tg(EH(s,t))≤2g(s+2-g)-1.證畢。

下面將討論tg(EH(s,t))的下界。

定理10設(shè)0≤g≤s，則tg(EH(s,t))≥2g(s+2-g)-1.

證明：由定義2可知，只需證明EH(s,t)是g好鄰條件2g(s+2-g)-1診斷的。要證EH(s,t)是g好鄰條件2g(s+2-g)-1診斷的，只需證明在EH(s,t)中任意兩個(gè)頂點(diǎn)數(shù)至多為2g(s+2-g)的g好鄰條件故障集F1，F(xiàn)2都是可區(qū)分的。

假設(shè)存在兩個(gè)滿足條件的g好鄰條件故障集F1和F2是不可區(qū)分的。由定理8可知，F(xiàn)1和F2不可區(qū)分有兩種情況：V(EH(s,t))=F1∪F2或者V(EH(s,t))≠F1∪F2且V(EH(s,t))-(F1∪F2)與F1△F2之間沒有邊。不失一般性，假設(shè)F2-F1≠φ.

情況1：V(EH(s,t))=F1∪F2.

因?yàn)閟≥g,t≥1且EH(s,t)的所有點(diǎn)都在F1∪F2中，所以:

2s+t+1=V(EH(s,t))=|F1|+|F2|-|F1∩F2|≤2(2g(s+2-g)-1)≤4×2s-2<2s+2≤2s+t+1，矛盾。

情況2：V(EH(s,t))≠F1∪F2，且V(EH(s,t))-(F1∪F2)與F1△F2之間沒有邊。

因?yàn)镕2-F1≠φ，F(xiàn)1為g好鄰條件故障集，且δ(EH(s,t)[F1-F2])≥g.由引理7可知，|F2-F1|≥2g.

斷言：F1∩F2是EH(s,t)的g好鄰條件故障割。

首先，假設(shè)F1?F2.因?yàn)镕2是EH(s,t)的g好鄰條件故障集，所以δ(EH(s,t)-F2)≥g.又因?yàn)棣?EH(s,t)[F1-F2])≥g，所以F1∩F2為EH(s,t)的g好鄰條件故障集。由于V(EH(s,t))-(F1∪F2)與F1△F2之間沒有邊，故V(EH(s,t))-F2與F2-F1不連通。因此當(dāng)F1?F2時(shí)，F(xiàn)1∩F2是EH(s,t)的g好鄰條件故障割。

現(xiàn)在假設(shè)F1?F2，即F2-F1≠φ，且F1-F2≠φ.因?yàn)镕1和F2都是g好鄰條件故障集，且V(EH(s,t))-(F1∪F2)與F1△F2之間沒有邊，所以δ(EH(s,t)[F1-F2])≥g，δ(EH(s,t)[F2-F1])≥g，且δ(EH(s,t)-(F1∪F2))≥g.由此可知，F(xiàn)1∩F2是EH(s,t)的g好鄰條件故障集。由于V(EH(s,t))-(F1∪F2)與F1△F2之間沒有邊，故V(EH(s,t))-(F1∪F2)與F1△F2不連通。因此當(dāng)F1?F2時(shí)，F(xiàn)1∪F2是EH(s,t)的g好鄰條件故障割。斷言成立。

由引理6可知，κ(g)(EH(s,t))=2g(s+1-g).因?yàn)镕1∩F2是EH(s,t)的g好鄰條件故障割，所以|F1∩F2|≥2g(s+1-g).從而，|F2|=|F2-F1|+|F1∩F2|≥2g(s+2-g)，與假設(shè)|F2|≤2g(s+2-g)-1矛盾。證畢。

結(jié)合定理9和定理10，我們可以得到當(dāng)1≤s≤1，0≤g≤s時(shí)，在PMC模型下，交換超立方體的g好鄰條件診斷度。

定理11設(shè)1≤s≤t，0≤g≤s，則交換超立方體EH(s,t)的g好鄰條件診斷度tg(EH(s,t))=2g(s+2-g)-1.

對(duì)偶立方體DCn是超立方體的另一種變形網(wǎng)絡(luò)。因?yàn)镋H(n,n)?DCn，所以可以得到下面的結(jié)論。

推論設(shè)n≥2，則對(duì)偶立方體DCn在PMC模型下的g好鄰條件診斷度tg(DCn)=2g(n+2-g)-1.

參考文獻(xiàn)：

[1] PRETARATA F P，METZE G，CHIEN R T.On the connection assignment problem of diagnosis systems[J].IEEE Transactions on Computers，1967，16(12)：848-854.

[2] LAI P L，TAN J J M，CHANG C P，HSU L H.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers，2005，54：165-175.

[3] PENG S L，LIN C K，TAN J J M，HSU L H.The g-good-neighbor conditional diagnosability of hypercube under PMC model[J].Applied Mathematics and Computation，2012，218：10406-10412.

[4] BONDY J A，MURTY U S R.Graph Theory with Applications[M].New York：The Macmillan Press Ltd，1976.

[5] LI X J，XU J M.Generalized measures of fault tolerance in exchanged hypercubes[J].Information Processing Letters，2013，113：533-537.

[6] SHIH Y K，CHUANG H C，KAO S S.Mutually independent Hamiltonian cycles in dual-cubes[J].The Journal of Super computing，2010，54 (2)：239-251.

[7] LI Y，PENG S，CHU W.Fault-tolerant cycle embedding in dual-cube with node faulty[J].International Journal of High Performance Computing and Networking，2005，3(1)：45-53.

[8] LOH P K K，HSU W J，PAN Y.The exchanged hypercube[J].IEEE Transactions on Parallel and Distributed Systems，2005，16 (9)：866-874.

[9] DAHBURA A T，MASSON G M.AnO(n2.5) faulty identification algorithm for diagnosable systems[J].IEEE Transactions on Computers，1984，33：486-492.