Permutation mapping for MIN using high level net models

This paper proposes to structurise the analysis of the performance of Multistage Interconnection Networks (MINs). A new type of High level net, named Modified Petri net (MP-net) which has subsequently been refined to S-net, has been defined in the process. Essentially, a variation of Coloured and Stochastic nets, this S-net has been shown to be a very effective tool for dynamic modelling of MINs. The results reported so far in the context of performance estimation of MINs, are mainly based on direct combinatorial analysis of the concerned networks with very little consideration towards the modelling aspects. The outcome of the present research work may be utilized for modelling of a wide range of MINs consisting of 2×2 crossbar switches. Multistage redundant path networks like Omega and non-redundant path networks such as Baseline network have been considered and modelled with S-net as a case study. It has also been established that using S-net, a MIN of N×N size can be modelled with 3N/2 number of places as against O(Nlog₂N) no. of switching elements for the equivalent MIN. Using the S-net model connectivity status of constituent cross-bar switches of a MIN, has been represented in a matrix, proposed to be termed as Control matrix. An algorithm has been developed to study and modify entries of the control matrix to analyse performance of MIN using S-net model