Partial rerouting algorithm for reconfigurable VLSI arrays

The problem of reconfiguring a two-dimensional degradable VLSI array under the row and column routing constraints has been shown to be NP-complete. This paper aims to decrease the reconfiguration time to enhance the real time application. A partial rerouting algorithm is proposed in this paper. For a given m × n VLSI array with the fault density ρ, the proposed algorithm runs in O((1 - ρ)·τ~·n) which is far less than O((1 ρ)·m·n), the time complexity of the most efficient algorithm, cited in the literature, where τ~ is far less than m and it is nearly a constant for the small fault density. In addition, the proposed algorithm is exactly the same in harvest as the version reported so far.