Reconfiguration of a fault‐tolerant rectangular systolic array

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.