Analysis of some combinatorial properties of a 2D torus
Gennady Veselovsky · 2008
This paper introduces an exploration to the permuting ability of a 2D torus under deterministic XY routing. The research is carried out for a number of communication models, namely, unidirectional uniaxial, bidirectional uniaxial, unidirectional biaxial, and bidirectional biaxial. Necessary and sufficient conditions of blocking occurrence in a 2D torus for uniaxial models are expressed mathematically with the use of congruence notion from number theory. Examples of applying the technique to some permutations of either BPC (bit-permute-complement) or Omega class are given. Comparison of efficiency of different communication models is carried out. In particular, it is found that such important permutations as perfect shuffle and bit reversal are admissible to 2D torus under XY routing with unidirectional biaxial model.