A New Approach For Optimal MIMD Queueless Routing Of Omega and Inverse-Omega Permutations On Hypercubes

Abstract

Omega permutations constitute the subclass of particular permutations which have gained the more attention in the search of optimal routing of permutations in hypercubes. The reason of this attention comes from the fact that they are permutations for general-purpose computing like the simultaneous conflict-free access to the rows or the columns of a matrix. In this paper we address the problem of the optimal routing of omega and inverse omega permutations on hypercubes under the MIMD queueless communication model. We revisit the problem through a new paradigm: the so-called graphs partitioning in order to take advantage of the recursive structure of the hypercubes topology. We prove that omega permutations are partitionable. That is any omega permutation on n-dimensional hypercube can be decomposed in two independent permutations on two disjoint (n-1)-dimensional hypercubes. We also prove that each one of these permutations is also an omega permutation. It follows that any omega permutation on n-dimensional hypercube is routable in at most n steps of data exchanges, each step realizing the partition of the hypercube.