Efficient Oblivious Parallel Sorting on the MasPar MP-1

TitleEfficient Oblivious Parallel Sorting on the MasPar MP-1
Publication TypeTechnical Report
Year of Publication1996
AuthorsBrockmann, K., & Wanka R.
Other Numbers1051

We address the problem of sorting a large number N of keys on a MasPar MP-1 parallel SIMD machine of moderate size P where the processing elements (PEs) are interconnected as a toroidal mesh and have 16KB local storage each. We present a comparative study of implementations of the following deterministic oblivious sorting methods: Bitonic Sort, Odd-Even Merge Sort, and FastSort. We successfully use the guarded split&merge operation introduced by Rüb. The experiments and investigations in a simple, parameterized, analytical model show that, with this operation, from a certain ratio N/P upwards both Odd-Even Merge Sort and FastSort become faster on average than the up to the present fastest, sophisticated implementation of Bitonic Sort by Prins. Though it is not as efficient as Odd-Even Merge Sort, FastSort is to our knowledge the first method specially tailored to the mesh architecture that can be, when implemented, competitive on average with a mesh-adaptation of Bitonic Sort for large N/P.

Bibliographic Notes

ICSI Technical Report TR-96-042

Abbreviated Authors

K. Brockmann and R. Wanka

ICSI Publication Type

Technical Report