Technical Reports

Display by Author: A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:
Optimal Permutation Routing for Low-dimensional Hypercubes
Authors: Laing, Ambrose K.; Krumme, David W.
Date:July 2003
Download Formats: [PDF]
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 .

Faculty: for help posting a technical report please visit the User Guide.