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

Jean Pierre Jung, Ibrahima Sakho

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.

Keywords


interconnection network, omega network, hypercube, permutations, perfect shuffle, maximum matching of bipartite graph, graph partitioning, parallel processing, MIMD queueless routing.

Full Text:

PDF


DOI: http://dx.doi.org/10.5296/npa.v3i1.563

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

To make sure that you can receive messages from us, please add the 'macrothink.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.

Copyright © Macrothink Institute ISSN 1943-3581