葛姝媛，原 軍

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

0 引言

隨著高性能計(jì)算的快速發(fā)展，多處理器系統(tǒng)的規(guī)模也在逐漸擴(kuò)大。為了保證系統(tǒng)能夠穩(wěn)定運(yùn)行，必須對(duì)系統(tǒng)進(jìn)行故障診斷。在處理器之間發(fā)起測(cè)試，利用測(cè)試結(jié)果來(lái)判定故障元素的方法稱(chēng)為系統(tǒng)級(jí)診斷，是一種主要的診斷措施。PMC模型是Preparata等[1]在1967年建立的第一個(gè)系統(tǒng)級(jí)診斷模型。這一診斷模型的特點(diǎn)是，由鏈路連接的每2個(gè)處理器都能分配一個(gè)測(cè)試，并且處理器的狀態(tài)影響測(cè)試結(jié)果的可靠性。在這一開(kāi)創(chuàng)性的工作之后，BGM模型、比較模型等系統(tǒng)級(jí)診斷模型相繼被提出。大量圍繞著PMC模型、BGM模型、比較模型的研究出現(xiàn)，可參考文獻(xiàn)[2-7]。

然而，這些診斷模型假定只發(fā)生處理器故障，不發(fā)生鏈路故障。實(shí)際當(dāng)系統(tǒng)投入使用時(shí)，處理器和鏈路可能同時(shí)發(fā)生故障。因此，為了適應(yīng)這一混合故障環(huán)境，Zhu等[8]在2020年建立了基于PMC模型的系統(tǒng)級(jí)診斷模型——HPMC模型。在HPMC模型中，任意2個(gè)相鄰的處理器和處理器之間的鏈路可以分配一個(gè)測(cè)試，這三者分別稱(chēng)為測(cè)試者、被測(cè)試者和測(cè)試邊。與PMC模型不同的是，測(cè)試結(jié)果不僅受到測(cè)試者和被測(cè)試者狀態(tài)的影響，與測(cè)試邊的狀態(tài)也相關(guān)。需特別強(qiáng)調(diào)：① 與故障處理器關(guān)聯(lián)的鏈路總是好的；② 當(dāng)且僅當(dāng)測(cè)試者無(wú)故障，測(cè)試結(jié)果是可靠的。

與此同時(shí)，Zhu等提出了HPMC模型下的h-限制點(diǎn)診斷度和r-限制邊診斷度。這2種混合故障診斷度是衡量混合故障環(huán)境下系統(tǒng)故障診斷能力的重要參數(shù)。隨后，文獻(xiàn)[8-10]分別確定了超立方體、交換超立方體、類(lèi)超立方體等無(wú)三角正則網(wǎng)絡(luò)的混合故障診斷度。

交錯(cuò)群圖是基于交錯(cuò)群的一類(lèi)含三角正則網(wǎng)絡(luò)，因具有點(diǎn)傳遞性、邊傳遞性、哈密爾頓連通性等良好的性質(zhì)被廣泛研究[11-14]。交錯(cuò)群圖是構(gòu)建多處理器系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一，其故障診斷度能夠反映所構(gòu)建系統(tǒng)的故障診斷能力，在系統(tǒng)的設(shè)計(jì)和維護(hù)中起重要作用。鑒于此，研究了交錯(cuò)群圖在HPMC模型下的2種混合故障診斷度。

1 預(yù)備

1.1 符號(hào)和術(shù)語(yǔ)

設(shè)G是由邊集E(G)和頂點(diǎn)集V(G)構(gòu)成的簡(jiǎn)單無(wú)向圖。若e=uv∈E(G)，則稱(chēng)u和v是相鄰的，并稱(chēng)e和u、v是關(guān)聯(lián)的。頂點(diǎn)u的度是指G中與u關(guān)聯(lián)的邊的數(shù)目，記作d(u)。G的最小度為δ(G)=min{d(u)|u∈V(G)}。如果G中每個(gè)頂點(diǎn)的度都等于k，則稱(chēng)G是k正則的。對(duì)于任意的頂點(diǎn)u,v∈V(G)，cn(u,v)指u和v的公共鄰點(diǎn)數(shù)。

對(duì)于任意的頂點(diǎn)u，NG(u)指G中與u相鄰的所有頂點(diǎn)，NEG(u)指G中與u關(guān)聯(lián)的所有邊。給定一個(gè)頂點(diǎn)集X，G中與X相鄰的所有頂點(diǎn)用NG(X)=(∪u∈XNG(u))X表示，且G中與X關(guān)聯(lián)的所有邊用NEG(X)=(∪u∈XNEG(u))E(G[X])表示。一般地，在沒(méi)有混淆的情況下，總是將下標(biāo)省去。

1.2 交錯(cuò)群圖

令p=p1p2…pn是{1,2,…,n}中所有元素的一個(gè)排列，即pi∈{1,2,…,n}且當(dāng)i≠j時(shí)，pi≠pj。若當(dāng)j>i時(shí)滿足pj

n維交錯(cuò)群圖AGn[11]是頂點(diǎn)集為V(AGn)=An，邊集為E(AGn)={pq|q=pgi,3≤i≤n}的簡(jiǎn)單無(wú)向圖。顯然，當(dāng)n≥3時(shí)，AGn是2n-4正則的。圖1(a)和圖1(b)分別為交錯(cuò)群圖AG3和AG4。

圖1 交錯(cuò)群圖AG3和AG4

引理1[12,15]設(shè)u和v是n維交錯(cuò)群圖AGn中的任意2個(gè)頂點(diǎn)。當(dāng)uv∈E(AGn)時(shí)，cn(u,v)=1；當(dāng)uv?E(AGn)時(shí)，cn(u,v)≤2。

2 混合故障診斷理論

首先給出有關(guān)混合故障診斷的一些定義和引理。

定義1[8]設(shè)F?V和S?E分別是多處理器系統(tǒng)G(V,E)的頂點(diǎn)子集和邊子集。若任意的uv∈S滿足u?F且v?F，則稱(chēng)(F,S)為一致故障對(duì)。

引理2[8]設(shè)(F1,S1)和(F2,S2)是多處理器系統(tǒng)G(V,E)中任意2個(gè)相異的一致故障對(duì)，則(F1,S1)和(F2,S2)在HPMC模型下是可區(qū)分的當(dāng)且僅當(dāng)下列條件之一成立：

3) 存在e=uv∈E滿足e∈S1S2且u?F2，v?F2；

4) 存在e=uv∈E滿足e∈S2S1且u?F1，v?F1。

定義2[8]設(shè)G是一個(gè)多處理器系統(tǒng)，t、s是2個(gè)正整數(shù)。則G在HPMC模型下是(t,s)-可診斷的當(dāng)且僅當(dāng)任意2個(gè)滿足|F1|,|F2|≤t,|S1|,|S2|≤s的相異的故障對(duì)(F1,S1)和(F2,S2)是可區(qū)分的。

接下來(lái)給出h-限制點(diǎn)診斷度和r-限制邊診斷度的相關(guān)性質(zhì)。

性質(zhì)3[8]設(shè)G是有m條邊且最小度為δ(G)的多處理器系統(tǒng)，且設(shè)G在PMC模型下的診斷度為t(G)，則

3 交錯(cuò)群圖AGn的混合故障診斷度

這一節(jié)將討論交錯(cuò)群圖AGn(n≥3)在HPMC模型下的h-限制點(diǎn)診斷度和r-限制邊診斷度。

情形1F1≠F2。

由F1和F2的對(duì)稱(chēng)性，不失一般性，假設(shè)|F1F2|≥|F2F1|。接下來(lái)，討論以下3種子情形。

子情形1.1 |F1F2|=1且|F2F1|=1。

圖2 不可區(qū)分的(F1,S1)和(F2,S2)示意圖

子情形1.2|F1F2|=1且|F2F1|=0。

設(shè)F1F2={u}。與子情形1.1類(lèi)似，可得|F2|=2n-h-4。結(jié)合|F1F2|=1和|F2F1|=0，可得到|F1|=|F1∩F2|+1=|F2|+1=2n-h-3，與|F1|≤2n-h-4矛盾。

子情形1.3 |F1F2|≥2。

又由于當(dāng)u和v相鄰時(shí)cn(u,v)=1，當(dāng)u和v不相鄰時(shí)cn(u,v)≤2，故|N({u,v})|=|(N(u)∪N(v)){u,v}|≥d(u)+d(v)-3。結(jié)合|S2|≤h可得

(d(u)+d(v)-3)-|S2|≥

[(2n-4)+(2n-4)-3]-h=4n-h-11

(1)

因此

|F1∪F2|≥|NF1∪F2({u,v})|+|{u,v}|≥

(4n-h-11)+2≥4n-2h-8≥

|F1|+|F2|

(2)

因此

|F1∪F2|≥|NF1∪F2({u,v,w})|+|{u,v,w}|≥

(6n-18-2h)+3=6n-15-2h

結(jié)合|F1∪F2|=|F1|+|F2|=4n-2h-8，可得n≤3，與題設(shè)n≥4矛盾。

情形2S1≠S2。

圖3 不可區(qū)分的(F1,S1)和(F2,S2)示意圖

d(u)-|NEF1∪F2(u)|=d(u)-|NF1∪F2(u)|≥

2n-4-1=2n-5

情形1F1≠F2。

由F1和F2的對(duì)稱(chēng)性，不失一般性，假設(shè)|F1F2|≥|F2F1|。接下來(lái)，討論以下2種子情形。

子情形1.1|F1F2|=1。

子情形1.2|F1F2|=2。

又由于當(dāng)u和v相鄰時(shí)cn(u,v)=1，當(dāng)u和v不相鄰時(shí)cn(u,v)≤2，故|N({u,v})|=|(N(u)∪N(v)){u,v}|≥d(u)+d(v)-3。結(jié)合|S2|≤2n-7可得

因此

|F1∪F2|≥|NF1∪F2({u,v})|+|{u,v}|≥

(2n-4)+2>2+2≥|F1|+|F2|

與|F1|+|F2|≥|F1∪F2|矛盾。

情形2S1≠S2。

4 結(jié)論

確定了交錯(cuò)群圖在HPMC模型下的h-限制點(diǎn)診斷度和r-限制邊診斷度，主要結(jié)果見(jiàn)表1。結(jié)果表明了當(dāng)任意故障邊集的邊數(shù)不超過(guò)最小度時(shí)，系統(tǒng)可以識(shí)別到的最大故障頂點(diǎn)數(shù)，以及當(dāng)任意故障頂點(diǎn)集的頂點(diǎn)數(shù)小于最小度時(shí)，系統(tǒng)可以識(shí)別到的最大故障邊數(shù)。這些結(jié)果更精確地描述了以交錯(cuò)群圖為網(wǎng)絡(luò)底層拓?fù)浣Y(jié)構(gòu)的多處理器系統(tǒng)的故障診斷能力，為系統(tǒng)的設(shè)計(jì)和維護(hù)提供了新的參考。

表1 交錯(cuò)群圖AGn在HPMC模型下的混合故障診斷度

目前關(guān)于混合故障診斷問(wèn)題的結(jié)果較少，如何確定一般含三角網(wǎng)絡(luò)、非正則網(wǎng)絡(luò)的h-限制點(diǎn)診斷度和r-限制邊診斷度，是下一步要解決的問(wèn)題。此外，未來(lái)可圍繞互連網(wǎng)絡(luò)的混合故障診斷算法進(jìn)行研究。