Parallel merge-sort algorithms on the HEP
Paul Hartono Singgih, Howard B. Demuth, Martin Hagan, Roger L. Wainwright · 1986
In this paper we describe four parallel merge-sort algorithms:(I) Parallel merging;(2) Bubble/merge; (3) Batcher's odd-even merge; and (4) Quicksort/merge.In each algorithm we divide a sequence of numbers of length n into k subsequences of equal length.Using k processors we sort each subsequence using a serial algorithm, either Merge-sort, Bubble, Batcher's or Qulcksort.Finally the k sorted subsequences are merged in parallel using a parallel implementation of the tree sort.Each algorithm was run on the Denelcor HEP computer.The HEP is the first commercially available MIMD multiprocessor system.Each algorithm was executed using k -I, 2, 4, 8, and 16 processors over dataset sizes ranging from 64 to 8192 items.The serial and parallel CPU times and the speedups for each algorithm are presented.I.