Optimal sorting on mesh-connected processor arrays
Christos Kaklamanis, Danny Kriz̧anc · 1992
We show that sorting an input of size N = nz can be performed by an n x n mesh-connected processor array in 2n + O(n) parallel communication steps and using constant-size queues, with high probability.This result is optimal to within a low order additive term, realizing the obvious diameter lower bound.The best previously known algorithm for this problem required 2.5n + o(n) steps.Our techniques can be applied to higher dimensional meshes as well as torus-connected networks, achieving significantly better bounds than the known results.computers.While its diameter is large in comparison to other well-studied networks (e.g., hypercube, butterfly, shuffle-exchange networks), the simplicity and regularity of its interconnection pattern make it ideal for VLSI implementation.Recent work by Dally [Da187] suggests that high diameter networks such as the mesh may provide a more efficient communication medium for VLSI-based parallel computers.Furthermore, a large number of efficient algorithms have been