Abstract
We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of θ(p) highest priority items and insertions of θ(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akl, S.G. 1984. An optimal algorithm for parallel selection. Inf. Proc. Letters, 19, 1 (July):47–50.
Bilardi, G., and Nicolau, A. 1989. Adaptive bitonic sorting: An optimal algorithm for shared-memory machines. SIAM J. Computing, 18, 2 (Apr.):216–228.
Biswas, J., and Browne, J.C. 1987. Simultaneous update of priority structures. In Proc., 1987 Internat. Conf. on Parallel Processing (Aug.), IEEE Comp. Soc. Press, Silver Spring, Md., pp. 124–131.
Cole, R. 1986. An optimal selection algorithm. Ultracomputer Note #97, Courant Institute of Math. Sci., New York Univ., N.Y. (Mar.).
Cole, R. 1988. Parallel merge sort. SIAM J. Computing, 17, 4 (Aug.):770–785.
Das, S.K., and Horng, W.-B. 1991. Managing a parallel heap efficiently. In Proc., Parallel Lang, and Arch. Europe, Lecture Notes in Computer Science, vol. 505, Springer-Verlag, Berlin, pp. 270–287.
Deo, N., and Prasad, S. 1990. Parallel heap. In Proc., 1990 Internat. Conf. on Parallel Processing, vol. 3 (Aug.), IEEE Comp. Soc. Press, Silver Spring, Md., pp. 169–172.
Ellis, C.S. 1980. Concurrent search and insertion in AVL trees. IEEE Trans. Comps., C-29, 9 (Sept.):811–817.
Fan, Z., and Cheng, K.H. 1989. A simultaneous access priority queue. In Proc., 1989 Internat. Conf. on Parallel Processing, vol. 1 (Aug.), IEEE Comp. Soc. Press, Silver Spring, Md., pp. 95–98.
Fujimoto, R.M. 1990. Parallel discrete event simulation. CACM, 33 (Oct.):31–53.
Gonnet, G.H., and Munro, J.I. 1986. Heaps on heaps. SIAM J. Computing, 15, 4 (Nov.):964–971.
Hagerup, T., and Rub, C. 1989. Optimal merging and sorting on the EREW PRAM. Inf. Process. Letters, 33 (Dec.): 181–185.
Jones, D.W. 1989. Concurrent operations on priority queues. CACM, 32, 1 (Jan.):132–137.
Karp, R.M., and Ramachandran, V. 1990. Parallel algorithms for shared-memory machines. Handbook on Theoretical Computer Science, vol. A: Algorithms and Complexity (J. van Leeuwen, ed.), MIT Press, pp. 869–941.
Leiserson, C.E. 1981. Area-efficient computation. Ph.D. diss., Carnegie-Mellon Univ., Penn.
Manber, U. 1984. Concurrent maintenance of binary search trees. IEEE Trans. Software Engineering, SE-10, 6 (Nov.):777–784.
Mohan, J. 1983. Experience with two parallel programs solving the traveling salesman problem. In Proc., 1983 Internat. Conf. on Parallel Processing (Aug.), IEEE Comp. Soc. Press, Silver Spring, Md., pp. 191–193.
Paul, W., Vishkin, U., and Wagner, H. 1983. Parallel dictionaries on 2–3 trees. In Proc., ICALP, Lecture Notes in Computer Science, vol. 154, Springer-Verlag, Berlin, pp. 597–609.
Pinotti, M.C., and Pucci, G. 1991. Parallel priority queues. TR 91–016, ICSI, Berkeley (Mar.) (to appear in Inf. Proc. Letters).
Prasad, S. 1990. Efficient parallel algorithms and data structures for discrete-event simulation. Ph.D. diss., Comp. Sci. Dept., Univ. Central Fl., Orlando (Dec.).
Prasad, S. 1991. A scalable and efficient optimistic algorithm for parallel discrete-event simulation. In Proc., Simulation Technology (SIMTEC) (Orlando, Oct. 21–23), The Soc. for Comp. Simulation, pp. 350–355.
Prasad, S., and Deo, N. 1991. An efficient and scalable parallel algorithm for discrete-event simulation. In Proc., Winter Simulation Conf. (Phoenix, Ariz., Dec. 8–11), The Soc. for Comp. Simulation, pp. 652–658.
Prasad, S., and Deo, N. 1992. Parallel heap: Improved and simplified. In Proc., Internat. Parallel Processing Symp. (Beverly Hills, California, Mar. 23–26), IEEE Comp. Soc. Press, Los Alamitos, California, pp. 448–451.
Quinn, M.J., and Deo, N. 1984. Parallel graph algorithms. Computing Surveys, 16, 3 (Sept.):319–348.
Quinn, M.J., and Yoo, Y.B. 1984. Data structure for the efficient solution of graph theoretic problems on tightly-coupled MIMD computers. In Proc., 1984 Internat. Conf. on Parallel Processing (Aug.), IEEE Comp. Soc. Press, Silver Spring, Md., pp. 431–438.
Rao, V.N., and Kumar, V. 1988. Concurrent access of priority queues. IEEE Trans. Comps., 37, 12 (Dec.): 1657–1665.
Rao, V.N., Kumar, V., and Ramesh, K. 1987. Parallel heuristic search on a shared memory multiprocessor. Tech. rept. AI TR87–45, Univ. of Tex. at Austin, Tex. (Jan.).
Wegner, L.M., and Teuhola, J.I. 1989. The external heapsort. IEEE Trans. Software Engineering, 15, 7 (July):917–925.
Author information
Authors and Affiliations
Additional information
This work was supported by U.S. Army's PM-TRADE contract N61339-88-g-0002, Florida High Technology and Industry grant 11-28-716, and Georgia State University's internal research support during spring and summer quarters, 1991.
Rights and permissions
About this article
Cite this article
Deo, N., Prasad, S. Parallel heap: An optimal parallel priority queue. J Supercomput 6, 87–98 (1992). https://doi.org/10.1007/BF00128644
Issue Date:
DOI: https://doi.org/10.1007/BF00128644