Efficient reconfiguration scheme for mesh-connected network: the recursive shift approach

Recently, several strategies have been studied to recover faulty processing elements on mesh arrays. S.Y. Kung et al. (1989) proposed a 1½ track model for reconfiguration of mesh arrays and the reconfiguration algorithm based on graph theory by finding compensation paths. However, compensation path scheme does not perform reconfiguration efficiently since the strategy only focuses on faulty processing elements and requires global information. In this paper, we propose a new reconfiguration strategy named recursive shift to recover faulty processing elements on mesh arrays. It is confirmed that our strategy obtains much higher array yield than previous schemes without global information on identical redundant processing elements