Optimal Self-Routing of Linear-Complement Permutations in Hypercubes
Rajendra V. Boppana, Cauligi S. Raghavendra · 2005
In this paper we describe an algorithm to route the class of linear-complement permutations on Hypercube SIMD computers. The class of linearcomplement permutations are extremely useful in devising storage schemes for parallel array access. The proposed algorithm is self-routing and minimal, that is, the path established by the algorithm between each pair of source and destination processors is via a minimal path using only the destination processor address. Furthermore, the algorithm requires only the optimal number of routing steps to realize any linearcomplement permutation. The best known previous routing algorithms for the Hypercubes are for the class of bit-permute-complement permutations, a subset of the class of linear-complement permutations. Those algorithms are either non-optimal or not self-routing. The algorithm presented is self-routing, optimal, and it routes a larger class of permutations. Also, this algorithm can route the class of linear-complement permutations in mult...