The KR-Benes Network: A Control-Optimal Rearrangeable Permutation Network
| dc.creator | Kannan, Rajgopal | |
| dc.date | 2003-09-06 | |
| dc.date | 2004-06-21 | |
| dc.date.accessioned | 2026-07-07T03:20:17Z | |
| dc.date.available | 2026-07-07T03:20:17Z | |
| dc.description | The Benes network has been used as a rearrangeable network for over 40 years, yet the uniform $N(2 \log N-1)$ control complexity of the $N \times N$ Benes is not optimal for many permutations. In this paper, we present a novel $O(\log N)$ depth rearrangeable network called KR-Benes that is {\it permutation-specific control-optimal}. The KR-Benes routes {\it every} permutation with the minimal control complexity {\it specific} to that permutation and its worst-case complexity for arbitrary permutations is bounded by the Benes; thus it replaces the Benes when considering control complexity/latency. We design the KR-Benes by first constructing a restricted $2 \log K +2$ depth rearrangeable network called $K$-Benes for routing $K$-bounded permutations with control $2N \log K$, $0 \leq K \leq N/4$. We then show that the $N \times N$ Benes network itself (with one additional stage) contains every $K$-Benes network as a subgraph and use this property to construct the KR-Benes network. With regard to the control-optimality of the KR-Benes, we show that any optimal network for rearrangeably routing $K$-bounded permutations must have depth $2 \log K + 2$, and therefore the $K$-Benes (and hence the KR-Benes) is optimal. | |
| dc.description | 18 pages, 11 figures, website http://www.csc.lsu.edu/~rkannan V3: Proved the (previous) Conjecture on Optimality of K-Benes | |
| dc.identifier | https://arxiv.org/abs/cs/0309006 | |
| dc.identifier | http://arxiv.org/abs/cs/0309006 | |
| dc.identifier | IEEE Transactions on Computers, Vol. 54, No. 5, pp. 534-544, May 2005. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31771 | |
| dc.subject | Networking and Internet Architecture | |
| dc.subject | Computational Complexity | |
| dc.subject | C.2.1 | |
| dc.title | The KR-Benes Network: A Control-Optimal Rearrangeable Permutation Network | |
| dc.type | text |