Research On System-Level Diagnosability Of Augmented Cubes Network

Fault-tolerant computing for the parallel multiprocessors system has been of interest to many researchers.The process of identifying faulty vertices is called the diagnosis of the system.System diagnosis can be done in two different approaches,that is,circuit-level diagnosis and system-level diagnosis.In circuit-level diagnosis,the processors must be tested one after one by the human labor,which induces diagnosis complicated and possibly inaccurate.On the other hand,system-level diagnosis could be done automatically by the system itself.Thus,system-level diagnosis appears to be an alternative to circuit-level testing in a large multiprocessor system.In the current researches of system level diagnosis,there are two common diagnosis models,which are PMC model and LMM*model.In the study of identifying faulty,the network topology of the system is also one of the keys to be considered except the diagnosis model.It is well known that the diagnosability of hypercube network,exchanged hypercube and star network had been widely studied.There is no doubt that the regular interconnect network is more important in the topology of multiprocessors network systems.The reason is that the hypercube network has many advantages such as good recursion,regularity,symmetry,Hamilton property,simple routing algorithm and strong fault tolerance.Secondly,the hypercube network has been widely applied in commercial and civilian fields,such as Intel iPSC/1,iPSC/2 and nCUBE computer systems.The hypercube network structure is adopted,and it may even become the basic structure of the future nanocomputer network.However,the hypercube network has its defects,the increasing dimension of networks,and the number of nodes increasing.This will greatly cost the hardware cost of the computer.Aiming at the defects of hypercubes network,in this paper,the t/k-diagnosability,the(t,k))-diagnosability and 2-good-neighbor diagnosability of augmented cubes network is studies.In the t/k-diagnosability strategy,by analyzing the network characteristics of the augmented cube network,the distribution of the neighbor nodes is analyzed according to the t/k diagnostic characteristics,and the minimum lower limit of cardinal number of the test subset is calculated,finally the t/k-diagnosis of the system is obtained.In the(r,k)-diagnosability strategy,We first sketches the important properties of the n-dimensional augmented cube network by the method of graph theory,present an algorithm based on the comparison model to locate the biggest fault component in the network,further calculate the(t,k)-diagnosability of the augmented cube network by using the biggest fault component obtained.Finally,we propose and prove the fact that the n-dimensional augmented cube network is(t,2n-1)-diagnosable.In the 2-good-neighbor diagnosability strategy,the condition is limited to any node,which has at least 2 free faulty nodes,that is,all adjacent nodes of each node can't be a fault processor node at the same time.Under the condition,the diagnosability of the system is extremely high.Finally,the results show that the 2-good-neighbor diagnosability of augmented cubes is8n-18.