## Abstract

An array grid model based on single-track switches is proposed. A reconfigurability theorem is developed to provide the theoretical footing for novel reconfiguration algorithms for the fabrication-time and run-time processing. For fabrication-time yield enhancement, the problem of finding a feasible reconfiguration using global control can be reformulated as a maximum independent set problem. An existing algorithm in graph theory is adopted to solve this problem. The simulations conducted indicate that the algorithm is computationally very efficient; therefore, it may also be applicable to certain run-time fault tolerance. In real-time fault tolerance, the propagation time of data/control signals between the host computer incurred in the global control is often prohibitively long; therefore, only distributed processing is feasible. Based on the same reconfigurability theorem, a distributive reconfiguration algorithm is developed for (asynchronous) array processors.

Original language | English (US) |
---|---|

Pages (from-to) | 501-514 |

Number of pages | 14 |

Journal | IEEE Transactions on Computers |

Volume | v |

Issue number | n |

State | Published - 1992 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics