Research On Several Fault Diagnosis Strategies For Interconnection Networks

Supercomputer system,also known as multi-processor parallel system,is an importan-t index to measure a country's comprehensive scientific and technological level.It is a basic platform for the future high-tech development of a country.It plays an increasingly important role in aerospace,geophysics,life information,artificial intelligence,Engineering Computing,and other fields.In a supercomputer system,the interconnection relationship between proces-sors and processors can be represented by a graph.Vertexes represent processors and edges represent connections between processors.Such a graph is called the interconnection network.The interconnection network is an important part of supercomputer system engineering.The performance of the interconnection network will affect the ultimate performance limit of the whole supercomputer system to a considerable extent.With the rapid development of the supercomputer system,the scale of the system is ex-panding.It is inevitable to face the failure of the links between processors or processors in the system,which brings about the problem of how to ensure high reliability and high utilization of the system.Interconnection network fault diagnosis is one of the key fault-tolerant technologies to solve this problem.The fault diagnosis technology of interconnection network does not need to take down and disassemble the system,and under the condition of no additional hardware cost,it uses the computing power of processor and interconnection network to realize the func-tion of fault self-diagnosis within the system,so as to realize the identification of fault points within the system,thus improving the reliability and utilization of the system.Therefore,the research on fault diagnosis of the interconnection network is a valuable subject.In this paper,we will study folded hypercube(FQ_n),hyper Petersen network(HP_n),star graph(S_n),balanced hypercube(BH_n),bijection-connected(BC)networks(L_n)and matching composition networks(MCNs)from the perspective of accurate fault diagnosis,and study the fault diagnosis problems of local fault diagnosis strategy,intermittent fault diagnosis strategy and g-extra conditional diagnosis strategy in the corresponding interconnection network.The main work of this paper is divided into three parts:1.We prove that folded hypercube and matching composition networks have good local diagnosability and propose a local fault diagnosis method based on mutual test strategy.The main conclusions are as follows:(1)It analyses the local fault diagnosability of vertex v in folded hypercube when a vertex v is associated with different number of available edges,and proves that when each vertex in F Q_n-F is connected with at least three available edges,the local diagnosability of each vertex v in F Q_n-F is equal to the degree of vertex v in graph F Q_n-F,and F Q_n-F has the strong local diagnosability property.(2)It is analyzed that the matching composition networks have the strong local diagnosabil-ity property when all the associated edges are available edges.In addition,a sufficient condition is provided to verify the strong local diagnosability property of matching composition network-s under the PMC model with unusable edges.The method is extended to n-dimensional BC interconnection networks L_nand hyper Petersen network HP_n.(3)The two-way mutual testing strategy under type?structure is analyzed and demonstrated in detail.A fault diagnosis method based on type?structure for vertex States is proposed.2.We study the intermittent fault diagnosability of hyper Petersen network,BC networks,and star graph.The main conclusions are as follows:(1)It is proved that under the condition of no unavailable edges,the intermittent fault diagnosability of n-dimensional hyper Petersen network under the PMC model is n-1,and when min{deg(v)|v?V(HP_n)}=r,2?r?n,an n-dimensional hyper Petersen net-work HP_n(n?3)is(r-1)_idiagnosable.In addition,it is proved that the intermittent fault diagnosability of n-dimensional hyper Petersen Network is n-2 under the MM*comparison diagnosis model.(2)It is proved that BC interconnection networks are(r-1)_i-diagnosable under PMC diagnosis model when there are unavailable edges in the network.The intermittent fault diag-nosability of BC networks under the MM*comparison diagnosis model is n-2.(3)The concept of minimum neighbor number is used to prove that the intermittent fault diagnosability of star graph under PMC diagnosis model is n-1.3.We study the g-extra conditional fault diagnosability of balanced hypercube BH_nunder the PMC diagnosis model,and the g-extra conditional diagnostic properties of BC networks under the MM*comparison diagnosis model.The following conclusions are obtained:(1)When n?3,the 4-extra conditional fault diagnosability and 5-extra conditional fault diagnosability of BH_nunder the PMC diagnosis model are 6n-4 and 6n-3,respectively.(2)When n?33 and 3?g?(n-1)/4,F is a g-extra vertex subset of X_n.If there are at most(n-1)/2 vertices with deg(v)=1 in X_n-F,then the g-extra conditional fault diagnosability of BC networks in MM*diagnosis model is (?)_g(G)=(g+1)n-g-C_g~2.