Real-time reconfiguration of two-dimensional VLSI arrays

The extension of index mapping to the reconfiguration of two-dimensional VLSI arrays in real time is presented. Index mapping is implemented by a two-operator technique which assigns to a faulty cell a unique fault free space. This process is accomplished by a decentralized parallel approach which finds the appropriate of deformation for the recomputation of the indices and their mapping. It is proved that this process is O(1) if the number of simultaneously faulty cells is restricted to one. The proposed technique can also be applied efficiently in the presence of multiple (accumulated) faulty cells. It is shown that the hardware overhead required for routing and switching is very small. It is proved also that the proposed technique provides an optimal solution to reconfiguration if cells fail according to certain patterns. Illustrative examples are shown