張念蓬 朱強(qiáng)

摘要：系統(tǒng)級(jí)診斷是多處理器系統(tǒng)設(shè)計(jì)和維護(hù)中的重要方面，通過診斷參數(shù)來衡量系統(tǒng)的容錯(cuò)性能。傳統(tǒng)的診斷參數(shù)都是在假設(shè)系統(tǒng)中僅有處理器發(fā)生故障的情形下得到的，但是在實(shí)際情形中，系統(tǒng)中的處理器和鏈接都可能發(fā)生故障。該文研究了新的系統(tǒng)級(jí)診斷參數(shù)—h-邊容錯(cuò)診斷數(shù)。當(dāng)系統(tǒng)G中的故障邊數(shù)不超過h時(shí)，G中包含的可以被全部識(shí)別的最大故障點(diǎn)數(shù)稱為系統(tǒng)G的h-邊容錯(cuò)診斷數(shù)。通過對(duì)一般圖中公共鄰點(diǎn)數(shù)的限制，證明了PMC模型下一般圖的h邊容錯(cuò)診斷數(shù)。文中確定了k-元n-方體、平衡立方體、交換立方體和交換折疊立方體4類網(wǎng)絡(luò)在PMC模型下的h-邊容錯(cuò)診斷數(shù)，為衡量系統(tǒng)在點(diǎn)邊混合故障情形下的容錯(cuò)性能提供了有效參數(shù)。

關(guān)鍵詞：多處理器系統(tǒng);PMC模型;混合故障診斷;h-邊容錯(cuò)診斷數(shù)

中圖分類號(hào)：O614

DOI：10.16152/j.cnki.xdxbzr.2020-05-012

h-edge tolerant diagnosabilities under the PMC model

ZHANG Nianpeng， ZHU Qiang

（School of Mathematics and Statistics， Xidian University， Xi′an 710071， China）

Abstract： System-level diagnosis is an important aspect in the design and maintenance of multiprocessor systems， the fault tolerance performance of multiprocessor system is measured by diagnostic parameters. Traditional diagnostic parameters are obtained under the assumption that only the processor in the system has failed. However， in the actual situation， both processors and links in the system may fail. In this paper， a new system-level diagnosis parameter， h-edge tolerant diagnosabilities is studied. When the number of fault edges in the system G does not exceed h， the maximum number of fault points included in the system G that can be guaranteed to be identified is called the system′s h-edge tolerant diagnosabilities. By limiting the common adjacent points in general graphs， the number of h-edge tolerant diagnosabilities in PMC models is proved. In this paper， the h-edge fault tolerant diagnosabilities for the following four types of networks is determined： k-ary n-cubes， balanced hypercubes， exchange hypercubes and exchange folded hypercubes under the PMC model， which provides an effective parameter for measuring the fault-tolerant performance of multiprocessor systems in the case of mixed faults.

Key words： multiprocessor system; PMC model; hybrid faulty diagnosis; h-edge tolerant diagnosabilities

隨著大規(guī)模多處理器系統(tǒng)中包含的處理器數(shù)目不斷增多，系統(tǒng)中的處理器及其之間的鏈接就不可避免地出現(xiàn)故障。因此，處理器的故障診斷已經(jīng)成為了系統(tǒng)容錯(cuò)性能研究中的一個(gè)重要問題。多處理器系統(tǒng)往往以互連網(wǎng)絡(luò)作為拓?fù)浣Y(jié)構(gòu)，用點(diǎn)表示處理器、邊表示處理器之間的鏈接來建立圖論模型。通過研究互連網(wǎng)絡(luò)的可靠性可以反映出相應(yīng)的多處理器系統(tǒng)的容錯(cuò)性能。

系統(tǒng)級(jí)診斷是識(shí)別系統(tǒng)中故障節(jié)點(diǎn)和非故障節(jié)點(diǎn)的過程，也是多處理器系統(tǒng)的故障診斷中最重要的方式之一。系統(tǒng)中處理器之間的測試結(jié)果稱為該處理器的癥狀，所有測試結(jié)果組成的集合稱為系統(tǒng)的一個(gè)綜合病癥。系統(tǒng)級(jí)故障診斷充分利用了多處理器系統(tǒng)中每一個(gè)處理器的測試能力，讓處理器之間進(jìn)行相互測試，通過診斷算法對(duì)系統(tǒng)的綜合病癥進(jìn)行分析來識(shí)別出故障節(jié)點(diǎn)的所在。根據(jù)測試的定義和結(jié)果假設(shè)的不同可以建立不同的診斷模型，如PMC模型、MM模型和BGM模型等［1-5］。PMC模型作為最著名的系統(tǒng)級(jí)診斷模型之一，由Prearata，Metze和Chien［6］在1976年提出。在PMC模型中，兩個(gè)節(jié)點(diǎn)可以互相測試，當(dāng)且僅當(dāng)節(jié)點(diǎn)之間存在一條鏈接。假設(shè)測試節(jié)點(diǎn)是無故障的，則被測節(jié)點(diǎn)的測試結(jié)果是可靠的;否則，測試結(jié)果是不可靠的。一個(gè)系統(tǒng)的可診斷數(shù)是使得系統(tǒng)中包含的故障節(jié)點(diǎn)可以被全部識(shí)別的最大故障點(diǎn)數(shù)，通常是假設(shè)系統(tǒng)中某一節(jié)點(diǎn)的所有鄰點(diǎn)同時(shí)發(fā)生故障而得到的。但是在大規(guī)模多處理器系統(tǒng)的實(shí)際運(yùn)行中，這種情形出現(xiàn)的概率是極小的。為了更好地衡量系統(tǒng)的故障診斷能力，Lai提出了條件診斷數(shù)［7］，從理論上提高了多處理器系統(tǒng)的容錯(cuò)性能。隨后，t／k條件診斷數(shù)、g-好鄰條件診斷數(shù)和h-額外條件診斷數(shù)等故障診斷參數(shù)被相繼提出，目前，這些參數(shù)在PMC模型下的許多網(wǎng)絡(luò)中得到研究［8-12］。

上述的各類診斷參數(shù)都是在假設(shè)系統(tǒng)中只有節(jié)點(diǎn)發(fā)生故障的情形下提出的。然而在實(shí)際情形中，系統(tǒng)中的節(jié)點(diǎn)和邊都可能發(fā)生故障。為了更好地衡量系統(tǒng)在點(diǎn)邊混合故障情形下的可靠性，Zhu［13］提出了h-邊容錯(cuò)診斷數(shù)。作為傳統(tǒng)診斷數(shù)的一種推廣，h-邊容錯(cuò)診斷數(shù)是假設(shè)系統(tǒng)中故障鏈接不超多h時(shí)，使系統(tǒng)是t-可診斷的最大故障點(diǎn)數(shù)。因此，h-邊容錯(cuò)診斷數(shù)可以在實(shí)際情形中更好地衡量多處理器系統(tǒng)的容錯(cuò)性能。隨后，Wei和Xu［14］證明了在PMC模型中k-正則圖的h-邊容錯(cuò)診斷數(shù)如下：

定理1［9］ 在PMC模型中，令k-正則圖G=（V，E）滿足g（G）≥4且nc（G）≤k-1。當(dāng)0≤h≤k時(shí)，則teh （G）=k-h。

然而許多著名的互連網(wǎng)絡(luò)中的h-邊容錯(cuò)診斷數(shù)不能通過定理1得到，如當(dāng)k，n≥3時(shí)，k-元n-方體Qkn和交錯(cuò)群圖AGn的圍長等于3;當(dāng)s≠t時(shí)，交換立方體EH（s，t）和交換折疊立方體EFH（s，t）不是正則的。本文將h-邊容錯(cuò)診斷數(shù)的結(jié)果推廣到一般圖中，證明了在PMC模型中，對(duì)于滿足nc（G）≤δ（G）-h-2的圖G，當(dāng)12δ（G）≤h≤δ（G）-1時(shí)，G的h-邊容錯(cuò)診斷數(shù)為δ（G）-h。通過該結(jié)論，k-元n-方體、交錯(cuò)群圖、交換立方體以及交換折疊立方體在PMC模型下的h-邊容錯(cuò)診斷數(shù)可以被確定。

1 準(zhǔn)備知識(shí)

給定一個(gè)簡單無向圖G=（V，E），V（G）和E（G）分別表示G的頂點(diǎn)集和邊集。e=uv表示G中以u(píng)和v為端點(diǎn)的邊e，同時(shí)稱u和v是相鄰的，e與u，v是連接的。對(duì)于圖G中任意一點(diǎn)u，NG（u）定義為u在G中的所有相所有相鄰頂點(diǎn)組成的集合。d（u）=|NG（u）|稱為u的度，G中最小的度數(shù)記為δ（G），即δ（G）=min｛d（u）|u∈V｝。對(duì)于G中的任意兩點(diǎn)u和v，nc（u，v）記為u和v的公共鄰點(diǎn)數(shù)，nc（G）=max｛nc（u，v）|u，v∈V｝。令F1，F(xiàn)2V，F(xiàn)1ΔF2=（F1∪F2）-（F1∩F2）。令F是圖G的任一邊集，則G-F是在G中去掉F包含的所有邊而導(dǎo)出的子圖。

在PMC模型中，給定圖G及其一個(gè)綜合病癥δ。G的點(diǎn)集F一致于δ當(dāng)且僅當(dāng)F中包含的所有節(jié)點(diǎn)都是故障的，并且所有不在F中的節(jié)點(diǎn)都是無故障的。因?yàn)楣收瞎?jié)點(diǎn)的測試結(jié)果是不可靠的，所以一個(gè)故障點(diǎn)集F可能會(huì)一致于多個(gè)綜合病癥。我們把所有一致于故障集F的綜合病癥組成的集合記為δ（F）。兩個(gè)故障集F1和F2是可區(qū)分的，當(dāng)且僅當(dāng)δ（F1）∩δ（F2）=;否則，F(xiàn)1和F2是不可區(qū)分的。

定義1［15］ 一個(gè)系統(tǒng)稱為t-可診斷的，如果當(dāng)系統(tǒng)中發(fā)生故障的節(jié)點(diǎn)數(shù)目不超過t時(shí)，所有的節(jié)點(diǎn)都能被準(zhǔn)確地識(shí)別是否故障。系統(tǒng)的可診斷數(shù)定義為使得G是t-可診斷的最大值，記為t（G）。

4 結(jié) 語

多處理器系統(tǒng)容錯(cuò)性能一直是人們關(guān)心的重要問題之一。PMC模型下的h-邊容錯(cuò)診斷數(shù)相比以往診斷參數(shù)可以更好地衡量系統(tǒng)在點(diǎn)邊混合故障情形下的容錯(cuò)性能，因而提高了系統(tǒng)在實(shí)際情形中的故障診斷性能。本文首先給出了在PMC模型下一般圖G的h-邊容錯(cuò)診斷數(shù)的單調(diào)性質(zhì)。然后證明了當(dāng)一般圖G滿足nc（G）=δ（G）-h-2時(shí)，G的h-邊容錯(cuò)診斷數(shù)為teh （G）=δ（G）-h，其中，12δ（G）≤h≤δ（G）-1。相比目前的研究成果，該結(jié)論不再局限于正則圖，同時(shí)也不對(duì)網(wǎng)絡(luò)的圍長作出要求，可以更廣泛地應(yīng)用到多處理器系統(tǒng)在PMC模型下的點(diǎn)邊混合故障診斷。最后，將結(jié)論應(yīng)用到k-元n-方體、交錯(cuò)群圖、交換立方體和交換折疊立方體4類網(wǎng)絡(luò)中，得到表2中的結(jié)果。

參考文獻(xiàn)：

［1］ DAHBURA A T，SABNANI K K， KING? L.The comparison approach to multiprocessor fault diagnosis［J］. IEEE Transactions on Computers，1987，36（3）：373-378.

［2］ LOMBARDI F.Comparison-based diagnosis with faulty comparators［J］. Electronics Letters，1986，22（22）：1158.

［3］ RANGARAJAN S， FUSSELL D. Probabilistic diagnosis algorithms tailored to system topology［J］.Fault-Tolerant Computing： The Twenty-First International Symposium， 1991：230-237.

［4］PELC A.Undirected graph models for system-level fault diagnosis［J］. IEEE Transactions on Computers，1991，40（11）：1271-1276.

［5］RANGARAJAN S， FUSSELL D.Diagnosing arbitrarily connected parallel computers with high probability［J］. IEEE Transactions on Computers，1992，41（5）：606-615.

［6］PREPARATA F P， METZE G， CHIEN R T.On the connection assignment problem of diagnosable systems［J］.IEEE Transactions on Electronic Computers， 1967，12（6）：848-854.

［7］ LAI P L， TAN J J M， CHANG C P， et al.Conditional diagnosability measures for large multiprocessor systems［J］. IEEE Transactions on Computers，2005，54（2）：165-175.

［8］ CHANG N W， HSIEH S Y.Conditional diagnosability of （n， k）-star graphs under the PMC model［J］. IEEE Transactions on Dependable and Secure Computing， 2018， 15（2）：207-216.

［9］ WEI Y L， XU M.The g-good-neighbor conditional diagnosability of locally twisted cubes［J］. Journal of the Operations Research Society of China， 2018， 6（2）：333-347.

［10］WANG S Y，WANG Z H， WANG M J S， et al.g-good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model［J］. Frontiers of Mathematics in China， 2017，12（5）：1221-1234.

［11］JIRIMUTU J， WANG S Y.The 1-good-neighbor diagno-sability of alternating group graph networks under the PMC model and MM* model［J］.Recent Patents on Computer Science， 2017，10（2）：108-115.

［12］張興， 李莉莉， 陳敬，等. 平衡立方體的h-額外連通度及h-額外條件診斷數(shù)［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯， 2019， 34（1）：72-82.

ZHANG X， LI L L， CHEN J，et al. The h-extra connectivity and h-extra conditional diagnosability of balanced hypercubes［J］.Applied Mathematics A Journal of Chinese University， 2019， 34（1）：72-82.

［13］ZHU Q， LI L L， LIU S Y，et al.Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM model［J］. Theoretical Computer Science， 2019，758：1-8.

［14］WEI Y L， XU M.Hybrid fault diagnosis capability analysis of regular graphs［J］. Theoretical Computer Science，2019，760（14）：1-14.

［15］DAHBURA A T，MASSON G M.An 0（n2.5） faulty identification algorithm for diagnosable systems［J］.IEEE Transactions on Computers，1984，33（6）：486-492.

［16］翟登鑫.k元n立方體的條件容錯(cuò)強(qiáng)Menger邊連通性［J］.沈陽大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，31（2）：168-172.

ZHAI D X.Strong Menger edge-connectivity with conditional fault tolerance of k-ary n-cubes［J］.Journal of Shenyang University（Natural Science）， 2019， 31（2）：168-172.

［17］譚秋月.交錯(cuò)群圖AGn的5類子圖可靠性研究［J］.西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017，42（11）：21-24.

TAN Q Y. On Reliability of five kinds of subgraphs of alternating group graph AGn［J］.Journal of Southwest China Normal University （Natural Science）， 2017， 42（11）：21-24.

［18］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.

［19］蔡學(xué)鵬， 楊偉， 任佰通，等. 交換折疊超立方體的連通度［J］.井岡山大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2019， 40（4）：8-11.

CAI X P， YANG W， REN B T， et al.The connectivity of? exchangedfolded hypercube［J］.Journal of Jinggangshan University（Natural Science）， 2019，40（4）：8-11.

（編 輯 李 靜）