Control-Optimal Rearrangeable Permutation Network

Title: Control-Optimal Rearrangeable Permutation Network

Abstract: This research aims to improve the control complexity of rearrangeable networks, specifically the Benes network, which has been in use for over four decades. The authors present a novel network called the KR-Benes, which is permutation-specific and control-optimal. It routes every permutation with the minimum control complexity specified to that permutation and its worst-case complexity for arbitrary permutations is bounded by the Benes. This makes the KR-Benes network the optimal choice for control-optimality.

Methodology: The research begins by introducing the concept of rearrangeable networks, focusing on the Benes network. It explains the looping algorithm used for routing in the Benes network, which has a control complexity of N(2 log N - 1). The authors then introduce the K-Benes network, a restricted 2logK + 2 depth rearrangeable network designed to route K-bounded permutations with control 2NlogK. They show that the N × N Benes network, with one additional stage, contains every K-Benes network as a subgraph. This property is used to construct the KR-Benes network.

Results: The main result of this paper is that the KR-Benes network is permutation-specific and control-optimal. It shows that any optimal network for rearrangeably routing K-bounded permutations must have depth 2logK + 2, and therefore the K-Benes (and hence the KR-Benes) is optimal.

Implications: The implications of this research are significant. By improving the control/hardware complexity of rearrangeable networks, the KR-Benes network has the potential to greatly impact various fields such as shared-memory multiprocessor systems, telecommunication networks, and optical switching networks. It could lead to more efficient and cost-effective networks, especially in high-speed applications.

Link to Article: https://arxiv.org/abs/0309006v4 Authors: arXiv ID: 0309006v4