Optimal Permutation Routing for Low-Dimensional Binary Hypercubes

Abstract

In this talk we consider the offline problem of routing a permutation of tokens on the nodes of a $d$-dimensional hypercube, under a queueless MIMD communication model (under the constraints that each hypercube edge may only communicate one token per communication step, and each node may only be occupied by a single token between communication steps). For a $d$-dimensional hypercube, it is easy to see that $d$ communication steps are necessary. We develop a theory of ``separability'' which enables an analytical proof that $d$ steps suffice for the case $d=3$, and facilitates an experimental verification that $d$ steps suffice for $d=4$. This result improves the upper bound for the number of communication steps required to route an arbitrary permutation on arbitrarily large hypercubes to $2d- 4$. We also find an interesting side-result, that the number of possible communication steps in a $d$-dimensional hypercube is the same as the number of perfect matchings in a $(d+1)$-dimensional hypercube, a combinatorial quantity for which there is no known closed-form expression. Finally we present some experimental observations which may lead to a proof of a more general result for arbitrarily large dimension $d$.