Name
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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1109/SPDP.1994.346188 | Dallas, TX |
Keywords | Field | DocType |
parallel algorithms,predictive models,comparative study,prediction algorithms,radixsort,computer architecture,computer science,sorting,routing,mathematics,concurrent computing | Massively parallel,Computer science,Parallel algorithm,Parallel computing,Radix sort,Samplesort,Sorting,Grid,Computation,MIMD,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-6427-4 | 18 | 1.14 |
References | Authors | |
13 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ralf Diekmann | 1 | 281 | 28.99 |
| Jörn Gehring | 2 | 187 | 41.93 |
| Reinhard Lüling | 3 | 313 | 35.55 |
| Burkhard Monien | 4 | 2199 | 279.35 |
| Markus Nubel | 5 | 18 | 1.14 |
| Martin Lukasiewycz | 6 | 261 | 28.99 |