Browse Prior Art Database

Efficient Parallel Quicksort Using Fetch-And-Add in Multi-Processor Computing Systems

IP.com Disclosure Number: IPCOM000057709D
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15

Publishing Venue

IBM

Related People

Authors:
Heidelberger, P Norton, A Robinson, J [+details]

Abstract

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.