(t k)-Diagnosis of Multiprocessor Systems

Abstract

　　System-level diagnosis is a process of identifying faulty processors in a system by conducting tests on various processors and interpreting the test results The application of system-level diagnosis is the diagnosis of multiprocessor systems There are five important issues in system-level diagnosis: diagnosis model diagnosis strategy diagnosis algorithm fault model and diagnosability We focus the (t k)-diagnosis strategy (t k)-diagnosis algorithm random fault model and (t k)-diagnosis diagnosability for some multiprocessor systems under the PMC and MM* models 　　(t k)-diagnosis which is a generalization of sequential diagnosis requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors where t >= k In this thesis faulty nodes of multiprocessor systems may occur everywhere without any restriction We propose a unified approach to compute the (t k)-diagnosability for numerous multiprocessor systems including hypercubes crossed cubes twisted cubes locally twisted cubes multiply twisted cubes generalized twisted cubes recursive circulants M?bius cubes Mcubes star graphs bubble-sort graphs pancake graphs and burnt pancake graphs The key concept of our approach is to sketch the common graph properties of the above multiprocessor systems and demonstrate that their underlying topologies have a common super class of graphs called component-composition graphs We then show that the m-dimensional component-composition graph G for m >= 4 is a lower bound of the (t k)-diagnosability Based on this result the (t k)-diagnosability of the referred multiprocessor systems can be efficiently computed

Date of Award	2014 Jul 26
Original language	English
Supervisor	Sun-Yuan Hsieh (Supervisor)