Performing permutations on interconnection networks by regularly changing switch states

In this paper, we present an algorithm for performing permutations of messa ges on multistage interconnection networks. Permutations of messages are ne eded in many parallel algorithms. The proposed algorithm is feasible for an y networks that can connect each input to each output using a set of N nonb locking connections, where N is the number of ports on the network. Message s are segmented into N submessages that are sent independently in each time step. For any permutation, the settings of switches are changed with fixed patterns. Partitioning of the network into independent subnetworks is also supported, each capable of simultaneously routing a different permutation.