An efficient channel routing algorithm for defective arrays

Although a number of defect-tolerance schemes for two-dimensional VLSI/WSI (wafer scale integration) processor arrays have been proposed in the literature, none is efficient enough always to guarantee a restructured array that utilizes all the good processors on the wafer while using only a limited number of interconnection channels. The authors present a restructuring scheme that can achieve this (no matter how severely clustered the faults) with a maximum channel width of three, provided the total number of faults in the array are within some stated limits. For practical size arrays, this limit is large enough so as not be be restrictive in practice. Moreover, the scheme also works extremely well, in a probabilistic sense, for a larger number of faults, when the failed processors are severely clustered.<>