Ultrafast Expected Time Parallel Algorithms

✍ Scribed by Philip D MacKenzie; Quentin F Stout

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 227 KB
• Volume: 26
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0892

✦ Synopsis

It was shown previously that sorting n items into n locations with a polynomial Ž . number of processors requires ⍀ log nrlog log n time. We sidestep this lower Ž . bound with the idea of padded sorting, or sorting n items into n q o n locations. Because 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 concurrent read, concurrent write parallel random access machine Ž . Ž . CRCW PRAM and takes ⌰ log log nrlog log log n expected time using n log log log nr log log n processors, assuming the items are taken from a uniform distribution. Using similar techniques we solve some computational geometry problems, including Voronoi diagram, with the same processor and time bounds, assuming points are taken from a uniform distribution in the unit square. 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. All of these algorithms achieve linear speedup in expected time over their optimal serial counterparts.