loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
30th Hawaii International Conference on System Sciences (HICSS) Volume 1: Software Technology and Architecture
Maui, Hawaii
January 03-January 06
ISBN: 0-8186-7743-0
Klaus Brockmann, Paderborn University
Rolf Wanka, International Computer Science Institute
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?ub. 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.
Citation:
Klaus Brockmann, Rolf Wanka, "Efficient Oblivious Parallel Sorting on the MasPar MP-1," hicss, vol. 1, pp.200, 30th Hawaii International Conference on System Sciences (HICSS) Volume 1: Software Technology and Architecture, 1997
Usage of this product signifies your acceptance of the Terms of Use.