Parallel heap: An optimal parallel priority queue |
| |
Authors: | Narsingh Deo Sushil Prasad |
| |
Affiliation: | (1) Computer Science Department, University of Central Florida, 32816 Orlando, FL, USA;(2) Mathematics and Computer Science Department, Georgia State University, 30303 Atlanta, GA, USA |
| |
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 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. |
| |
Keywords: | Parallel data structure heap priority queue optimal parallel algorithm parallel random access machine |
本文献已被 SpringerLink 等数据库收录! |
|