On the configuration of degradable VLSI/WSI arrays
C.P. Low, H.W. Leong · 2002
The authors consider the problem of reconfiguring VLSI/WSI arrays via the degradation approach. In this approach, all elements are treated uniformly and no elements are dedicated as spares. The goal is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some specified minimum. This problem has been shown to be NP-complete under various switching and routing constraints. However, it is shown that a special case of the reconfiguration problem with row bypass and column rerouting capabilities, is solvable in polynomial time using network flows. Using this result, a new fast and efficient reconfiguration algorithm is proposed. Empirical study shows that the new algorithm indeed produces good results in terms of the percentages of harvest and degradation of VLSI/WSI arrays.