Power Efficient Sub-Array in Reconfigurable VLSI Meshes

Given an m x n mesh-connected VLSI array with some faultyelements, the reconfiguration problem is to find a maximum-sizedfault-free sub-array under the row and column rerouting scheme. Thisproblem has already been shown to be NP-complete. In this paper,new techniques are proposed, based on heuristic strategy, to minimizethe number of switches required for the power efficient sub-array.Our algorithm shows that notable improvements in the reduction ofthe number of long interconnects could be realized in linear timeand without sacrificing on the size of the sub-array. Simulationsbased on several random and clustered fault scenarios clearlyreveal the superiority of the proposed techniques.