Finding minimum interconnect sub-arrays in reconfigurable VLSI arrays

Shorter total interconnect and fewer switches in a VLSI array definitely lead to less capacitance, power dissipation and dynamic communication cost between the processing elements (PEs). This paper presents techniques to find a logical (target) array that has shorter interconnect and fewer switches in a reconfigurable VLSI array with faulty PEs. The proposed algorithm initially searches for a sub-array on the host array, which contains the minimum number of the faults. Then it reroutes the sub-array, rather than the whole host array as was done in previous algorithm, to an approximate target array whose size is less then but close to the size of the target array. Finally, the target array is obtained by simple extension of the approximate target array. Experimental results show that the proposed algorithm can construct a target array with much shorter total interconnect. The improvement over the previous work is up to 68% in terms of the interconnect redundancy for the case of the cluster faults.