New Algorithms for Permutation Passibility Behaviour of Some Irregular Multistage Interconnection Networks

Abstract

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 hardware and software organizations that are best suited for general purpose parallel processing. In order to operate more efficiently a network is required to provide low latency and be able to handle large amount of traffic. Multistage Interconnection networks (MINs) play a vital role in the performance of these parallel multiprocessor systems. In multistage interconnection networks, the fixed interstate connections between 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 inputs to outputs. One very important parameter in measuring the performance of MINs is the permutation passability and the average path-length. The MINs can be Uniquepath or multi-path. The Unique-path MINs do not have fault tolerance at all. A multi-path MIN has fault-tolerance at each stage of the network. Also, It can easily be depicted from the construction of the Irregular networks that they are going to give better performance in terms of the average path length. For example in the best cases the source to destination path length in the Multi-path MIN the FT[2] is 2 and it is considerably more for the regular networks (3 or more, such as ASEN-2[3] it is 3). Therefore, FT is a strong candidate for such an analysis. Not many such studies have been reported in the literature. Therefore, new algorithms for the permutation passability of MDOT [1–2] and FT irregular MINs have been developed.