Rearrangeability of Tandem Cascade of Banyan-Type Networks(Rearrangeable Network,<Special Section>Parallel/Distributed Processing and Systems)

概要

論文の詳細を見る
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^n×2^n 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.
社団法人電子情報通信学会の論文
2007-01-01