General properties of log2 N-stage switching networks

Various kinds of switching networks have been proposed for communications among processors and/or between processors and memories in parallel computers. Especially log2 N-stage switching networks are popular because of simplicity and easiness for routing. Although properties and permutation capabilities of individual networks have been presented, generalized discussion has not appeared yet. This paper aims at formalizing general properties of a class of log2 N-stage switching networks, and deriving useful properties applicable to the networks which use arbitrary bit-exchange type permutations as connections between stages. Particularly, conditions for admissible permutations and permutation groups which are formed by permutations realized by the networks are discussed. The results presented in this paper constitute a part of fundamental theories for log2 N-stage switching networks. [In Japanese.]