Performance analysis of multistage interconnection networks with a new high-level net model

This paper introduces a new high-level net, named S-net, for modelling multistage interconnection networks. Based on the stochastic behaviour of GSPN and coupled with the flexibility and compactness of Coloured Petri net uses tokens for storage and manipulation of data besides modelling the flow of control. It requires exactly 3 N/2 number of places to model an N x N multistage interconnection network irrespective of the number of stages and buddy properties of the network. A polynomial time algorithm is developed to check feasibility of mapping a permutation using the proposed S-net model of an MIN. (c) 2005 Elsevier B.V. All rights reserved.