Approximate estimation of reliability, mean time to failure and optimal redundancy of fault-tolerant processor arrays

Fault-tolerant schemes are very important for processor array design because there is a high probability of failure of one or more processors in an processor array of large size. This thesis addresses the problems of estimation and design of fault-tolerant processor arrays (FTPAs) that use hardware redundancy. To incorporate hardware redundancy in an FTPA, it is not only necessary to provide spare components but also to incorporate additional control and reconfiguration circuitry where a single failure can cause the total failure of the array. Because the amount of this hardware (and therefore the probability of a single failure) increases with the number of spares, it is not guaranteed that the additional redundancy always improves the overall FTPA reliability. Given a prescribed value of reliability and/or mean time to failure (MTTF), the necessary number of spare (NNS) is defined as the minimum number of spares needed to achieve the prescribed reliability or MTTF. The optimal number of spares (ONS) is defined as the number of spares for which the reliability or the MTTF of FTPA is maximized. In this thesis, FTPA reliability models are introduced and used to evaluate different types of FTPAs. Several approximated estimate formulas for NNS and ONS of FTPAs are proposed based on these reliability models. In hierarchical FTPA design, it is necessary to choose the size of subarrays for every level in hierarchy as well as the fault-tolerant scheme at that level. A methodology is proposed in this thesis which systematically provides the size of the subarray in a bi-level FTPA and the optimal combination of fault-tolerant schemes by which the overall reliability of an FTPA is maximized. Two joint measures of area, time and reliability are also proposed in this thesis to evaluate and compare the performance of different FTPAs