Parallelism and locality in priority queues
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 490-496
- https://doi.org/10.1109/spdp.1994.346131
Abstract
We explore two ways of incorporating parallelism into priority queues. The first is to speed up the execution of individual priority operations so that they can be performed one operation per time step, unlike sequential implementations which require O(log N) time steps per operation for an N element heap. We give an optimal parallel implementation that uses a linear array of O(log N) processors. Second, we consider parallel operations on the priority queue. We show that using a d-dimensional array (constant d) of P processors we can insert or delete the smallest P elements from a heap in time O(P/sup 1/d/log/sup 1-1/d/ P), where the number of elements in the heap is assumed to be polynomial in P. We also show a matching lower bound, based on communication complexity arguments, for a range of deterministic implementations. Finally, using randomization, we show that the time can be reduced to the optimal O(P/sup 1/d/) time with high probability.<>Keywords
This publication has 7 references indexed in Scilit:
- Theoretical Aspects of VLSI Pin LimitationsSIAM Journal on Computing, 1993
- A framework for analyzing locality and portability issues in parallel computingPublished by Springer Nature ,1993
- Parallel priority queuesInformation Processing Letters, 1991
- Concurrent access of priority queuesIEEE Transactions on Computers, 1988
- A randomized parallel branch-and-bound procedurePublished by Association for Computing Machinery (ACM) ,1988
- Area-time lower-bound techniques with applications to sortingAlgorithmica, 1986
- Searching, Merging, and Sorting in Parallel ComputationIEEE Transactions on Computers, 1983