Rearrangeability of shuffle-exchange networks

TitleRearrangeability of shuffle-exchange networks
Publication TypeConference Paper
Year of Publication1990
AuthorsCam, H, Fortes, JAB
Conference NameFrontiers of Massively Parallel Computation, 1990. Proceedings., 3rd Symposium
Date Published10/1990
AbstractA proof for the rearrangeability of (2n-1)-stage shuffle-exchange networks with N=2n inputs is given. The proof makes use of the notion of balanced matrices for representing passable permutations through a shuffle-exchange network. Because the proof is not constructive, it does not lead to a routing algorithm directly. Therefore, a heuristic algorithm is provided for routing arbitrary permutations on the (2n-1)-stage shuffle-exchange network. A new proof for the rearrangeability of the (2n-1) stage reduced ΩNΩN-1 network is also given, and a routing algorithm using precomputed digit-controlled routing tags is presented