Graphs Partitioning: An Optimal MIMD Queueless Routing for BPC-Permutations on Hypercubes

摘要

Bit-Permute-Complement permutations (BPC) constitute the subclass of particular permutations which have gained the more attention in the search of optimal routing of permutations on hypercubes. The reason of this attention comes from the fact that they care permutations for general-purpose computing like matrix transposing, vector reversal, bit shuffling and perfect shuffling. In this paper we revisit the optimal routing of BPC problem on hypercubes under MIMD queueless communication model through a new paradigm which takes advantage of their topology: the so-called graphs partitioning. We prove that BPC are partitionable in any dimension of the hypercube and that the resulting permutations are also BPC. It follows that any BPC on n-dimensional hypercube is routable in at most n steps of data exchanges, each one realizing the partition of the hypercube.