Efficient Reconfiguration Algorithms for Degradable VLSI/WSI Arrays

The issue of developing efficient algorithms for constructing a flawless subarray from a defective VLSI/WSI (wafer scale integration) array is addressed in this paper. The array consists of identical elements such as processors or memory cells embedded in a switch lattice in the form of a rectangular grid. In contrast to the redundancy approach in which some elements are dedicated as spares, all the elements in the degradation approach are treated in a uniform way. Each element can be either fault-free or defective, and a subarray which contains no faulty element is derived under constraints of switching and routing mechanisms. Although extensive literatures exist concerning spare allocation and reconfiguration in arrays with redundancy, little research has been published on optimal reconfiguration in a degradable array. A graph formulation is used to describe the problem and reconfiguration is found to relate to finding an independent set of a graph. Efficient heuristic algorithms are presented to determine a target subarray from the defective host array.