Title :
A simple, fast parallel implementation of Quicksort and its performance evaluation on SUN Enterprise 10000
Author :
Tsigas, Philippas ; Zhang, Yi
Author_Institution :
Dept. of Comput. Sci., Chalmers Univ., Gothenburg, Sweden
Abstract :
We have implemented sample sort and a parallel version of Quicksort on a cache-coherent shared address space multiprocessor: the SUN ENTERPRISE 10000. Our computational experiments show that parallel Quicksort outperforms sample sort. Sample sort has been long thought to be the best, general parallel sorting algorithm, especially for larger data sets. On 32 processors of the ENTERPRISE 10000 the speedup of parallel Quicksort is more than six units higher than the speedup of sample sort, resulting in execution times that were more than 50% faster than sample sort. On one processor, parallel quicksort achieved 15% percent faster execution times than sample sorting. Moreover, because of its low memory requirements, parallel Quicksort could sort data sets at twice the size that sample sort could under the same system memory restrictions.
Keywords :
parallel algorithms; shared memory systems; sorting; SUN Enterprise 10000; cache-coherent shared address space multiprocessor; execution times; larger data sets; parallel Quicksort; parallel sorting algorithms; parallel version; performance evaluation; sample sort; simple fast parallel implementation; Clustering algorithms; Computer aided manufacturing; Computer networks; Concurrent computing; Multiprocessing systems; Parallel algorithms; Parallel processing; Sorting; Space technology; Sun;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2003. Proceedings. Eleventh Euromicro Conference on
Conference_Location :
Genova, Italy
Print_ISBN :
0-7695-1875-3
DOI :
10.1109/EMPDP.2003.1183613