Philip D. MacKenzie and
Quentin F. Stout
EECS Department, University of Michigan
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.
Copyright © 2005-2024 Quentin F. Stout |