Abstract
In this paper, we explore parallel implementations of the abstract data type priority queue. We use the BSP* model, an extension of Valiant's BSP model which rewards blockwise communication, i.e. sending a few large messages instead of many small ones. We present two randomized approaches for different relations between the size of the data structure and the number of parallel updates to be performed. Both yield work optimal algorithms that need asymptotically less communication than computation time and use large messages. All previous work optimal algorithms need asymptotically as much communication as computation or do not consider blockwise communication. We use a work optimal randomized selection algorithm as a building block. This might be of independent interest. It uses less communication than computation time, if the keys are distributed at random. A similar selection algorithm was independently developed by Gerbessiotis and Siniolakis for the standard BSP model. We improve upon previous work by both reducing the amount of communication and by using large messages.
This research was partially supported by DFG-SPB 376 “Massive ParallelitÄt” and EU ESPRIT Long Term Research Project 20244 (ALCOM-IT).
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. A. Bader, J. JáJá. Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding and Selection. Technical report, Institute for Advanced Computer Studies and Department of Electrical Engineering, University of Maryland, 1995.
A. BÄumker, W. Dittrich, F. Meyer auf der Heide, and I. Rieping. Realistic Parallel Algorithms: Priority Queue Operations and Selection for the BSP* Model. Technical Report University of Paderborn, 1996, http://www.uni-paderborn.de/cs/inri.html.
A. BÄumker, W. Dittrich, and F. Meyer auf der Heide. Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP model. Proc. of European Symposium on Algorithms, 1995.
R. J. Cole. An Optimally Efficient Selection Algorithm. Information Processing Letters, no. 26, pp. 295–299, 1987/88.
N. Deo, S. Prasad. Parallel Heap: An Optimal Parallel Priority Queue. Journal of Supercomputing, 1992, vol. 6, no. 1, pp. 87–98, 1992.
A. V. Gerbessiotis and C. J. Siniolakis. Deterministic Sorting and Randomized Median Finding on the BSP model. Proc. of the 8th Symposium on Parallel Algorithms and Architectures, 1996.
A. V. Gerbessiotis and L. Valiant. Direct Bulk-Synchronous Parallel Algorithms. Journal of Parallel and Distributed Computing, 1994.
D. Nassimi and S. Sahni. Parallel Permutation and Sorting Algorithms and a new generalized Connection Network. Journal of the ACM, 29:3, pp. 642–667, 1982.
M.C. Pinotti, G. Pucci. Parallel Priority Queues. Information Processing Letters, no. 40, 1991.
S. Rajasekaran. Randomized Parallel Selection. Foundations of Software Technology and Theoretical Computer Science, 10: pp. 215–224, 1990.
A. Ranade, S. Chang, E. Deprit, J. Jones, and S. Shin. Parallelism and Locality in Priority Queues. Proc. of the 6th IEEE Symp. on Parallel and Distributed Processing (SPDP), IEEE Society Press, 1994.
I. Rieping. RealitÄtsnahe parallele Priority Queues, Analyse und experimentelle Untersuchungen. Diploma Thesis, University of Paderborn, January, 1996.
P. Sanders. Fast Priority Queues for Parallel Branch-and-Bound. Workshop on Algorithms for Irregularly Structured Problems, LNCS, Lyon, 1995.
R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and applied Mathematics, Philadelphia, Pennsylvania, 1983.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
BÄumker, A., Dittrich, W., Meyer, F., Rieping, I. (1996). Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model. In: Bougé, L., Fraigniaud, P., Mignotte, A., Robert, Y. (eds) Euro-Par'96 Parallel Processing. Euro-Par 1996. Lecture Notes in Computer Science, vol 1124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0024725
Download citation
DOI: https://doi.org/10.1007/BFb0024725
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61627-6
Online ISBN: 978-3-540-70636-6
eBook Packages: Springer Book Archive