Efficient spare allocation in reconfigurable arrays

The issue of yield degradation due to physical failures in large memory and processor arrays is of significant importance to semiconductor manufacturers. One method of increasing the yield for iterated arrays of memory cells or processing elements is by incorporating spare rows and columns in the die or wafer which can be programmed into the array. This paper addresses the issue of computer-aided design approaches to optimal reconfiguration of such arrays. The paper presents the first formal analysis of the problem. The complexity of optimal reconfiguration is shown to be NP-complete for rectangular arrays utilizing spare rows and columns. In contrast to previously proposed exhaustive search and greedy algorithms, this paper develops a heuristic branch and bound approach based on the complexity analysis, which allows for flexible and highly efficient reconfiguration. Initial screening is performed by a bipartite graph matching algorithm.