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

Wachsmann A, Wanka R (1997)


Publication Language: English

Publication Status: Published

Publication Type: Conference contribution

Publication year: 1997

Pages Range: 399-408

Conference Proceedings Title: Proc 3rd International Conference on Parallel Processing (Euro-Par)

Event location: Passau

DOI: 10.1007/BFb0002763

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.

Authors with CRIS profile

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: Download