Portal de Periódicos da CAPES

The KR-Benes network: a control-optimal rearrangeable permutation network

2005; Institute of Electrical and Electronics Engineers; Volume: 54; Issue: 5 Linguagem: Inglês

10.1109/tc.2005.84

2326-3814

Rajgopal Kannan,

Genome Rearrangement Algorithms

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 log K + 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 log K + 1.We also provide arguments for conjecturing that the optimal network, in fact has 2 log K + 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.