The KR-Benes Network: A Control-Optimal Rearrangeable Permutation Network based on K-bounded Permutations
Rajgopal Kannan · arXiv (Cornell University) · 2003
The Benes network has been used as a rearrangeable network for over 30 years for applications in circuit switching and packet routing. However the O(N log N) control complexity of the Benes is not optimal for many permutations. In this paper, we present a novel rearrangeable network that is permutation-specific control-optimal, i.e., it has the lowest control complexity for every input permutation. This network is based on another network we label KR-Benes. The KR-Benes exploits locality properties of permutations (called K-boundedness) and is derived by making some small modifications to the Benes. The KR-Benes network has a depth of 2 logK + 2 stages and a control complexity of O(N log K). The KR-Benes is superior to the Benes from the hardware point of view for K ≤ N / √ 8 and has a lower control complexity when K ≤ N / √ 2. In this paper, we show that any optimal network for rearrangeably routing K-bounded permutations must have depth at least 2 logK + 1. We also provide arguments for conjecturing that the optimal network, in fact has 2 logK + 2 stages, and therefore the KR-Benes is optimal. Finally, we use the KR-Benes to derive the permutationspecific control-optimal network for routing arbitrary permutations. Its control complexity is superior to the Benes in most cases and bounded by the Benes in the worst case.