Improving Rearrangeable Networks: A Quest for Optimal Control Complexity

Title: Improving Rearrangeable Networks: A Quest for Optimal Control Complexity

Research Question: Can we design a rearrangeable network that optimally routes every permutation with minimal control complexity, improving upon the standard Benes network?

Methodology: We propose a novel network called the KR-Benes, which is permutation-specific and control-optimal. We first design a restricted network called the K-Benes for optimally routing K-bounded permutations with control 2NlogK. We then show that the NxN Benes network itself (with one additional stage) contains every K-Benes network as a subgraph, allowing us to construct the KR-Benes.

Results: We present a strong conjecture that the optimal network for rearrangeably routing K-bounded permutations has a depth of 2 logK+2 stages, making the K-Benes (and hence the KR-Benes) control-optimal. We also show that any optimal network must have a depth at least 2 logK+1, meaning the KR-Benes is within an additive linear factor of the optimal for that permutation.

Implications: The KR-Benes network is a significant improvement over the standard Benes network, offering lower latency and control overhead for many permutations. This could have tremendous implications for the design of shared-memory multiprocessor systems, telecommunication networks, and other applications that rely on rearrangeable networks. The results also provide valuable insights into the design of optimal rearrangeable networks for arbitrary permutations.

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