A network flow approach to the reconfiguration of VLSI arrays

A technique for reconfiguring a two-dimensional VLSI array with faulty cells is presented. A network flow model of the problem is used to provide an algorithm for connecting the functional cells of the array so that they simulate a fault-free array of smaller size. The interconnection wires are routed inside horizontal and vertical channels according to the Manhattan model. Experimental results indicate that the algorithm has good performance in practice.