Improved bounds for routing and sorting on multi-dimensional meshes

ABSTRACT

We show improved bounds for 1–1 routing and sorting on multi-dimensional meshes and tori. In particular, we give a fairly simple deterministic algorithm for sorting on the d-dimensional mesh of side length n that achieves a running time of 3dn/2+o(n) for the d-dimensional mesh and torus, respectively, that make one copy of each element. We also show lower bounds for sorting with respect to a large class of indexing schemes, under a model of the mesh where each processor can hold an arbitrary number of packets. Finally, we describe algorithms for permutation routing whose running times come very close to the diameter lower bound.

REFERENCES

• 1: Y. Han , Y. Igarashi, Time lower bounds for sorting on multi-dimensional mesh-connected processor arrays, Information Processing Letters, v.33 n.5, p.233-238, January 1990 [doi>10.1016/0020-0190(90)90190-9]
• 2: Yijie Han , Yoshihide Igarashi , Mirosław Truszczyński, Indexing functions and time lower bounds for sorting on a mesh-connected computer, Discrete Applied Mathematics, v.36 n.2, p.141-152, April 30, 1992 [doi>10.1016/0166-218X(92)90228-3]
• 3: Christos Kaklamanis , Danny Krizanc, Optimal sorting on mesh-connected processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.50-59, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140907]
• 4: Christos Kaklamanis , Danny Krizanc , Lata Narayanan , Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.17-28, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113381]
• 5: Michael Kaufmann , Sanguthevar Rajasekaran , Jop F. Sibeyn, Matching the bisection bound for routing and sorting on the mesh, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.31-40, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140905]
• 6: Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
• 7: M Kunde, Lower bounds for sorting on mesh-connected architectures, Acta Informatica, v.24 n.2, p.121-130, April 1987
• 8: M. Kunde, Bounds for 1-selection and related problems on grids of processors, on Parcella '88: Fourth International Workshop on Parallel Processing by Cellular Automata and Arrays, p.298-307, September 1989, Berlin, Germany
• 9: M. Kunde, Routing and sorting on mesh-connected arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 10: Manfred Kunde, Balanced routing: towards the distance bound on grids, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.260-271, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113403]
• 11: Manfred Kunde, Concentrated regular data streams on grids: sorting and routing near to the bisection bound, Proceedings of the 32nd annual symposium on Foundations of computer science, p.141-150, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185363]
• 12: Manfred Kunde, Block Gossiping on Grids and Tori: Deterministic Sorting and Routing Match the Bisection Bound, Proceedings of the First Annual European Symposium on Algorithms, p.272-283, September 30-October 02, 1993
• 13: F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
• 14: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 15: D. Nassimi and S. Sahni. Bitonic sort on a meshconnected parallel computer. IEEE Transactions on Computers, C-28:2-7, 1979.
• 16: Samuel Ellis Orcutt, Jr., Computer organization and algorithms for very-high speed computations., 1975
• 17: C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12156]
• 18: C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]
• 19: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Theory, Verification