.png){kind=icon}
.png){kind=icon}
Return
Randomized priority queues for fast parallel access
.png){kind=icon}
OA
AI
DOI：10.1006/jpdc.1998.1429.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
analysis of randomized algorithms
branch-and-bound
distributed memory
load balancing
median selection
parallel priority queue
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available