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
TR20033
Optimal Permutation Routing for Lowdimensional Hypercubes 

Authors:  Laing, Ambrose K.; Krumme, David W. 
Date:  July 2003 
Pages:  42 
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 sideresult, 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 closedform 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.