ISSN:
1573-0484
Schlagwort(e):
parallel algorithm
;
parallel architecture
;
performance evaluation
;
scalability
;
sorting
;
supercomputing
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Notizen:
Abstract We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1023/A:1008173729055
Permalink
