A novel reconfiguration scheme for 2-D processor arrays

A novel reconfiguration scheme is proposed to achieve a highly successful reconfiguration rate for two-dimensional processor arrays with fixed interconnection resources. The authors use a flexible spare allocation scheme and thereby achieve a spare allocation pattern which maximizes the utilization of the given interconnection resources. However, some spare allocations may not result in the successful reconfiguration of a logic array due to the lack of necessary resources. The rationale behind this approach is that the probability of the occurrence of allocation patterns causing such resource conflicts is pretty low. Furthermore, the rare resource conflicts may be resolved by the proposed resolution techniques. By utilizing the given interconnection resources much more efficiently, the proposed scheme achieves a higher reconfiguration rate than a previous design of similar approach. The complexity of the reconfiguration algorithm is O(N/sup 2/).<>