Reliability Evaluation Of Multiprocessor System Based On (n,k)-Star Graph

With the rapid development of VLSI technology,a multiprocessor system might contain hundreds or even thousands of processors(nodes),some of which might be faulty while the system is operating.This motivates the focus of this paper on the issue of the reliability and the diagnosability of multiprocessor systems.We establish the reliability index of subsystem of multiprocessor system utilizing combinatorial probability as well as stochastic process along with some empirical analysis.The thesis is devoted to the discovery of methodology from diagnosability of units under microscale to reliability of subsystem of multiprocessor system under macroscale and it is also committed to the idea of discrete-continuous solution model.In the second chapter,when calculating the reliability of(n,k)-star graph based on subgraphs,we apply the idea of local to whole,and we get the failure probability of the whole system from the failure probability of a node.Based on this idea,we calculate the upper bound,lower bounds and approximations of reliability of(n,k)-star graph;and by comparing these three values,we find that the approximate calculation of the reliability of(n,k)-star graph is more simple and efficient.In the third chapter,our idea is to use duration of subsystem to reflect the reliability of system.Based on this idea,under node and edge fault model,we calculate the mean time to failure(MTTF)of subsystem in(n,k)-star graph according to different partition methods,respectively.In the process of calculating the MTTF of subsystem of(n,k)-star graph,we prove the MTTF Ti by matrix theory in a more clear way;and when the system is divided along any dimension,we solve the problem of computing the number of nodes that can cause the system to move from state Si to state Si+1.Through the comparison of the mean time to failure Ti and T'i obtained by fixed partition method and non-fixed partition method respectively,we conclude that the reliability is comparatively higher when(n,k)-star graph is partitioned by non-fixed method.In the fourth chapter,we obtain the g-good-neighbor diagnosability of(n,k)-star graph under PMC model,and show that(?)furthermore,the g-good-neighbor diagnosability of(n,k)-star graph under MM*model is(?)...