A Shuffle-Exchange Network with Simplified Control

Abstract

In this paper, a control mechanism for a shuffle-exchange interconnection network of N cells is proposed. With this network it is possible to realize some important permutations in log₂ N shuffle-exchange steps. In the control mechanism presented, the control variables at step k are determined by a Boolean operation of the control variables at step k - 1. The Boolean operation is very simple so that little additional hardware is required for this computation. This control scheme requires only one bit per cell instead of a destination tag of log₂ N bits required by a control mechanism presented previously. The network can be used for the interconnection of memory modules and processors in an array computer, and for the accessing of blocks of consecutive data in large dynamic memories. It is also shown that the shuffle-exchange interconnection network permits the efficient partitioning of an array computer into subarrays to allow for the simultaneous computation of several identical problems.