On the tradeoff between node degree and communication channel width in shuffle-exchange networks

The architecture of direct connected multiprocessor using the K-ary shuffle-exchange topology is investigated in the presence of node pin-out constraints. These constraints translate into a tradeoff between node degree and width of the communication channels between nodes. A higher order shuffle uses a higher node degree to reduce inter-node distances, but it also results in a lower bandwidth per channel by decreasing its width. A generalization of the K-ary shuffle exchange architecture to non-power-of-K system sizes permits the study of this tradeoff at a fine level, for values of K=2, 3, 4, . . . This study points out that the tradeoff is more complex here than in the family of multidimensional meshes. Very low order shuffles (K<0.5 log₂ N) do not perform well in any of the situations investigated. Among higher order shuffles, the best structure depends upon both the system size and the pin-out constraint, and monotonic reduction in message delays is not guaranteed as the order of the shuffle is increased