A reconfigurable and fault-tolerant VLSI multiprocessor array

Multiprocessor arrays have the property of regularity, enabling a low-cost VL81 implementation. However, multiprocessor systems with a fixed structure tend to be error prone and restricted to specialized applications, which makes them less attractive to the semiconductor industry. Consequently, reconfigurability and fault-tolerance are desirable features of a multiprocessor array. A multiprocessor array with a flexible structure can be adapted to many applications and may restructure itself upon failure of a processor, to avoid using faulty processors. The objective of this work is to demonstrate the feasibility of a multiprocessor array having these properties. An example of such an array is introduced, and distributed structuring algorithms for it are presented. A novel strategy for internal testing and for identification of faulty processors is developed, and the structuring algorithms are modified to accommodate faulty processors.