Efficient Low-Contention Parallel Algorithms

摘要

The queue-read, queue-write (qrqw) parallel random access machine (pram) model permits concurrent reading and writing to shared memory locations, but at a cost proportional to the number of readers/writers to any one memory location in a given step. Theqrqw prammodel reflects the contention properties of most commercially available parallel machines more accurately than either the well-studiedcrcw pramorerew prammodels, and can be efficiently emulated with only logarithmic slowdown on hypercube-type noncombining networks. This paper describes fast, low-contention, work-optimal, randomizedqrqw pramalgorithms for the fundamental problems of load balancing, multiple compaction, generating a random permutation, parallel hashing, and distributive sorting. These logarithmic or sublogarithmic time algorithms considerably improve upon the best knownerew pramalgorithms for these problems, while avoiding the high-contention steps typical ofcrcw pramalgorithms. An illustrative experiment demonstrates the performance advantage of a newqrqwrandom permutation algorithm when compared with the popularerewalgorithm. Finally, this paper presents new randomized algorithms for integer sorting and general sorting.