| Due to the impact of large-scale data analysis and processing requirements,multiprocessor systems are required to have larger size,the higher ability of processing and better stability.With the increase in size and processing speed,it is inevitable that some processors in such a system may fail.In order to maintain the reliability of the system,it should have the ability to identify fault nodes.There are two methods on the fault diagnosis of multiprocessor systems,one is called by system level diagnosis,another is called by circuit level diagnosis.Since circuit-level diagnosis requires more hardware operations,system-level diagnostics is used more popularly than logic-circuit-level diagnostic to identify faulty nodes in the system such that the system can finish independently the duties in detection and fault diagnosis by itself.In system-level diagnosis,there are many diagnostic strategies,which can be classified as precise diagnostic strategies and imprecise diagnostic strategies.The advantage of the imprecise diagnosis strategy is that its diagnosability is larger than that of precise diagnosis strategy.The diagnosability of some diagnostic strategy refers to the maximal negative integer t,which the faulty nodes in the system can be guaranteed to be indentified provided the number of the faulty nodes in the system does not exceeded t.Since the imprecise diagnosis for network system has been proposed in recent years,there are few results for reference.It is indeed difficult to do research about the imprecise diagnosis,which means that the research of the imprecise diagnosis is meaningful.Multiprocessor systems can often be modeled by regular interconnection networks,the most typical of them are hypercube networks including their variants,star networks,Mesh networks,and so on.Although a lot of results about the precise diagnosis of these network systems have been obtained,there are few results about the research of the imprecise diagnosis for them,and there are many problems on the imprecise diagnosis to be studied.In the paper,the topological structures of these new regular networks are analysed,their imprecise diagnosis strategies are studied in order to provide the support for the fault diagnosis of networks and a better serve for the high-performance supercomputer systemsIn this paper,we mainly focus on the hypercube-like networks,the exchanged hypercube network,the star networks,and study a few kinds of their diagnosability and algorithms for imprecise diagnosis.The main work and innovations are as follows.1.Through analysis of network structure properties of the exchanged hypercube EH(s,p)(s≤p),this paper presents and proves the result that the exchanged hyper cube EH(s,p)(s≤p)is((k+1)(s+1)-(k+1)(k+2)/2+1)/k k-diagnosable.Based on the above important result,an algorithm called the t/k-fault diagnosis algorithm can be proposed for EH(s,p)(s<p).Using this algorithm,we can determinate a node set S with |S| ≤t,which contains all fault nodes in EH(s,p)(s≤p)and has no more than k fault-free processors being mistakenly diagnosed as a fault.Our result shows that the t/k-diagnosability of EH(s,p)(s≤p)is larger than its classical diagnosability s+1.2.This paper presents a t/k-diagnosis algorithm on n-dimensional hypercube-like networks(include Hypercubes,Crossed cubes,Mobius cubes,Locally Twisted cubes,Twisted cubes,etc.)for any k∈[0,n-1].The algorithm can correctly identify all nodes,except at most k nodes undiagnosed.It runs in O(N)time,where N=2n is the total number of nodes of n-dimensional hypercube-like networks.3.In this paper,we first prove that an n-dimensional BC network has exactly a large component with size at least 2n-2 after removing at most 2n-2 nodes,where N is the total number of nodes of n-dimensional BC network.Based on this,we propose a pessimistic diagnosis algorithm which can correctly identify all nodes except at most one node undiagnosed,provided the number of faulty nodes is bounded by 2n-2.The algorithm can run in O(N)time.4.In this article,a new concept regarding diagnosability,called strong local diagnosability,which describes the local status of the strong diagnosability of a system,is presented.We conclude that in a hypercube network of n dimensions,the strong local diagnosability of a single node is equal to its degree.Moreover,we determine that the strong local diagnosability of a node is equal to its remaining degree in an incomplete hypercube network provided that the number of faulty edges in this hypercube network does not exceed n-3.Finally,we obtain the following results:If the minimum remaining degree of nodes in an incomplete hypercube network of Qn is greater than 3,then the strong local diagnosability of any node is still equal to its remaining degree provided that the number of faulty edges does not exceed 7(n-3)-1.5.In this paper,the t/(t+1)-diagnosable system,which can be located a set S with|S|≤t+1 containing all faulty units only if the system has at most t faulty units,is studied.Based on the characterization of t/(t+1)-diagnosable system,we present a necessary and sufficient condition to judge whether a system is t/(t+1)-diagnosable.Meanwhile,this paper exposes some new,important properties of the t/(t+1)-diagnosable system to present the t/(t+1)-diagnosability of some networks.Furthermore,we obtain the following results for the t/(t+1)-diagnosability of some special networks:a hypercube networks of n-dimensions is(3n-5)/(3n-4)-diagnosable,a star network of n-dimensions is(3n-5)/(3n-4)-diagnosable(n≥5)and a 2D-mesh(3D-mesh)with n2(n3)units is 8/9-diagnosable(11/12-diagnosable).6.This paper introduces the definition of augment hypercube network.By conditional diagnosability,this paper introduces the definition of 2 good-conditional neighbor-diagnosabile system,and presents an algorithm of fault diagnosis for an augment hypercube network,which is 2 good-ngeighbor diagnosable.In the paper,we present and prove that the 2 good-neighbor diagnosability of n-dimensional augment network is 8n-23,and at the same time,we prove that n-dimensional augment network is not 2 good-ngeighbor 8n-22-diagonsable.The research results mentioned above not only enrich the content of fault diagnosis theory of network system,but also provide an important basis and new method for designing fault diagnosis software to real networks. |
PDF Full Text Request