AN EFFICIENT ALGORITHM FOR MANAGING A PARALLEL HEAPFootnote∗

∗This work was in part supported by Texas Advanced Technology Program Grant under Award No. TATP-003594031. (A preliminary version of this paper was presented at the International Conference on Parallel Architectures and Languages Europe, June 1991, Eindhoven, The Netherlands.) The authors can be reached at (817) 565-4256 and via email at [email protected]

References

• G. Bilardi and A. Nicolau , Adaptive bitonic sorting An optimal algorithm for shared-memory machines , SIAM Journal on Computing 18 , 2 (April 1989 ), 216 – 228 .
   Web of Science ®Google Scholar
• J. Biswas and J. C. Browne , Simultaneous update of priority structures , in Proceedings of International Conference on Parallel Processing ( 1987 ), 124 – 131 .
   Google Scholar
• R. Cole , Parallel merge sort , SIAM Journal on Computing 17 , 4 ( August 1988 ), 770 – 785 .
   Web of Science ®Google Scholar
• S. K. Das and W.-B. Horng , Managing a parallel heap efficiently , in Proceedings of Parallel Architectures and Languages Europe (PARLE), June 1991 , Eindhoven , The Netherlands . Also Lecture Notes in Computer Science, Springer-Verlag 505 ( 1991 ) , 270 – 287 .
   Google Scholar
• N. Deo and S. Prasad , Parallel heap , in Proceedings of International Conference on Parallel Processing III ( August 1990 ), 169 – 172 .
   Google Scholar
• N. Deo and S. Prasad , Parallel heap An optimal parallel priority queue , Journal of Supercomputing 6 ( 1992 ), 87 – 98 .
   Google Scholar
• A. K. Gupta and A. G. Photiou , Load balanced priority queue implementations on distributed memory parallel machines , manuscript . Western Michigan University , 1993 .
   Google Scholar
• W.-B. Horng and S. K. Das , Heaps—Concurrency and Parallelism , Technical Report #N-90-003, Department of Computer Science , University of North Texas , Demon , March 1990 .
   Google Scholar
• E. Horowitz and S. Sahni , Fundamentals of Computer Algorithms , Computer Science Press , Rock- ville , MD , 1978 .
   Google Scholar
• D. W. Jones , Concurrent operations on priority queues , Communications of the ACM 32 , 1 ( January 1989 ), 132 – 137 .
   Web of Science ®Google Scholar
• R. M. Karp and V. Ramachandran , Parallel algorithms for shared-memory machines , in Handbook of Vteoretical Computer Science, Volume A Algorithms and Complexity , J, van Leeuwen, ed. , MIT Press , Cambridg MIT Presse , MA , 1990 , 869 – 941 .
   Google Scholar
• R. E. Ladner and M. J. Fischer , Parallel prefix computation , Journal of the ACM 27 , 4 ( October 1980 ), 831 – 838 .
   Web of Science ®Google Scholar
• T-W. Lai and S. Sahni , Anomalies in parallel branch-and-bound algorithms , Communications of the ACM 27 , 6 ( June 1984 ), 594 – 602 .
   Web of Science ®Google Scholar
• T.-W. Lai and A. Sprague , Performance of parallel branch-and-bound algorithms , IEEE Transactions on Computers C-34 , 10 ( October 1985 ), 962 – 964 .
   Web of Science ®Google Scholar
• G.-J. Li and B. W. Wah , Coping with anomalies in parallel branch-and-bound algorithms , IEEE Transactions on Computers C-35 , 6 ( June 1986 ), 568 – 573 .
   Web of Science ®Google Scholar
• M. C. Pinotti and G. Pucci , Parallel priority queue , Information Processing Letters 40 ( 1991 ), 33 – 40 .
   Google Scholar
• M. J. Quinn and Y. B. Yoo , Data structures for the efficient solution of graph theoretic problems on lightly-coupled MIMD computers , in Proceedings of International Conference on Parallel Processing ( 1984 ), 431 – 438 .
   Google Scholar
• V. N. Rao and V. Kumar , Concurrent access of priority queues , IEEE Transactions on Computers 37 , 12 ( December 1988 ), 1657 – 1665 .
   Web of Science ®Google Scholar
• B. Wah and Y. Ma , MANIP—A parallel computer system for implementing branch-and-bound algorithm , in Proceedings of the 8th Annual Symposium on Computer Architecture ( 1982 ), 239 – 262 .
   Google Scholar
• ∗This work was in part supported by Texas Advanced Technology Program Grant under Award No. TATP-003594031. (A preliminary version of this paper was presented at the International Conference on Parallel Architectures and Languages Europe, June 1991, Eindhoven, The Netherlands.) The authors can be reached at (817) 565-4256 and via email at [email protected]
   Google Scholar
• †Current address: Dept. of Computer Science and Information Engineering, Tamkang Univ, Tamsui, Taipei, Taiwan.
   Google Scholar