Sorting on a massively parallel system using a library of basic primitives: Modeling and experimental results

Conference contribution


Publication Details

Author(s): Wachsmann A, Wanka R
Publication year: 1997
Conference Proceedings Title: Proc 3rd International Conference on Parallel Processing (Euro-Par)
Pages range: 399-408
Language: English


Abstract


We present a comparative study of implementations of the following sorting algorithms on the Parsytec SC320 reconflgurable, asynchronous, massively parallel MIMD machine: Bitonic Sort, Odd-Even Merge Sort, Odd-Even Merge Sort with guarded split&merge. and two variants of Samplesort. The experiments are performed on 2- up to 5-dimensional wrapped butterfly networks with 8 up to 160 processors. We make use of library functions that provide primitives for global variables and synchronization, and we show that it is possible to implement efficient and portable programs easily. In order to predict the performance, we model the runtime of an access to a global variable by a certain trilinear function and the runtime of a synchronization by a certain bilinear function. Our experiments show that, in the context of parallel sorting, this model that can be applied easily is sufficiently detailed to give good runtime predictions. The experiments confirming the predictions point out that Odd-Even Merge Sort with guarded split&merge is the fastest method if the processors hold few keys. If there are many keys per processor, a combination of Samplesort and Odd-Even Merge Sort is the fastest method.



FAU Authors / FAU Editors

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


How to cite

APA:
Wachsmann, A., & Wanka, R. (1997). Sorting on a massively parallel system using a library of basic primitives: Modeling and experimental results. In Proc 3rd International Conference on Parallel Processing (Euro-Par) (pp. 399-408). Passau.

MLA:
Wachsmann, Alf, and Rolf Wanka. "Sorting on a massively parallel system using a library of basic primitives: Modeling and experimental results." Proceedings of the 3rd International Conference on Parallel Processing (Euro-Par), Passau 1997. 399-408.

BibTeX: 

Last updated on 2018-18-10 at 20:40