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
%0 Conference Paper
%1 346188
%A Diekmann, R.
%A Gehring, J.
%A Luling, R.
%A Monien, B.
%A Nubel, M.
%A Wanka, R.
%B Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on
%D 1994
%K overview parallel sorting
%P 2 -9
%R 10.1109/SPDP.1994.346188
%T Sorting large data sets on a massively parallel system
%U http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=346188&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D346188
%X 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
@inproceedings{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},
added-at = {2012-06-15T13:39:00.000+0200},
author = {Diekmann, R. and Gehring, J. and Luling, R. and Monien, B. and Nubel, M. and Wanka, R.},
biburl = {https://www.bibsonomy.org/bibtex/2d5e553576ed1e4108c059d50cf91e1f0/jens.willkomm},
booktitle = {Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on},
doi = {10.1109/SPDP.1994.346188},
interhash = {618b92731414206d57300087bf31cef2},
intrahash = {d5e553576ed1e4108c059d50cf91e1f0},
keywords = {overview parallel sorting},
month = oct,
pages = {2 -9},
timestamp = {2012-06-15T13:39:00.000+0200},
title = {Sorting large data sets on a massively parallel system},
url = {http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=346188&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D346188},
year = 1994
}