Technical Reports

We consider the offline problem of routing a permutation of tokens on the nodes of a -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 -dimensional hypercube, it is easy to see that communication steps are necessary. We develop a theory of ``separability'' which enables an analytical proof that steps suffice for the case , and facilitates an experimental verification that steps suffice for . This result improves the upper bound for the number of communication steps required to route an arbitrary permutation on arbitrarily large hypercubes to . We also find an interesting side-result, that the number of possible communication steps in a -dimensional hypercube is the same as the number of perfect matchings in a -dimensional hypercube, a combinatorial quantity for which there is no closed-form expression. Finally we present some experimental observations which may lead to a proof of a more general result for arbitrarily large dimension .