Abstract: It has been shown previously that sorting n items into n locations with a polynomial number of PRAM processors requires Ω(log n /loglog n) time. We sidestep this lower bound via Padded Sorting, in which n items are sorted into n+o(n) locations, with the extra locations blank. Since many problems do not rely on the exact rank of sorted items, a Padded Sort is often just as useful as an unpadded sort. Our algorithm for Padded Sort runs on the Tolerant CRCW PRAM and takes Θ(loglog n /logloglog n) expected time using n logloglog n /loglog n processors, assuming the items are taken from a uniform distribution.

Using padded sort and other techniques, if we assume that points are taken from a uniform distribution in the unit square, then we can solve several computational geometry problems, including Voronoi diagram, Delaunay triangulation, and all nearest neighbors, with the same processor and time bounds.

Further, we present an Arbitrary CRCW PRAM algorithm to solve the Closest Pair problem in constant expected time with n processors, regardless of the distribution of points.

Note that padded sort, and all of these geometric algorithms, achieve linear speedup in expected time over their optimal serial counterparts.

Keywords: PRAM, randomized parallel algorithm, computational geometry, lower bounds, padded sort, SIMD, shared memory

Complete paper.   This paper appears in Journal of Algorithms 26 (1998), pp. 1-33.

Other Ultrafast Algorithms:

The above result on closest pairs extends work done a decade earlier, in Constant-Time Geometry on PRAMs, where it was assumed that the points come from a uniform distribution. Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs gives ultrafast algorithms for some graph theory problems. Ultrafast Parallel Algorithms and Reconfigurable Meshes surveys various ultrafast algorithms for the PRAM and the reconfigurable mesh.

Parallel Computing:

A modest explanation of parallel computing, a tutorial on parallel computing, and a list of parallel computing resources
An overview of our work, and relevant papers.

Copyright © 2005-2008 Quentin F. Stout