A General Performance Model for Multistage Interconnection Networks

Abstract. Multistage Interconnection Networks (MINs) with crossbar switches are used to interconnect processors and memory modules in parallel multiprocessor systems. In this paper we analyze the general case of MINs, made of kk switches with nite, innite or zero length buers (unbuered). The exact solution of the steady state distribution of the rst stage is derived for all cases. We use this to get an approximation for the steady state distributions in the second stage and beyond. In the case of unbuered switches we reach the known exact solution for all the stages of the MIN. Our results are validated by extensive simulations