A Ring Diagnosis Algorithm Of Interconnection Networks

This dissertation investigates the fault diagnosis of processors in large-scale multiprocessor systems. A system is represented by its interconnection networks. Automatic fault diagnosis has been considered an integral part of the process of achieving highly reliability. The technique of identifying faulty processors within the system by conducting tests on processors and interpreting the test outcomes is known as system-level diagnosis which is available technique in fault diagnosis of systems.As the number of processors increases, so does the expected number of processors being faulty at the same time. Once the number of faults is greater than precise diagnosability and pessimistic diagnosability of systems, all precise algorithms and pessimistic algorithms fail.There are two popular system-level diagnosis model, i.e. the PMC model and the MM model. This dissertation proposes a ring diagnosis algorithm for interconnection networks based on the PMC model and the MM model respectively, which can successfully copy with the case of a large number of faulty processors existing in the system, greater than traditional precise diagnosability and pessimistic diagnosability of the system.A fault bound T(N) for a N-node ring is derived under both the PMC model and the MM model. Under this fault bound T(N), it is guaranteed that at least one part of the ring can be picked out, i.e. all nodes in this part can be identified. Then a fixed five-round adaptive diagnosis algorithm is proposed which is applicable for any network containing Hamiltonian cycle. This algorithm will never identify a faulty processor as fault-free, a fault-free processor as faulty. Provided the number of faults in the system does not exceed T(N), simulations show that it can achieve almost complete diagnosis. For the case of more than T(N) faults in the system, it can still available to some extent.