On Performance Analysis of Fault-Tolerant Multi-Stage Interconnection Networks

Abstract

With the present state of technology building multiprocessor system with hundreds of processors is feasible. A vital component of these systems is the interconnection network (IN) that enables the processors to communicate among themselves or with memory units. Any processor in multiprocessor system should be able to directly address every shared memory module through the IN. As a result, the performance of a multiprocessor system rests primarily on the design of its IN. In recent years, much research on multiple-path multi-stage networks (MINs) has been reported. Each network proposed aims to achieve a different objective. In this thesis, irregular and regular MINs are analyzed in terms of performance criteria’s namely, permutation passibility, reliability, bandwidth and cost. Also two new MINS, MABN (Modified Augmented Baseline Network) and IABN (Irregular Augmented Baseline Network) have been proposed, modifying the existing ABN (Augmented Baseline Network). IABN is an irregular network, whereas MABN and ABN are regular networks. Regular networks contain same number of switches in each stage; interconnection pattern also remains same in each stage. The permutation passibility determines the data routing capability in presence and absence of faults. The reliability of a network is evaluated in terms of MTTF (Mean Time To Failure), under the criteria of full access i.e. a network is assumed faulty if there is any source-destination pair that cannot be connected because of faulty components in the network. Here consideration is only on 2 bounds i.e. Upper Bound (UB) and Lower Bound (LB). Results of permutation passibility and reliability show that the proposed networks perform better than ABN, especially the IABN. It is also found that bandwidth; probability of acceptance, throughput, processor utilization and cost of IABN is much better than MABN and ABN. Values of these parameters for MABN are comparable to that of ABN, since both are regular networks. Thus the proposed irregular ABN (IABN) provides an improvement over the performance of regular networks, showing the supremacy of irregular networks over regular networks.