Deterministic permutation routing on meshes
Bogdan S. Chlebus, Michael Kaufmann, Jop F. Sibeyn · 2002
We present new deterministic algorithms for routing permutations on a two-dimensional n /spl times/ n MIMD mesh. One algorithm runs in the optimal time 2 /spl times/ n - 2, while the maximal number of packets stored in a processing unit is bounded to 81. Another algorithm runs in near optimal time, 2 /spl times/ n + O(1), and has maximal queue length only 31.>