LIANG Jiarong,ZHOU Ning,and YUN Long

1.School of Computer and Electronics Information,Guangxi University,Nanning 530004,China

2.Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China

1.Introduction

Since very large scale integration(VLSI)technology has fleetly been developed,in a multiprocessor system,the number of the processors,which communicate through an interconnection network by exchanging messages,may rise to hundreds or even thousands.

It is unavoidable that there are faulty nodes in multiprocessor systems.It is necessary that the system has the self diagnosing ability to identify a node to be fault or not in order to ensure its reliability.Once faulty nodes are identified,we can repair them or replace them with extra fault free nodes.We call the procedure of diagnosing faulty processors as fault diagnosis,and call the process of conducting tests about the processor and rending their results to be system-level fault diagnosis.

In[1],the concept of the Preparata,Metze,and Chien(PMC)model first is put forward,which is closely related to the system-level fault diagnosis for an interconnection network system.A system can be denoted by a graphG=(V,E),(x,y)∈Emeans that nodextests nodey.The PMC model supposes that when a processorvis tested by another processoru,a weight,e.g.,σ(x,y),can be employed to denote the corresponding test outcome,σ(x,y)=0(1)implies that nodeyis judged byxto be free-fault(faulty).The PMC model also assumes that the test outcome of a fault-free processor testing another processor is reliable,and that the one of a faulty processor testing another processor is unreliable.A syndromeσof the system refers to the aggregation of all test outcomes.The study on the PMC model can be found in[2–12].

In[13],the Maeng and Malek(MM)model is proposed,under which the unique comparator is asked to perform the comparison of each test.Two nodes are fed by the comparator with the same testing information,and then their feedbacks can be compared by the comparator.The MM model assumes that if the two nodes are fault-free,then their feedbacks are identical.Otherwise,their feedbacks are distinct.Besides,the MM model assumes that the comparison outcome of a fault-free comparator comparing other two nodes is reliable,and that of a faulty comparator comparing other two nodes is unreliable.Later,in[14]Maeng and Malek proposed the MM?model by amending the MM model,which assumes that each node can compare a pair of nodes only if the pair of nodes are its neighbors.Under the MM?model,the comparison result of nodexcomparing nodeszandycan be represented byσ(x∶z,y).When comparatorxis free-fault,σ(x∶y,z)=0 implies that nodeyand nodezare all fault-free(see Fig.1(a)),σ(x∶y,z)=1 implies that there is at least one faulty node in nodeyand nodez(see Fig.1(b)).If nodexis faulty,thenσ(x∶y,z)can be arbitrary.It is worth noting that the PMC model can be taken into the exceptional situation of the comparison model.It is easy to see that for every comparison edge(x,y)zwherezis the comparator,whenx=zory=z,the MM?model becomes the PMC model.The results on the MM?model can be found in[15–20].

Fig.1 Possible comparison results of node z comparing node x and node y

For a system,its t-diagnosability refers to the largest integer t such that all faulty nodes can be guaranteed to be identified only if the number of faulty processors is no more than t.The destination of sequence diagnosis is to strengthen the self-diagnostic ability of interconnection network through lowering the requirement of identifying faults.Furthermore,a system S is said to be t/s-diagnosable if given the integers t and s,and a set of nodes with at most s processors,which contains the faulty set,can be located providing the size of faulty processors is no more than t.On the other hand,the pessimistic diagnosability can also evaluate the self-diagnostic ability of a system.

The follows are the organization structure of the remaining parts of the paper:we present the preliminaries in Section2.Section 3discusses the properties of the largest connected component for the n-dimensional hypercube based on the MM?model.In Section 4,we present a new t/k fault-diagnosis algorithm and prove the correctness of the algorithm.Section5 describes the comparison between our results and the existing relative results and Section 6 draws conclusions.

2.Preliminaries

Let a graph G=(V,E)denote an interconnect network,V(G)the collection of nodes(processors),E(G)the collection of edges(communication links).For convenience,in this paper,we do not distinguish the three terminologies:node,vertex and processor.At the same time,the other three terminologies,interconnect network,system and graph,also are not distinguished.

Consider the system G=(V,E).Let L be some largest connected subgraph in G,and mc(G)denote the cardinality of the set of nodes of L.The connected subgraph set in G is denoted by Csub(G)={C1,C2,...,Cl|Ciis connected(1≤i≤l),Ciand Cjare disconnected(1≤ i,j≤ l),∪V(Ci)=V},letlet NG(x)={v∈V ∶(x,v)∈E},NG[x]=NG(x)∪{x}the closed set of neighbor nodes of x.Similarly,X?V,letLet NG[X]=NG(X)∪X denote the closed set of neighbor of X,G-X the subgraph of G where V(G-X)=V-X,E(G-X)={(i,j)∈E|i,j∈V-X},the induced subgraph of X can be represented by G(X)=(V?,E?),where V?=X,E?={(i,j)∈E|i,j∈X}.For a node v∈V,let degG(v)stand for v’s degree in G,δ(G)=min{degG(x)|x ∈ V}.

In the MM?model,if the three nodes x,y and z in G satisfy that both x and y are the neighbor nodes of z,then z can serve as a comparator to compare the two vertexes x and y.The comparison outcomes of z comparing nodes x and y can be shown in Table 1.

Table 1 The MM?model

Lemma 1Let G=(V,E)represent a graph.For three nodes i,j and k,suppose(k,i),(k,j)∈E.Then the following conditions hold.

(i)There exist at least one faulty node among nodes i,j,and k if σ(k ∶i,j)=1.

(ii)If σ(k ∶i,j)=0,then either nodes i,j,and k are all fault-free or node k is faulty.

ProofAccording to the definition of the comparison model,the result is true. ?

Suppose F is the faulty set in G=(V,E),σ is a syndrome caused by F.X?V is said to be a consistent fault set(CFS)of σ when the following conditions hold:(i)if k ∈ V-X and i,j∈ V-X,then σ(k ∶i,j)=0;(ii)if k∈ V-X and{i,j}∩X/= ?,then σ(k∶i,j)=1.It is easily seen that F is a consistent fault set of σ.Further,is said to be a t-CFS of σ if it is a CFS of σ and its cardinality is no more than t.

definition 1Under the MM?model,let G=(V,E)represent a system,if for each syndrome produced by a t fault set,there exists uniquet-CFS,then this system is said to be MM?t-diagnosable.

Lemma 2[15] A graph G = (V,E)is MM?t-diagnosableif and only if,for any X,Y?V,|X|,|Y|≤t,X/=Y,there are three nodes i,j and k with k∈V-X-Y and(k,i),(k,j)∈E,such that i,j∈X-Y,ori,j∈ Y-X,orj∈ (X-Y)∪(Y-X),i∈ V-X-Y.

Lemma 3[15] Let G = (V,E)be an MM?t-diagnosable system.Then,δ(G)?t.

3.Main results supporting our algorithm

definition 2[1] For a multiprocessor system G of n nodes and integer k,let R be the faulty set,if for any syndrome caused by R,a set of nodes R?with|R?|≤|R|+k can be located such that all faulty processors are contained within R?and that there are at most k fault-free processors in R?only if the cardinality of faulty sets is not more than t,then G is said to be t/k-diagnosable.

definition 3For a system represented by G=(V,E)and a syndrome σ produced by a fault set.We define the 0-comparison set of a node i as P0(i)={k∈V ∶?j(j∈V ∧ σ(k∶i,j)=0)}.The 0-comparison subgraph of G,denoted by T0(G),is a graph T0(G)=(C,E?),C=V,

A hypercube network Qncan be decomposed into two isomorphic hypercube networks of(n-1)dimensions Qn-1,denoted byand

Lemma 5Under the MM?model,given an n-dimensional hypercube network represented by Qn,and a comparison syndrome σ caused by a fault set.Let L denote a connected subgraph of T0(Qn),then either none of L is faulty or none of L is fault-free.

ProofCase 1 |V(L)|=1,the result is true.

Case 2 |V(L)|?2.Let x∈V(L),then?y∈NL(x),x∈P0(y),y∈P0(x).Without loss of generality,let x be faulty,then y is faulty.Hence,each node in NL(x)is faulty.Furthermore,each node in NL(NL(x))is faulty.Therefore,none of L is fault-free.when x is fault free,a similar discussion can be employed to prove that none of L is faulty. ?

Lemma 6[22]Let H?V(Qn)with|H|≤(3n-6)(n?3),then|V(Qn)|-|H|-2≤mc(Qn-H).

Algorithm:BFS algorithm.

Input: A hypercube network of n-dimensionand a syndrome σ caused by a-fault set,k∈{1,2,3,4},n?7.

Output:The 0-comparison subgraphsand

Step 1Begin.

Step 2define an array,e.g.,componentsfor storing the components of(i=1,2),and a queue tempand a sign array visiteddefine a set

Step 3Choose a node of V,say u,as an initial comparator node and visited[u]=1.Forif v∈P0(u),u∈P0(v),and visited[u]=1,then components[u][]=components[u][]∪{v},visited[v]=1,temp[]=temp[]∪{v}.

Step 4If temp[]/=?,then circularly take out a node from temp[],say x,for arbitrary neighbor node y of x if visited[v]=0,x∈P0(y),y∈P0(x),then components[u][]=components[u][]∪{x},visited[v]=1,temp[]=temp[]∪{x}.Else if temp[]= ?,V =V-components[u][]and exit Step 4.

Step5Circularly execute Step 3to Step4 untilV=?.

Step 6Put the array components[][]into(i=1,2).

Step 7End.

For example(see Fig.2,Fig.3),choose v5as an initial comparator node,add v5to components[v5][].Next,we have σ(v5∶v6,v8)= 0,so add v6and v8to components[v5][].Continue to choose the next node v6as the comparator,as σ(v6∶v2,v7)=0,so adding v2and v7to components[v5][]and so on,until there is no σ(w ∶u,v)=0.In the end,we obtain a component of the 0-comparison subgraph ofand(Shown in Fig.3)

Fig.2 A hypercube Q4with faulty nodes

Fig.3 Illustration of the 0-comparisont subgraph of T0(Q4)

Theorem1Letis n-dimensional hypercube network,whereand(V2,E2)are two copies of hypercube network of(n-1)dimensions.Letk≤4,n?7,F be the faulty set in Qnwith f(k)?|F|,F1=V1∩F,F2=V2∩F,Cia largest component ofσ a syndrome caused by F.Suppose thatThen under the MM?model,the following conditions are true:

(ii)A largest connected subgraph H ofexists with satisfying V(H)? V1-F1,|N(H)-F1|≤ 3.

The cases are considered as follows.

Case 2 |Fi|=|F2|.A similar argument of Case 1 can be used to obtain the resultBy the hypothesis,we have that

In summary,condition(i)is true.

(ii)For a largest component insay,H,according to Lemma 5,it is true that either the vertexes in H are all faulty or the vertexes in H are all free-fault.On the other hand,from condition(i),we have that|H|?f(k)?|F1|which implies that all vertexes of H are free-fault.Hence,V(H)?V1-F1,which implies that there exists a connected component insay,L,such that L contains H and N(L)?F1.Let L?={x|x∈V(L),degL(x)=1},then L-L?is a connected component inAccording to the definition ofwe conclude that L?∩V(H)= ?,which implies that L-L?=H.Note thatwhich implies that|L?|≤ 3.Therefore,|N(H)-F1|≤ 3.Hence,condition(ii)holds.Overall,the results of Theorem 1 are true. ?

(ii)There exists only one Ci∈Csub(G-S)with|V(Ci)|?k.

4.t/k-fault diagnosis algorithm

Using the theory in the previous section,we propose a novel t/k-diagnosis algorithm on the hypercube network of n dimensions,called by t/k-MM?-DIAG,in this section.The algorithm t/k-MM?-DIAG is a pseudo-code description algorithm.Furthermore,we will prove the correctness of algorithm t/k-MM?-DIAG.

Algorithm:t/k-MM?-DIAG

Output a sequence(H,F?).H is a set to save the fault-free nodes identified.F?is a set to save then odes identified as faulty.

Step 1Initialization.H ← ?,F?← ?.

Step 2Obtain the largest component C by the BFS algorithm in,and add each node of C to H.

Step 3Check all nodes of,for node x in,if there are y,z ∈ C such that σ(y ∶x,z)=0,then add x to H,otherwise add x to F?.

Step 4For each undiagnosed vertex v ofin the previous steps,if there exist u∈H,w∈NH(u),such that u and v are connected,and σ(u ∶w,v)=1,then add v into F?.Otherwise,addinto H wherea component by the BFS algorithm in,contains v or a neighbor of v,at the same time,check all neighbors ofin,for each neighbori ofin,if there aresuch that σ(j ∶i,k)=0,then add i to H,otherwise add x to F?.

Step 5For each undiagnosed vertex j ofin the previous steps,if there exist i∈H,k∈NH(j),such that i and j are connected and σ(i ∶k,j)=0,then add j into H.Otherwise,add v into F?.

Step 6If|F?|=f(k),then add each undiagnosed vertex v ofin the previous steps into H.Otherwise,add all(suspicious)undiagnosed vertices into F?.

Step 7Return the sequence(H,F?).

ProofFor convenience,letAccording to Lemma 5 and Theorem 1,the nodes in a largest connected subgraph C ofobtained by the BFS algorithm in Step 2,are fault-free.According to the process of the proof in Theorem 1,there exists a largest component of,say L,such thatH contains all nodes of the largest component L ofafter Step 3.By Theorem 1,we have that|L|?2n-1-.According to Lemma7,we conclude that L must be contained by the largest component ofHence,L must connect with the largest component ofwhich guarantees that all nodes of the largest component ofcan be put into H after Step 4.After Step 5,H contains all nodes of the largest component of Qn-F,which are all free-fault.According to Lemma 7,the cardinality of the union of all small connected subgraphs of Qn-F is not k.Hence,after Step 6,F?contains all faulty nodes of Qnand fault-free nodes of size at most k. ?

ProofThe BFS algorithm to buildandcostsO(2nn2)time.In algorithm of t/k-MM?-DIAG,it costs O(2n-1)time that Step 3 finds outall nodes ofwhich connect to H.Step 4 costs O(2n-1)time,Step 5 costs O(2n-1)time,and O(1)time is needed to executing Step 6.Hence,the total time is O(2nn2). ?

5.Comparisons

Diagnosability is essential for the reliability of a system.The larger the diagnosability it has,the stronger the self-diagnostic capability it has.In this section,we make some comparisons between our results and the relative results in[24]and[25].

In[24],an algorithm of(4n-9)/3-diagnosis is presented on a hypercube network of n dimensions,whose diagnosability(4n-9)is less than(5n-14),the diagnosability of the algorithm of this paper when k=4.The diagnosis algorithm in[24]is studied under the PMC model,which is a simple fault pattern and a special situation of the comparison model.However,the algorithm of the paper is obtained under the comparison model.Besides,the scope of the t/k diagnosis algorithm in the paper(k=1,2,3,4)is larger than that of[24]([24]only considers the situation k=3).

The difference between this paper and[25]is that this paper focuses on the procession of the identification of faulty nodes of hypercube network under the comparison model,and[25]focuses on the research about the t/kdiagnosability of regular graphs under the PMC model.

6.Conclusions

Fault diagnosis is very important in maintaining the reliability of a system.This paper presents the result that if a hypercube network of n dimensions Qn=contains a fault-set F with f(k) =then there must be a component ofwith size of at least 2n-1-|Fi|-5,where(i=1,2).Based on this result,a t/k-fault diagnosis algorithm is presented for the hypercube network of n dimensions.If the number of faulty nodes is no more thanin a hypercube network of n dimensions,our algorithm is able to isolate all faulty nodes to a set,among which there may be at most k nodes to be fault-free.Our algorithm has a time complexity of O(2nn2).

[1]PREPARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosable systems.IEEE Trans.on Electronic Computers,1967,16(6):848–854.

[2]SOMANI A K,PELEG O.On diagnosability of large fault sets in regular topology-based computer systems.IEEE Trans.on Computers,1996,45(8):892–903.

[3]LIANG J R,HUANG Y,YE L C.Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy.Journal of Systems Engineering and Electronics,2015,26(2):415–420.

[4]YE L C,LIANG J R.Five-round adaptive diagnosis in Hamiltonian networks.IEEE Trans.on Parallel and Distributed Systems,2015,26(9):2459–2464.

[5]ZHU Q,GUO G,WANG D.Relating diagnosability,strong diagnosability and conditional diagnosability of strong networks.IEEE Trans.on Computers,2014,63(7):881–885.

[6]HSU H C,WU K S,LIN C K,et al.A linear time pessimistic diagnosis algorithm for hyper mesh multiprocessor systems under the PMC model.IEEE Trans.on Computers,2014,63(12):2894–2904.

[7]LIN C K,KUNG T L,TAN J J M.An algorithmic approach to conditional-fault local diagnosis of regular multiprocessor interconnected systems under the PMC model.IEEE Trans.on Computers,2013,62(3):493–451.

[8]CHANG N W,HSIEH S Y.Conditional diagnosability of augmented hypercubes under the PMCmodel.IEEE Trans.on Dependable and Secure Computing,2012,9(1):46–60.

[9]TSAI C H.A quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model.IEEE Trans.on Computers,2013,62(2):259–267.

[10]LAI P L,TAN J J M,CHANG C P,et al.Conditional diagnos-ability measures for large multiprocessor systems.IEEE Trans.on Computers,2005,54(2):165–175.

[11]LIN L,ZHOU S,XU L,et al.The extra connectivity and conditional diagnosability of alternating group networking.IEEE Trans.on Parallel and Distributed Systems,2015,26(3):2352–2362.

[12]ZHOUS,XUJ M.Fault diagnosability of arrangement graphs.Information Science,2013,24(6):177–190.

[13]MALEK M.A comparison connection assignment for diagnosis of multiprocessor systems.Proc.of the 7th International Symposium on Computer Architecture,1980:31–35.

[14]MAENG J,MALEK M.A comparison connection assignment for self-diagnosis of multiprocessor systems.Proc.of the International Symposium on Fault Tolerant Computing,1981,30:173–175.

[15]SENGUPTA A,DANBURA A T.On self-diagnosable multiprocessor systems:diagnosis by the comparison approach.IEEE Trans.on Computers,1992,41(11):1386–1396.

[16]YE L C,LIANG J R,LIN H X.A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model.IEEE Trans.on Computers,2016,65(9):2884–2888.

[17]CHEN C A,CHANG G Y,HSIEH S Y.Conditional(t,k)-diagnosis in graphs by using the comparison diagnosis model.IEEE Trans.on Computers,2015,64(6):1622–1632.

[18]YE T L,HSIEH S Y.A scalable comparison based diagnosis algorithm for hypercube-like networks.IEEE Trans.on Reliability,2013,62(4):789–799.

[19]YANG X,CAO J,MEGSON G M,et al.Minimum neighborhood in a generalized hypercube.Information Processing Letters,2006,97(3):88–93.

[20]YANG X,MEGSON G M,CAO J,et al.A lower bound on the size of k-neighborhood ingeneralized hypercubes.Applied Mathematics and Computation,2006,179(1):47–54.

[21]SOMANI A K,AGARWAL V K,AVIS D.A generalized theory for system-level diagnosis.IEEE Trans.On Computers,1987,36(5):538–546.

[22]YANG X,EVANS D J,CHEN B,et al.On the maximal connected component of hypercube with faulty vertices.International Journal of Computer Mathematics,2004,81(5):515–525.

[23]LIANG J R,ZHANG Q.The t/s-diagnosability of hypercube networks under the PMC and comparison models.IEEE Access,2017,5(1):5340–5346.

[24]HUI Y,YANG X F,AMIY N.A(4n-9)/3 diagnosis algorithm for generalized hypercube networks.International Journal of Parallel,Emergent and Distributed Systems,2010,25(3):171–182.

[25]LIN L,XU L,ZHOU S,et al.Thet/k-diagnosbility for regular networks.IEEE Trans.on Computers,2016,65(10):3157–3170.