DESIGN AND ANALYSIS OF EVEN-SIZED BINARY SHUFFLE-EXCHANGE NETWORKS FOR MULTIPROCESSORS

The architecture and performance of binary shuffle-exchange networks of any even size are investigated. It is established that a network with inverted right perpendicular log2N inverted left perpendicular shuffle-exchange stages or a single recirculating stage can provide the connectivity between N inputs and N outputs using a distributed tag-based control algorithm. Control tags depend on both source and destination when N is not a power of two, and can be computed in a simple manner. Several structural and dynamic properties of the network are established, contrasting the behavior of the power-of-two and composite sized systems. The performance of the network in a stochastic environment is also investigated analytically. It is seen that the shuffle-exchange networks behave in much the same way with respect to traffic and buffer capacity, whether or not the system size is a power of two.