A Study of Precise Fault Diagnosis Algorithms for Hypercube-Like Networks Based on the Comparison Diagnosis Model

  • 葉 泰麟

Student thesis: Doctoral Thesis

Abstract

With the rapid development of technology multiprocessor systems may contain hundreds or even thousands of processors (nodes) that communicate by exchanging messages through an interconnection network Fault-tolerance computing is important for a massively parallel processing system and the reliability of processors in it is therefore becoming an important issue In order to maintain high system reliability whenever a processor is found faulty it should be replaced by a fault-free processor The technique of identifying faulty processors by constructing tests on the processors and interpreting the outcomes is known as fault diagnosis The precise fault diagnosis diagnoses all processors correctly In the comparison diagnosis model it allows a processor to perform diagnosis by contrasting the responses from a pair of neighboring processors through sending the identical assignment Under the comparison diagnosis model Sengupta and Dahbura put forward the MM* model and also designed a O(N5)-time precise fault diagnosis algorithm to diagnose faulty processors for general topologies by using the MM* model where N is the number of processors in multiprocessor systems In this thesis we devised a O(N(log2 N)2)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model Based on the Hamiltonian cycle properties we improved the aforementioned results by presenting a O(N)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model Applying our algorithms the faulty processors in n-dimensional hypercubes ndimensional crossed cubes n-dimensional M?obius cubes n-dimensional generalized twisted cubes n-dimensional twisted cubes n-dimensional locally twisted cubes and recursive circulants can all be diagnosed in linear time
Date of Award2017 Feb 14
Original languageEnglish
SupervisorSun-Yuan Hsieh (Supervisor)

Cite this

'