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

Beitrag bei einer Tagung


Details zur Publikation

Autor(en): Wachsmann A, Wanka R
Jahr der Veröffentlichung: 1997
Tagungsband: Proc 3rd International Conference on Parallel Processing (Euro-Par)
Seitenbereich: 399-408
Sprache: Englisch


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-Autoren / FAU-Herausgeber

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


Zitierweisen

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: 

Zuletzt aktualisiert 2018-18-10 um 20:40