Interference Analysis of Shuffle/Exchange Networks

Abstract

The use of shuffle/exchange (S/E) interconnection networks in multiprocessor systems has been proposed for several applications. In order to evaluate the potential performance and reliability of such systems, the effects of conflicts involving switch and memory contention should be determined. This paper presents a discrete Markov chain model to study the effects of such contention for S/E networks used in random access application environments. This model is used to derive memory bandwidth (MBW) of the system, with analytic expressions presented for 4 X 4 and 8 X 8 S/E networks. Two cases are considered. First, the model is applied to systems in which all processors issue their access requests synchronously, then this model is used to construct a traffic model which allows the generation of access requests at arbitrary times. The results of the analysis are compared with simulation results and the analytical results derived by Bhandarkar for the full Crossbar network. Besides the MBW, other interference-related parameters such as blocking probability, traffic, loading, and blocking delay are discussed. In particular, the loading effect of a 16 X 16 S/E network obtained from the model is compared with the results of the simulation from Wirsching's CONET model.