Reconfiguration of a fault‐tolerant rectangular systolic array

Yoshinao Suzuki, Tomio Hirata, Masaharu Imai, Masafumi Yamashita, Toshihide Ibaraki

Research output: Contribution to journalArticlepeer-review


Fault‐tolerant designs which incorporate redundancy to improve the yields of VLSI chips are well known. In such designs flaws in a chip are excluded by reconfiguration. This paper discusses the reconfiguration problem of a rectangular systolic array: Given a rectangular systolic array, construct a flawless array of maximum size. Three levels of constraints on reconfiguration are considered, and for each constraint the problem is proved to be NP‐complete and an approximation algorithm is proposed.

Original languageEnglish
Pages (from-to)79-89
Number of pages11
JournalSystems and Computers in Japan
Issue number1
Publication statusPublished - Jan 1 1988

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Reconfiguration of a fault‐tolerant rectangular systolic array'. Together they form a unique fingerprint.

Cite this