FAULT-TOLERANT MINs FOR PARALLEL PROCESSING

Abstract

This thesis addresses the techniques for the design of reliable fault-tolerant multistage interconnection networks (MINs) used in multiprocessor systems. Statically as well as dynamically reroutable MINs are studied. Methods for the construction of regular fault-tolerant MINs are described. Their characteristics pertaining to performance and reliability are analyzed and compared with the previously proposed networks. It is shown that these multipath regular MINs are of higher reliability than other MINs having similar fault-tolerant capabilities and give better performance. The effect of component failures on the performance of these networks is also evaluated. It is observed that although faults do not significantly affect the overall network performance, they degrade the performance of some parts of the system resulting in an increase in network cycle time. New type of irregular fault-tolerant multistage networks are introduced and analyzed. Various algorithms are developed to study their characteristics. Compared to regular networks, these irregular networks have lesser hardware complexity and more computational speed because of their shorter path lengths between a processor and its favourite memory modules. The results of analysis show that it is worthwhile to employ the proposed irregular techniques in designing faulttolerant MINs. Modular implementation has been proposed to simplify the design of statically reroutable networks. The proposed fault-tolerant networks have many attractive features for use in multiprocessor systems.