Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations

Abstract

The Benes binary network can realize any one-to-one mapping of its 2ⁿinlets onto its 2ⁿoutlets. Several authors have proposed algorithms which compute control patterns for this network from any bijection assignment. However, these algorithms are both time-consuming and space-consuming. In order to meet the time constraints arising from the use of a Benes network as the alignment network of a parallel computer, another approach must be chosen. In this paper, we consider typical functions and show that the set of needed permutations of data is very small, as compared to the whole symmetric group. We gather frequently used bijections into five families. For each family we present an algorithm that can control the two-state switches on the fly, as the vector of data passes through the network. Finally, we describe one possible scheme to implement an instruction "Trigger a Frequently Used Bijection."