Processor fault diagnosis is an essential subject for the reliability of a multiprocessor system. The precise strategy and the pessimistic strategy are two classical diagnostic strategies which are based on the well-known PMC model. The precise strategy problem of fault diagnosis is discussed widely and demands that all processors be identified correctly, specifically that all fault-free processors are identified as "fault free” and all faulty processors are identified as "faulty.” The pessimistic diagnosis strategy is a process to diagnose faults that allows all faulty processors to be isolated within a set that contains at most one fault-free processor. In this paper, we study the pessimistic diagnosis strategy under the PMC model for hypercube-like multiprocessor systems. The contribution is to propose an efficient pessimistic diagnosis algorithm for hypercube-like multiprocessor systems. If we denote by N the total number of processors in the hypercube-like system to be diagnosed, the algorithm can run in O(N) time.

System level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Adaptive diagnosis, proposed by Nakajima, is a practical system level diagnostic scheme; the main design objective of an adaptive diagnostic scheme is to reduce the number of test rounds, as well as the total number of tests. The hierarchical crossed cube draws upon constructions used within both the hypercube and the crossed cube, giving it many desirable features such as symmetry and logarithmic diameter, making it suitable for massively parallel systems with thousands of processors. In this paper, we first show that the diagnosability of a hierarchical crossed cube, HCCk,n, is k+n, and then propose a scheme that completely diagnoses a HCCk,n within three test rounds, and at most N+⌈(k+n+2)/2⌉ × ⌊(k+n+2)/2⌋ tests, where N=2k+2nis the number of vertices of HCCk,n. Our diagnostic scheme has the optimal number of test rounds. Moreover, most of our proofs are applicable not just to hierarchical crossed cubes but also to hierarchical interconnection networks formed by replacing crossed cubes with other appropriate interconnection networks.

The problem of whether or not there are mutually independent hamiltonian cycles in interconnection networks has attracted a great attention in recent years. In this paper, we will show that most of n-dimensional hypercube-like graphs have two mutually independent hamiltonian cycles. Moreover, we also develop a systematic linear time algorithm for constructing two mutually independent hamiltonian cycles in the n-dimensional hypercube Qn, n > 3.

The hypercube has been widely used as the interconnection network in parallel computers. The crossed cube is a variation of hypercube and preserves many of its desirable properties. The hierarchical crossed cube draws upon constructions used within the hypercube and also the crossed cube. The hierarchical crossed cube is suitable for massively parallel systems with thousands of processors and owns many alluring features, such as symmetry and logarithmic diameter. In this paper, we adopt the concept of Hamiltonian cycles pattern to provide a constructive algorithm to generate a Hamiltonian cycle of the hierarchical crossed cube.

The locally twisted cube is one of the most notable variations of hypercube, but some properties of the locally twisted cube are superior to those of the hypercube. For example, the diameter of former is almost the half of that of the later. This paper addresses how to embed a maximal size of multi-dimensional torus into a locally twisted cube. The major contribution of this paper is that for n ≥4, every k-dimensional torus of size 2s1× 2s2× ⋯ × 2sksatisfyingΣi=1ksi= n can be embedded into an n-dimensional locally twisted cube with dilation two and unit expansion. Further, an embedding algorithm can be constructed based on our embedding method and the time complexity of the algorithms linear with respect to the size of the locally twisted cube. The embedding is optimal in the sense that it has unit expansion.

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks has been explored. We consider the diagnosability of a family of networks, called the matching composition network (MCN); a perfect matching connects two components. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the hypercube Qn, the crossed cube CQ/sub n/, the twisted cube TQ/sub n/, and the Mobius cube MQ/sub n/ can all proven to be n, for n/spl ges/4. In particular, we show that the diagnosability of the four-dimensional hypercube Q/sub 4/ is 4, which is not previously known.