Analysis of a Fault-Tolerance Scheme For Processor Ensembles

The problem of designing faulttolerant binary trees has been extensively studied in the literature. This paper analyzes a locally redundant scheme (LR-Scheme) for designing fault-tolerant processor ensembles. The LR-Scheme is general enough to apply to several interconnection topologies including nonplanar topologies. Systems incorporating the LRScheme can be laid out in an area-efficient manner. A switching structure for reconfiguration is presented and a detailed model for the yield analysis of the LR-Scheme, that takes into account processor, switch, and link failures is developed. Negative binomial distribution is used for the yield statistics as it best fits the empirical data. This model is used to compare the yield (with and without fault tolerance) of some architectural topologies. A dynamic analysis that analyzes the effect of residual redundancy on the improvement of operational system reliability is presented. Our analysis reveals an appreciable improvement in the yield and operational system-reliability when the LR-Scheme is used. A qualitative comparison of the LR-Scheme with existing schemes establishes the strength of the LR-Scheme from both yield and reliability points of view. An important point of this analysis is that it includes the reliability of switches and links unlike previous analyses of fault tolerant schemes. Our empirical results show that ignoring switch reliability could result in appreciable overestimate of the system reliability.