Sorting on a Massively Parallel System Using a Library of Basic Primitives: Modeling and Experimental Results

TitleSorting on a Massively Parallel System Using a Library of Basic Primitives: Modeling and Experimental Results
Publication TypeTechnical Report
Year of Publication1997
AuthorsWachsmann, A., & Wanka R.
Other Numbers1093

We present a comparative study of implementations of the following sorting algorithms on the Parsytec SC320 reconfigurable, asynchronous, massively parallel MIMD machine: Bitonic Sort, Odd-Even Merge Sort without and with guarded split&merge, Periodic Balanced Sort, Columnsort, 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. We assume the time for accessing a global variable to be linear in the parameters s, d, and c, where s is the size of the variable, d the distance between the accessing processor and the processor holding the variable, and c the contention, i. e., the number of processors accessing the variable simultaneously. In order to predict the performance, we model the runtime of this access by a trilinear function. Similarly, the runtime of a synchronization is described by a bilinear function, depending on the number of processors involved and their maximum distance. 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 variant of Samplesort that uses Odd-Even Merge Sort as a subroutine is the fastest method. Additionally, we show that the relative behavior of implementations of different algorithms is quite similar to their theoretical relation.

Bibliographic Notes

ICSI Technical Report TR-97-028

Abbreviated Authors

A. Wachsmann and R. Wanka

ICSI Publication Type

Technical Report