Efficient reconfiguration by degradation in defect-tolerant VLSI arrays

This thesis addresses the problem of constructing a flawless subarray from a defective VLSI/WSI array consists of identical cells such as memory cells or processors. In contrast to the redundancy approach in which some cells are dedicated as spares, all the cells in the degradation approach are treated in a uniform way. Each cell can be either fault-free or defective and a subarray which contains no faulty cell 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 systematic method based on graph theoretic models is developed to deal with the problem. The complexities of reconfiguration are analyzed for schemes using different switching mechanisms. Efficient heuristic algorithms are presented to determine a target subarray from the defective host array