DocumentCode :
868174
Title :
Parallel Quicksort using fetch-and-add
Author :
Heidelberger, Philip ; Norton, Alan ; Robinson, John T.
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
Volume :
39
Issue :
1
fYear :
1990
fDate :
1/1/1990 12:00:00 AM
Firstpage :
133
Lastpage :
138
Abstract :
A parallelization of the Quicksort algorithm that is suitable for execution on a shared memory multiprocessor with an efficient implementation of the fetch-and-add operation is presented. The partitioning phase of Quicksort, which has been considered a serial bottleneck, is cooperatively executed in parallel by many processors through the use of fetch-and-add. The parallel algorithm maintains the in-place nature of Quicksort, thereby allowing internal sorting of large arrays. A class of fetch-and-add-based algorithms for dynamically scheduling processors to subproblems is presented. Adaptive scheduling algorithms in this class have low overhead and achieve effective processor load balancing. The basic algorithm is shown to execute in an average of O(log(N)) time on an N-processor PRAM (parallel random-access machine) assuming a constant-time fetch-and-add. Estimated speedups, based on simulations, are also presented for cases when the number of items to be sorted is much greater than the number of processors
Keywords :
parallel algorithms; sorting; N-processor PRAM; Quicksort algorithm; fetch-and-add; parallel algorithm; parallelization; partitioning phase; scheduling; shared memory multiprocessor; simulations; sorting; Adaptive scheduling; Dynamic scheduling; Heuristic algorithms; Load management; Parallel algorithms; Partitioning algorithms; Phase change random access memory; Processor scheduling; Scheduling algorithm; Sorting;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.46289
Filename :
46289
Link To Document :
بازگشت