Routing permutations on MESH interconnection networks
Jop F. Sibeyn · 2002
The author presents an algorithm for routing permutations on a n*n SIMD MESH interconnection network with wrap-around connections. If every PU has memory for three packets, then permutations are routed in 2.n+log/sup 1/2/n time with extremely high probability. This routing time is optimal within O(log/sup 1/2/n). One can bound queue lengths to 3 by sending data in a wrong direction to make room for arriving data if necessary. If the datasets to be routed consist of M>1 packets, then one can achieve a spectacular improvement over the trivial bound of (2.n+log/sup 1/2/n).M time. By splitting the datasets one can exploit the fact that on the average 3/4 of the PUs are idle during a routing step.>