Fault Tolerance Of Regularly Interconnected Multicomputer System And Diagnosis Algorithms

The interconnection network used in a multicomputers system provides an effective mechanism for the data exchange between the processors and hence is one of the dominating factors of performance of the system. In this paper, the fault tolerance and system-level diagnosis algorithms of five regularly interconnected networks are examined.The fault tolerance of an interconnection network can be measured by the probability of connectedness of the surviving network in the presence of failures. We examine the five networks under two different failure models. In the first model, it is assumed that all the communication links work properly and some processors may fail. In the second model, however, both the processors and the communication links may break out. Experimental results show that all these networks display excellent failure tolerance. In particular, the crossed cube enjoys the highest probabilistic of connectivity among them.System-level fault diagnosis is an effective approach to locating the fault processors in a multicomputers system. With the realm of test-based diagnosis, processors in a system conduct tests on neighboring processors, and diagnosis is performed based on the test outcomes. In this paper, a new fault diagnosis algorithm is proposed under a probabilistic model, which consists of two stages: preprocessing stage and neural network iteration stage. The convergence of Hopfield Neural Network ensures the convergence of this new algorithm. The performance of this new algorithm is compared with two custom probabilistic diagnosis algorithms by computer simulations on two typical types of interconnection networks (hypercube and crossed cube). Experimental results show that this new algorithm can achieve a significantly higher probability of correct diagnosis. In addition, the effectiveness of this new fault diagnosis algorithm does not significantly depend on the size of the system or the probability of processor failure. Therefore, this diagnosis algorithm is practically applicable.