(t k)-Diagnosis of Multiprocessor Systems

  • 陳 俊安

學生論文: Doctoral Thesis

摘要

  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
獎項日期2014 七月 26
原文English
監督員Sun-Yuan Hsieh (Supervisor)

引用此文

(t k)-Diagnosis of Multiprocessor Systems
俊安, 陳. (Author). 2014 七月 26

學生論文: Doctoral Thesis