Fault-tolerant array processors using single-track switches

Sun Yuan Kung, Shiann Ning Jean, Chih Wei Chang

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


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 languageEnglish (US)
Pages (from-to)501-514
Number of pages14
JournalIEEE Transactions on Computers
Issue numbern
StatePublished - 1992

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Fault-tolerant array processors using single-track switches'. Together they form a unique fingerprint.

Cite this