Randomized priority queues for fast parallel access

doi:10.1006/jpdc.1998.1429

1998-02-01

Peter Sanders *

DOI：10.1006/jpdc.1998.1429

原文链接

查看原文

摘要

En 中文

We present simple randomized algorithms for parallel priority queues on distributed memory machines, Inserting O(n) elements or deleting the O(n) out of m smallest elements using n processors requires O(T-coll + log(m/n)) amortized time with high probability where T-coll bounds the time for performing prefix sums and randomized touting. The memory requirement is bounded by (m/n)(1 + o(1)) + O(log n) whp. These bounds are an improvement over the best previously known algorithms for many interconnection, networks and even matches the speed of the best known PRAM algorithms. Generalizations for accessing the k >> n smallest elements are even more efficient. A portable implementation using MPI demonstrates that our approach is already useful for medium scale parallelism. Two parallel selection algorithms for randomly placed data are a spin-off. One runs in time O(T-coll) with high probability, beating a lower bound for the worst case. The other requires only a single reduction operation. (C) 1998 Academic Press.

Keyword:

analysis of randomized algorithms

branch-and-bound

distributed memory

load balancing

median selection

parallel priority queue