Binsorting on hypercubes with d-port communication

ABSTRACT

Three sorting algorithms are given for hypercubes with d-port communication. All of these algorithms are based on binsort at the global level. The binsort allows the movement of keys among nodes to be performed by a d-port complete exchange rather than a sequence of l-port exchanges as in other algorithms. This lowers communication costs by at least a factor of d compared to other sorting algorithms. The first algorithm assumes the keys are uniformly distributed and selects bin boundaries based on the global maximum and minimum keys. The other two algorithms make no assumption about the distribution of keys and so they sample the keys before the binsort in order to estimate their distribution. Splitting keys based on that estimate reduce the variance among the lengths of the subsequences left in the nodes after the complete exchange of bins which in turn helps to balance the computational load in each node. The performance of two of these algorithms on an FPS T-40 is given for data of various distributions and is compared to the performance of bitonic sort and hyperquicksort.

REFERENCES

• 1: K.E. Batcher, Sorting networks and their applications, Spring Joint Computer Conference, AFiPS Proceedings, v. 32, 1968, 307-314.
• 2: E. Felten, S. Karlin and S. Otto, Sorting on a hypercube, Caltech/JPL Hm244, 1986.
• 3: J.L. Gustafson, S. Hawkinson and K. Scott, The architecture of a homogeneous vector supercomputer, Int'l Conf. on Parallel Processing, 1986, 649-652.
• 4: C. Ho and S. L. Johnsson, Spanning graphs for optimum broadcasting and personalized communication in hypercubes, YALEU/Dept. of Computer Science/Tech. Rep.-500, Nov. 1986.
• 5: P.J. Janus and E. A. Lamagna, An adaptive method for unknown distributions in distributive partitioned sorting, IEEE Trans. Comp. C-34,4 (Apr. 1985), 367- 372.
• 6: S.L. Johnsson, Combining parallel and sequential sorting on a Boolean n-cube , lnt'l Conf. on Parallel Processing, 1984, 444-448.
• 7: P.P. Li, Parallel sorting on Ametek/S14, Ametek Computer Research Division, Arcadia, CA , Sept. 1986.
• 8: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 9: Q. Stout and B. Wagar, Passing messages in linkbound hypercubes, Hypercube Multiprocessors 1987, SIAM Press, Phila., 1987, 251-257.
• 10: Q. Stout, Personal communication, Jan. 1988.
• 11: B. Wagar, Hyperquicksort: A fast sorting algorithm for hypercubes, Hypercube Multiprocessors 1987, SIAM Press, Phila., 1987, 292-299.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Economics, Performance