On Fault Tolerant Irregular Multistage Interconnection Networks

Abstract

The basic way to achieve high-performance, high-reliable computing is to use multiple processors linked by one or more shared buses. Such multiple bus systems offer the advantage of low hardware cost, and graceful degradation in the presence of faults. There are many different ways to organize computational structures to exploit parallelism. Many research efforts around the world are being conducted with the purpose of determining the hardware and software organizations that are best suited for general purpose parallel processing. The communication subsystems linking processors, memory modules and input/output controllers in a parallel processing subsystem is one of its most important architectural features and has a profound impact on system capabilities, performance, size and cost. An interconnection network of the processors that provides the desired connectivity and performance at minimum cost is required for communications in parallel processing systems with a large number of components. Multistage interconnection networks play an important role in parallel computing systems. In multistage interconnection the fixed inter stage connections between adjacent stages exist with a number of switches at each stage that are dynamically set to establish the desired connection to route the requests from input to the output. The distribution of switches as well as their complexity is very important in designing multistage interconnection networks. The important issues in the study of multistage interconnection networks are estimation of complexity, fault tolerance, reliability and cost. FT network is a single switch fault-tolerant. If both switches in a loop are simultaneously faulty then clearly some sources are disconnected from some destinations. In this thesis two fault-tolerant irregular MINs FT-1 and FT-2 are proposed. FT-1 Network is a multipath, dynamic MIN which is a modified form of Four Tree (FT) Network. It has been found that FT-1 network is having better permutation capabilities, less cost and high reliability than FT whereas FT-2 have decreased path length, high permutation capability and is more fault-tolerant.