Self-restructuring in Fault Tolerant Architecture: Processor Arrays with Spares

Recently, high-speed and high-quality technologies for processing many kinds of information have become essential and will become more and more necessary in the future. For such needs, parallel computer systems composed of many processing elements (PEs) are used and it is important to make high reliable systems which is called "fault-tolerant computer systems". As VLSI technology has developed, the realization of parallel computer systems using multi-chip module (MCM) or wafer scale integration (WSI) has been considered so as to enhance the speed of the computers, decrease energy consumption and sizes, and so on. In such a realization, entire or significant parts of PEs and connections among them are connected or implemented on a board or wafer. Therefore, the reliability and/or yield of the system may become drastically low if there is no strategy for coping with faults or defects. In realizing such systems as well as parallel computer systems, in order to restore the correct computation capabilities of the systems with faults, it must be reconfigured appropriately using spare PEs so that the faulty PEs are eliminated from the computation paths by replacing faulty PEs with healthy spare PEs and the remaining healthy PEs maintain correct logical connectivity among them. Various strategies to reconfigure a faulty physical system into a fault-free target logical system are described in the literature. Some of these techniques employ very powerful reconfiguring systems that can repair a faulty processor array with almost certainty, even in the presence of clusters of multiple faults. However, the key limitation of these techniques is that they are executed in software programs to run on an external host computer and they cannot be designed and implemented efficiently within a system. If a faulty system can be self-reconfigured by a built-in circuit or network, the system down time is significantly reduced. Furthermore, the system will become more reliable when it is used in such environments that the fault information cannot be monitored externally and manual maintenance operations are difficult.