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. If the items are iid from a uniform distribution, our algorithm for Padded Sort takes Θ(loglog n /logloglog n) expected time using n logloglog n /loglog n processors on a Tolerant CRCW PRAM.

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. A preliminary version of the results appeared in Symp. on Discrete Algorithms (SODA) 1991, pp. 414-423.

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. For some graph problems, Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs gives ultrafast PRAM algorithms and Ultrafast Graph Algorithms on Reconfigurable Meshes gives ultrafast algorithms for reconfigurable meshes with limited reconfigurability. 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-2024 Quentin F. Stout