Improving Rearrangeable Networks: A New Approach to Optimize Control Complexity

Title: Improving Rearrangeable Networks: A New Approach to Optimize Control Complexity

Abstract: This research aims to improve the control complexity of rearrangeable networks, specifically focusing on the Benes network. The main objective is to design a permutation-specific, control-optimal network that can route arbitrary permutations with minimal control complexity. The paper presents a novel network called the KR-Benes, which is shown to be permutation-specific and control-optimal. The KR-Benes network is constructed using a modified Benes network looping algorithm and a restricted rearrangeable network called the K-Benes. The paper also provides a strong conjecture that the optimal network has a depth of two more stages than the provable lower bound, making the K-Benes and hence the KR-Benes network control-optimal.

Main Research Question: Can we design a permutation-specific, control-optimal rearrangeable network that improves upon the control complexity of the standard Benes network?

Methodology: The paper uses graph theory and control complexity analysis to design the KR-Benes network. The methodology involves:

1. Designing a restricted rearrangeable network called the K-Benes for optimally routing K-bounded permutations with control 2NlogK. 2. Showing that the N×N Benes network itself contains every K-Benes network as a subgraph. 3. Using this property to construct the KR-Benes network, which is shown to be permutation-specific and control-optimal.

Results: The main results of the paper include:

1. A novel KR-Benes network that is permutation-specific and control-optimal. 2. A strong conjecture that the optimal network has a depth of two more stages than the provable lower bound, making the K-Benes and hence the KR-Benes network control-optimal.

Implications: The implications of this research are significant for the field of rearrangeable networks. The KR-Benes network presents a new approach to optimize control complexity, which can lead to improved hardware and control efficiency in various applications, such as shared-memory multiprocessor systems, telecommunication networks, and internet routers. The paper also provides a new methodology for designing permutation-specific, control-optimal networks, which can be applied to other rearrangeable network problems.

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