Analysis and simulation of multistage interconnection networks under non-uniform traffic

Abstract

The performance of multistage interconnection networks is known to degrade severely with nonuniformities in the traffic distribution. In the present work, on the basis of simulation and analysis, the authors study the effect of nonuniform traffic patterns simulation and analysis when two multistage networks are used in parallel to interconnect processors and memory modules in a shared-memory system. The networks considered are identical copies of buffered multistage networks. The authors consider the following two strategies for distributing the total traffic between the two networks and study the conditions under which each strategy is effective: (1) distribute the traffic randomly among the networks; (2) route the nonuniform component of the traffic to one network and the uniform component to the other. They also derive approximate analytical expressions for the time taken for tree saturation to occur with a single hot spot and the time taken for recovery when the hot spot disappears. The time taken for tree saturation to occur under a single hot spot is several times that of a single network, thereby demonstrating the effectiveness of dual networks in tolerating short bursts of nonuniform traffic.