交錯群圖的混合故障診斷問題研究

葛姝媛，原 軍

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

0 引言

隨著高性能計算的快速發展，多處理器系統的規模也在逐漸擴大。為了保證系統能夠穩定運行，必須對系統進行故障診斷。在處理器之間發起測試，利用測試結果來判定故障元素的方法稱為系統級診斷，是一種主要的診斷措施。PMC模型是Preparata等[1]在1967年建立的第一個系統級診斷模型。這一診斷模型的特點是，由鏈路連接的每2個處理器都能分配一個測試，并且處理器的狀態影響測試結果的可靠性。在這一開創性的工作之后，BGM模型、比較模型等系統級診斷模型相繼被提出。大量圍繞著PMC模型、BGM模型、比較模型的研究出現，可參考文獻[2-7]。

然而，這些診斷模型假定只發生處理器故障，不發生鏈路故障。實際當系統投入使用時，處理器和鏈路可能同時發生故障。因此，為了適應這一混合故障環境，Zhu等[8]在2020年建立了基于PMC模型的系統級診斷模型——HPMC模型。在HPMC模型中，任意2個相鄰的處理器和處理器之間的鏈路可以分配一個測試，這三者分別稱為測試者、被測試者和測試邊。與PMC模型不同的是，測試結果不僅受到測試者和被測試者狀態的影響，與測試邊的狀態也相關。需特別強調：① 與故障處理器關聯的鏈路總是好的；② 當且僅當測試者無故障，測試結果是可靠的。

與此同時，Zhu等提出了HPMC模型下的h-限制點診斷度和r-限制邊診斷度。這2種混合故障診斷度是衡量混合故障環境下系統故障診斷能力的重要參數。隨后，文獻[8-10]分別確定了超立方體、交換超立方體、類超立方體等無三角正則網絡的混合故障診斷度。

交錯群圖是基于交錯群的一類含三角正則網絡，因具有點傳遞性、邊傳遞性、哈密爾頓連通性等良好的性質被廣泛研究[11-14]。交錯群圖是構建多處理器系統的網絡拓撲結構之一，其故障診斷度能夠反映所構建系統的故障診斷能力，在系統的設計和維護中起重要作用。鑒于此，研究了交錯群圖在HPMC模型下的2種混合故障診斷度。

1 預備

1.1 符號和術語

設G是由邊集E(G)和頂點集V(G)構成的簡單無向圖。若e=uv∈E(G)，則稱u和v是相鄰的，并稱e和u、v是關聯的。頂點u的度是指G中與u關聯的邊的數目，記作d(u)。G的最小度為δ(G)=min{d(u)|u∈V(G)}。如果G中每個頂點的度都等于k，則稱G是k正則的。對于任意的頂點u,v∈V(G)，cn(u,v)指u和v的公共鄰點數。

對于任意的頂點u，NG(u)指G中與u相鄰的所有頂點，NEG(u)指G中與u關聯的所有邊。給定一個頂點集X，G中與X相鄰的所有頂點用NG(X)=(∪u∈XNG(u))X表示，且G中與X關聯的所有邊用NEG(X)=(∪u∈XNEG(u))E(G[X])表示。一般地，在沒有混淆的情況下，總是將下標省去。

1.2 交錯群圖

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

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

圖1 交錯群圖AG3和AG4

引理1[12,15]設u和v是n維交錯群圖AGn中的任意2個頂點。當uv∈E(AGn)時，cn(u,v)=1；當uv?E(AGn)時，cn(u,v)≤2。

2 混合故障診斷理論

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

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

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

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

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

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

接下來給出h-限制點診斷度和r-限制邊診斷度的相關性質。

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

3 交錯群圖AGn的混合故障診斷度

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

情形1F1≠F2。

由F1和F2的對稱性，不失一般性，假設|F1F2|≥|F2F1|。接下來，討論以下3種子情形。

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

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

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

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

子情形1.3 |F1F2|≥2。

又由于當u和v相鄰時cn(u,v)=1，當u和v不相鄰時cn(u,v)≤2，故|N({u,v})|=|(N(u)∪N(v)){u,v}|≥d(u)+d(v)-3。結合|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

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

情形2S1≠S2。

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

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

2n-4-1=2n-5

情形1F1≠F2。

由F1和F2的對稱性，不失一般性，假設|F1F2|≥|F2F1|。接下來，討論以下2種子情形。

子情形1.1|F1F2|=1。

子情形1.2|F1F2|=2。

又由于當u和v相鄰時cn(u,v)=1，當u和v不相鄰時cn(u,v)≤2，故|N({u,v})|=|(N(u)∪N(v)){u,v}|≥d(u)+d(v)-3。結合|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 結論

確定了交錯群圖在HPMC模型下的h-限制點診斷度和r-限制邊診斷度，主要結果見表1。結果表明了當任意故障邊集的邊數不超過最小度時，系統可以識別到的最大故障頂點數，以及當任意故障頂點集的頂點數小于最小度時，系統可以識別到的最大故障邊數。這些結果更精確地描述了以交錯群圖為網絡底層拓撲結構的多處理器系統的故障診斷能力，為系統的設計和維護提供了新的參考。

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

目前關于混合故障診斷問題的結果較少，如何確定一般含三角網絡、非正則網絡的h-限制點診斷度和r-限制邊診斷度，是下一步要解決的問題。此外，未來可圍繞互連網絡的混合故障診斷算法進行研究。