Rearrangeability of Tandem Cascade of Banyan-Type Networks

Xuesong TAN; Shuo-Yen Robert LI

Rearrangeability of Tandem Cascade of Banyan-Type Networks

Xuesong TAN, Shuo-Yen Robert LI

Full Text Views

0

Share
Cite this

Summary :

The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., bit-permuting unique-routing network) is the tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. Let τ denote the trace permutation of a 2ⁿ2ⁿ banyan-type network and γ the guide permutation of it. This paper proves that rearrangeability of the tandem cascade of the network is solely determined by the transposition τγ^-1. Such a permutation is said to be tandem rearrangeable when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.1 pp.67-74

Publication Date: 2007/01/01

Publicized

Online ISSN: 1745-1361

DOI

Type of Manuscript: Special Section PAPER (Special Section on Parallel/Distributed Processing and Systems)

Category: Rearrangeable Network

Cite this

Copy

Xuesong TAN, Shuo-Yen Robert LI, "Rearrangeability of Tandem Cascade of Banyan-Type Networks" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 1, pp. 67-74, January 2007, doi: .
Abstract: The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., bit-permuting unique-routing network) is the tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. Let τ denote the trace permutation of a 2ⁿ2ⁿ banyan-type network and γ the guide permutation of it. This paper proves that rearrangeability of the tandem cascade of the network is solely determined by the transposition τγ^-1. Such a permutation is said to be tandem rearrangeable when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e90-d_1_67/_p

Copy

@ARTICLE{e90-d_1_67,
author={Xuesong TAN, Shuo-Yen Robert LI, },
journal={IEICE TRANSACTIONS on Information},
title={Rearrangeability of Tandem Cascade of Banyan-Type Networks},
year={2007},
volume={E90-D},
number={1},
pages={67-74},
abstract={The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., bit-permuting unique-routing network) is the tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. Let τ denote the trace permutation of a 2ⁿ2ⁿ banyan-type network and γ the guide permutation of it. This paper proves that rearrangeability of the tandem cascade of the network is solely determined by the transposition τγ^-1. Such a permutation is said to be tandem rearrangeable when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.},
keywords={},
doi={},
ISSN={1745-1361},
month={January},}

Copy

TY - JOUR
TI - Rearrangeability of Tandem Cascade of Banyan-Type Networks
T2 - IEICE TRANSACTIONS on Information
SP - 67
EP - 74
AU - Xuesong TAN
AU - Shuo-Yen Robert LI
PY - 2007
DO -
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2007
AB - The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., bit-permuting unique-routing network) is the tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. Let τ denote the trace permutation of a 2ⁿ2ⁿ banyan-type network and γ the guide permutation of it. This paper proves that rearrangeability of the tandem cascade of the network is solely determined by the transposition τγ^-1. Such a permutation is said to be tandem rearrangeable when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.
ER -