Rearrangeability of 7-stage 16 × 16 shuffle exchange networks

Abstract

It has long been an outstanding conjecture that any (2n - 1)-stage shuffle exchange network (Omega network) is rearrangeable for 2ⁿ × 2ⁿ. Many researchers have failed to prove this conjecture, including a recent one established by Hasan. However, nobody has pointed out its fallacy. Therefore, as one of the objectives, this paper shall clarify this fact. Since the case of n = 3 has been proven by many researchers 12, this paper uses a constructive approach to prove that when n = 4, the 7-stage 16 × 16 shuffle exchange network is also rearrangeable. The paper also presents the model of a balanced tree to avoid internal conflict, the representation of permutations using a connection graph and loop graph, and the concepts of symmetry graph and identical transform. Based on graphic composition and bipartition, the permutations 16 × 16 are divided into five classes, with five assignment algorithms proposed. These algorithms are simpler, clearer and easier to program. The techniques used for n = 4 may provide hints for the general case of n > 4.

References

1. Kim K, Raghavendra C S . A simple algorithm to routearbitrary permutations on 8-input 5-stage shuffle/exchange network. In: Proceedings of the 5th International ParallelProcessing Symposium. 1991, 398–403
2. Raghavendra C S, Varma A . Rearrangeability of the 5-stageshuffle/exchange network for N =8. In: Proceedings of 1986 InternationalConference on Parallel Processing. 1987, 119–122
3. Stone H S . Parallel processing with the perfect shuffle. IEEE Transactions on Computers, 1971, C-20(2): 153–161. doi:10.1109/T-C.1971.223205
4. Lawrie D H . Access and alignment of data in an array processor. IEEE Transactions on Computers, 1975, C-24(12): 1145–1155. doi:10.1109/T-C.1975.224157
5. Raghavendra C S . On the rearrangeability conjecture of (2log₂N - 1)-stage shuffle/exchangenetwork. IEEE Computer Society TechnicalCommittee on Computer Architecture Newsletter. 1994, 95, 10–12
6. Wu C L, Feng T Y . On a class of multistageinterconnection networks. IEEE Transactionson Computers, 1980, C-29(8): 694–702. doi:10.1109/TC.1980.1675651
7. Wu C L, Feng T Y . The universality of the shuffle-exchangenetwork. IEEE Transactions on Computers, 1981, C-30(5): 324–332. doi:10.1109/TC.1981.1675798
8. Benes V E . Proving the rearrangeability of connecting networks by group calculations. Bell System Technology Journal, 1975, 54: 421–434
9. Parker D S . Notes on shuffle/exchange-type switching networks. IEEE Transactions on Computers, 1980, C-29(3): 213–222. doi:10.1109/TC.1980.1675553
10. Linial N, Tarsi M . Efficient generation of permutationswith the shuffle/exchange network. TechnicalReport, UCLA Computer Science Department, 1982
11. Sovis F . Uniformtheory of the shuffle-exchange type permutation networks. In: Proceedings of the 10th Annual InternationalSymposium on Computer Architecture, 1983, 185–191
12. Lee K Y . On the rearrangeability of 2(log₂N) - 1 stage permutation networks. IEEE Transactions on Computers, 1985, C-34(5): 412–425. doi:10.1109/TC.1985.1676581
13. Andresen S . Thelooping algorithm extended to base 2ⁱ rearrangeable switching networks. IEEE Transactions on Communications, 1977, COM-25(10): 1057–1063. doi:10.1109/TCOM.1977.1093753
14. Huang S T, Tripathi S K . Finite state model and compatibilitytheory: new analysis tools for permutation networks. IEEE Transaction on Computers, 1986, C-35(7): 591–601. doi:10.1109/TC.1986.1676800
15. Varma A, Raghavendra C S . Rearrangeability of multistageshuffle/exchange networks. IEEE Transactionson Communications, 1988, COM-36(10): 1138–1147. doi:10.1109/26.7531
16. Linial N, Tarsi M . Interpolation between basesand the shuffle exchange network. EuropeanJournal of Combinatorics, 1989, 10(1): 29–39
17. Feng T Y, Seo S W . A new routing algorithm fora class of rearrangeable networks. IEEETransactions on Computers, 1994, 43(11): 1270–1280. doi:10.1109/12.324560
18. Sovis F . Onrearrangeable networks of the shuffle-exchange type. Computers and Artificial Intelligence, 1988, 7(4): 359–373
19. Can H, Fortes J A . Rearrangeability of shuffle/exchangenetwork. In: Proceedings of Frontiers ofMassively Parallel Computation. 1990, 303–314
20. Abdennadher A, Feng T Y . On rearrangeability of Omega-Omeganetworks. In: Proceedings of InternationalConference on Parallel Precessing. 1992, 159–165
21. Kim M K, Yook H, Maeng S R . On the correctness of inside-out routing algorithm. IEEE Transactions on Computers, 1997, 46(7): 820–823. doi:10.1109/12.599903
22. Cam H . Rearrangeablityof (2n - 1)-stage shuffle-exchangenetworks. Society of industrial and applied mathematics. Journal of Computers, 2003, 32(3): 557–585