THE FULL-USE-OF-SUITABLE-SPARES (FUSS) APPROACH TO HARDWARE RECONFIGURATION FOR FAULT-TOLERANT PROCESSOR ARRAYS

A general approach to hardware reconfiguration is proposed for VLSIAVSI fault-tolerant processor arrays. The technique, called FUSS (full use of suitable spares), 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 there is a linear relationship between the array size and the area of interconnect required for 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's entries. The surplus vector is progressively updated after each column is reconfigured. The reconfiguration is successful when the surplus vector becomes null. Simple FUSS is discussed in detail and evaluated. 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 is far better than the probability of survival of existing schemes with similar complexity in execution time and interconnection hardware. © 1990 IEEE