Sorting Large Data Sets on a Massively Parallel System
Ralf Diekmann, Jörn Gehring, Reinhard Lüling, Burkhard Monien, Markus Nübel, Rolf Wanka Dept. of Mathematics and Computer Science
and Heinz Nixdorf Institute
Paderborn University
D-33095 Paderborn, Germany
{diek, joern, rl, bm, wanka}@uni-paderborn.de
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
(< 2048) and Samplesort outperforms all other methods for larger instances.
Full text in compressed Postscript format (compress used).© Copyright 1994 IEEE. Published in the Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing (SPDP); pp. 2-9; 1994.