Randomized Priority Queues for Fast Parallel Access |
| |
Affiliation: | 1. School of Science, Southwest University of Science and Technology, Mianyang 621010, China;2. Institute of Modeling and Algorithm, Southwest University of Science and Technology, Mianyang 621010, China;3. School of Management, University of Science and Technology of China, Hefei 230026, China |
| |
Abstract: | We present simple randomized algorithms for parallel priority queues on distributed memory machines. Inserting O(n) elements or deleting the O(n) out ofmsmallest elements usingnprocessors requires O(Tcoll+ log(m/n)) amortized time with high probability whereTcollbounds the time for performing prefix sums and randomized routing. The memory requirement is bounded by (m/n)(1 +o(1)) + O(logn) 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 thek⪢nsmallest 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(Tcoll) with high probability, beating a lower bound for the worst case. The other requires only a single reduction operation. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|