Hardware reconfiguration for fault-tolerant processor arrays

In large VLSI/WSI arrays, improved reliability and yield can be obtained through reconfiguration techniques. In fault tolerance design, redundancy is used to offset faults when they occur in the arrays. Since redundant components are themselves susceptible to faults, their number must be a minimum. This also implies that an efficient reconfiguration scheme is preferred, i.e., one that can use as many spare components as possible so that unnecessary waste of spares is reduced. In this thesis, hardware reconfiguration for fault-tolerant processor arrays is discussed. First, a taxonomy for reconfiguration techniques is introduced, and several schemes are surveyed and classified. This taxonomy can be used to introduce, explain, compare, study, and classify new reconfiguration schemes. Next, an extension to reconfiguration technique is presented. Two special cases of the scheme are simulated and their results compared and studied. Finally, a new approach to hardware reconfiguration, called FUSS (Full Use of Suitable Spares), is proposed for VLSI/WSI fault-tolerant processor arrays. FUSS uses an indicator vector, the surplus vector, to guide the replacement of faulty processors within an array. Analytical study of the general FUSS algorithm shows that a linear relationship between the array size and the area of interconnect is required for the reconfiguration to be 100% successful. In an instance of FUSS, called simple FUSS, reconfiguration is done by simply shifting up or down faulty processors along their corresponding columns according to the surplus vector\u27s entries. The surplus vector is progressively updated after each column is reconfigured. The reconfiguration is successful when the surplus vector becomes the null vector. Simulations show that when the number of faulty processors is equal to that of spare processors, simple FUSS can achieve a probability of survival as high as 99%; this it far better than the probability of survival of existing schemes with similar complexity in execution time and interconnection hardware. Simple FUSS is presented and evaluated. Its hardware implementation, probability of survival, reliability, extensible variations, and applications are discussed in detail. While designed for two-dimensional arrays, FUSS can also be extended to other computational topologies