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. This book concerns fault-tolerant systems consisting of many PEs, mainly mesh-connected processor arrays. A mesh-connected processor array is a kind of form of massively parallel computing systems which consist of hundreds of PEs and have regular and modular structures, small wiring length between PEs, and high scalabilities. Here, self-reconfiguration of processor systems with spares using built-in digital circuits are focused on and spare arrangements together with networks connecting among PEs and reconfiguration algorithms with digital circuits are described, considering the number of spares, reconfiguration algorithms and their hardware realizations (built-in circuits), etc. where spares are arranged on the sides or diagonal of arrays. The effectiveness of the systems is evaluated in terms of the survival rates (successfully reconfigured rates) for the number of faults, and the array reliabilities (successfully reconfigured probabilities under the condition that each PE is equally reliable).

Table of Contents:
Introduction.- Self-restructuring of two-dimensional arrays.- Self-restructuring of three-dimensional arrays.- Self-restructuring of tree arrays.