Balanced permutations and multistage interconnection networks

Multistage interconnection networks provide communication among processors and memory modules. It is highly desirable to know what permutations can be realized by multistage interconnection networks because parallel algorithms often require permutation-type data transfers. This paper introduces a class of permutations called balanced permutations that are realized by some well-known multistage interconnection networks. Grid-like diagrams called frames are used to identify the balanced permutations. To help design of a multistage interconnection network for implementing a given class of permutations, the paper presents an in-depth analysis of the balanced permutations.