Fast reconfiguring mesh-connected VLSI arrays

Mesh-connected VLSI array has a regular and modular structure and allows fast implementation of most signal and image processing algorithms. This paper aims to propose a fast reconfiguration algorithm for finding an maximum sized sub-array in two-dimensional degradable VLSI arrays. The older approach for row-selection is improved such that the time complexity in row-selection is reduced from O((1-ρ)·m·n) to O((1-ρ)·n) for a given array with size m×n, where ρ is the fault density. The proposed algorithm only reroutes a small sized sub-set of the logical arrays which possibly contains the maximal sized target array. The time complexity of the latest reconfiguration algorithm cited in the literature is reduced from O((1-ρ)·m²·n) to O((1-ρ)·k·m·n) without loss of performance, where k≪m and k is nearly a constant for small ρ.