Efficient Parallel Quicksort Using Fetch-And-Add in Multi-Processor Computing Systems
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby efficient internal sorting of data is provided a parallelization of a quicksort algorithm, that is suitable for execution on a shared-memory multi-processor system, so as to exploit fetch-and-add operations. The concept implements adaptive scheduling of the partitioning phase of quicksort, executes in constant time and is used to achieve efficient processor load balancing. The algorithm used in the concept enables a large number of processors to be parameterized for specific architectures, so as to minimize synchronization overhead. Simulations of the algorithm indicate a near- linear speedup can be achieved with hundreds or even thousands of processors. Typically, in serial processors, quicksorting consists of a simple and efficient algorithm.