System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem...System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem of fault identification in an unstructured graph has been proved to be NP-hard (non-deterministic polynomial-time hard). In this paper, we adopt the PMC diagnostic model (first proposed by Preparata, Metze, and Chien) as the foundation of point-to-point probing technology, and a system contains only restricted-faults if every of its fault-free units has at least one fault-free neighbor. Under this condition we propose an efficient method of identifying restricted-faults in the folded hypercube, which is a promising alternative to the popular hypercube topology.展开更多
The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks (denoted by FQn) acts as the host graph, and the longest fault-free cycle represents the gue...The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks (denoted by FQn) acts as the host graph, and the longest fault-free cycle represents the guest graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where |Fv| is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.展开更多
超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络...超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1 s t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。展开更多
基金supported in part by the NSC under Grand No.NSC102-2221-E-468-018
文摘System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem of fault identification in an unstructured graph has been proved to be NP-hard (non-deterministic polynomial-time hard). In this paper, we adopt the PMC diagnostic model (first proposed by Preparata, Metze, and Chien) as the foundation of point-to-point probing technology, and a system contains only restricted-faults if every of its fault-free units has at least one fault-free neighbor. Under this condition we propose an efficient method of identifying restricted-faults in the folded hypercube, which is a promising alternative to the popular hypercube topology.
基金Supported by the National Natural Science Foundation of China(11071022)the Key Project of Hubei Department of Education(D20092207)
文摘The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks (denoted by FQn) acts as the host graph, and the longest fault-free cycle represents the guest graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where |Fv| is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.
文摘超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1 s t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。