On Irregular Multistage Interconnection Networks

Abstract

Multi-stage Interconnection Networks (MINs) play a very important role in the Parallel computing system. In MINM, the fixed inter-stage connections between the adjacent stages exist with a number of switches at each stage that are dynamically set to establish the desired connections to route the requests from the inputs to the outputs, MINs differ in the usage of switches and inter-stage connection patterns used. The important factors in the study of MINs are estimation of Complexity, Fault-tolerance, Communication efficiency, Performance and Cost. This thesis analyses various Regular and Irregular MINs had been presented, providing in-depth knowledge of interconnection possibilities, Fault-tolerance and Performance parameters which is useful for researcher in the design of High-Performance, Fault-free and Efficient networks. A new Irregular MIN has been proposed named Modified Four-Tree (MFT) modifying the existing Four-Tree (FT) MIN. The performance of Irregular MINs has been analysed in terms of Reliability, Cost and Permutation passable parameters. The reliability of various Irregular MINs has been analysed in terms of Mean-time -to-failure (MTTF). This analysis shows that FDOT-2 MIN gives better performance compared to most of the Irregular MINs. Also, it can be deduced from this analysis that MTTF/Cost is better for Irregular MINs is lower compared to Regular as they use lesser number of switches in total. The Permutation passable capability determines the data routing capability, which dominates performance for large sizes. The Irregular MINs are analysed for this parameter. The results of the analysis show that the MFT is better in terms of Cost and Permutation passability than most of the Irregular MINs. The Reliability and Fault-tolerance of MFT are comparable TO ft. thus, The MFT provides and improvement over the performance of the existing Irregular MINs. The comparison of the analysis with Regular MINs shows that the Irregular MINs are more Cost-effective, Reliable and efficient especially for higher network sizes. Hence, it can be deduced from this analysis that the Irregular Mins can replace regular and thereby provide better performance.