A NOTE ON OFF-LINE PERMUTATION ROUTING ON A MESH-CONNECTED PROCESSOR ARRAY
Danny Kriz̧anc · Parallel Processing Letters · 1991
We show how to off-line route any permutation of an n×n mesh-connected processor array in 2.5n steps with at most two packets per processor per time step and in 2.25n+3 steps with at most four packets per processor per time step.