Conflict-free routing on hypercubes
Zhiyong Liu, Jia-Huai You, Xiaobo Li · 2003
The authors propose a conflict-free algorithm to route linear-complement (LC) permutations on hypercubes. Conflicts are avoided in a way that in addition to exchange messages along one dimension in some steps, the authors find two dimensions in some steps along which the messages are transmitted circularly. The routing algorithm realizes LC-permutations in n steps, each node holds one and only one message in each step, and only one bit in the destination address of the packet is tested in each routing step, thus the time to realize LC-permutations is significantly reduced. The algorithm is completely distributed as each node decides where to send its message independently, neither central control nor additional communication is needed for routing. The algorithm needs precomputation which can be carried out before run-time. The algorithm can be realized simply by providing a shift register in each node.>