Rearrangeability of the Five-Stage Shuffle/Exchange Network for N = 8

Author

Raghavendra, C.S. ; Varma, Anujan

Author_Institution

Univ. of Southern Calif., Los Angeles, CA, USA

Volume

35

Issue

8

fYear

1987

fDate

8/1/1987 12:00:00 AM

Firstpage

808

Lastpage

812

Abstract

In this paper we prove the rearrangeubility of a multistage shuffle/exchange network with eight inputs and outputs consisting of five stages. A lower bound of ( $2 \\log _{2} N - 1$ ) stages for rearrangeability of a Shuffle/exchange network with $N = 2^{n}$ inputs and outputs is known; we show its sufficiency for $N = 8$ . We not only prove the rearrangeability, but also describe an algorithm for routing arbitrary permutations on the network and prove its correctness. In contrast to previous efforts to prove rearrangeability, which rely on topological equivalence to the Benes class of rearrangeable networks, our approach is based on first principles. We also show that two switches in the network are redundant. The results in this paper are useful for establishing an upper bound of ( $3 \\log _{2} N - 4$ ) stages for rearrangeability of a multistage shuffle/exchange network with $N \\geq 8$ , as demonstrated in [12].

Keywords

Multiprocessing, interconnection; Communication switching; Communications Society; Multiprocessor interconnection networks; Parallel processing; Routing; Sorting; Switches; Systems engineering and theory; Upper bound;

fLanguage

English

Journal_Title

Communications, IEEE Transactions on

Publisher

ieee

ISSN

0090-6778

Type

jour

DOI

10.1109/TCOM.1987.1096867

Filename

1096867