Sorting large data sets on a massively parallel system
Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on, page 2 -9. (October 1994)DOI: 10.1109/SPDP.1994.346188
Abstract
This paper presents a performance study for many of today's
popular parallel sorting algorithms. It is the first to present a
comparative study on a large scale MIMD system. The machine, a Parsytec
GCel, contains 1024 processors connected as a two-dimensional grid. To
justify the experimental results, we develop a theoretical model to
predict the performance in terms of communication and computation times.
We get a very close relation between the experiments and the theoretical
model as long as the edge congestion caused by the algorithms is
predicted precisely. We compare: Bitonicsort, Shearsort, Gridsort,
Samplesort, and Radixsort. Experiments were performed using random
instances according to a well known benchmark problem. Results show that
for the machine we used, Bitonicsort performs best for smaller numbers
of keys per processor ( lt;2048) and Samplesort outperforms all other
methods for larger instances